Algorithm

Scheduling in Batch Systems
1460 views
Scheduling in Batch Systems

It is now time to turn from general scheduling issues to specific scheduling algorithms. In this section we will study algorithms used in batch systems. In the following ones we will study interactive and real-time systems. It is worth pointing out that some algorithms are used in both

Shortest Process Next
1171 views
Shortest Process Next

Because shortest job first always creates the minimum average response time for batch systems, it would be nice if it could be used for interactive processes as well. To a certain extent, it can be. Interactive processes usually follow the pattern of wait for command, execute

CLASSICAL IPC PROBLEMS
2525 views
CLASSICAL IPC PROBLEMS

The operating systems literature is full of interesting problems that have been extensively discussed and analyzed using a variety of synchronization methods. In the following sections we will look at three of the better-known problems.

RESEARCH ON PROCESSES AND THREADS
1093 views
RESEARCH ON PROCESSES AND THREADS

In INTRODUCTION, we examined some of the current research in operating system structure. In this and subsequent sections we will consider more narrowly focused research, starting with processes. As will become clear in time, some subjects are much more settled than

Managing Free Memory
1729 views
Managing Free Memory

When memory is allocated dynamically, the operating system must manage it. Generally, there are two methods to keep track of memory usage: bitmaps and free lists. In this section and the next one we will study these two methods.

PAGE REPLACEMENT ALGORITHMS
1115 views
PAGE REPLACEMENT ALGORITHMS

When a page fault takes place, the operating system has to choose a page to remove (remove from memory) to make room for the incoming page. If the page to be removed has been customized while in memory, it must be rewritten to the disk to bring the disk copy up to date. If,

The Not Recently Used Page Replacement Algorithm
2092 views
The Not Recently Used Page Replacement Algorithm

In order to allow the operating system to collect useful page usage statistics, most computers with virtual memory have two status bits associated with each page. R is set whenever the page is referenced (read or written). M is set when the page is written to (i.e., modified).

The Least Recently Used (LRU) Page Replacement Algorithm
1689 views
The Least Recently Used (LRU) Page Replacement Algorithm

A good estimation to the best algorithm is based on the observation that pages that have been heavily used in the last few instructions will possibly be heavily used again in the next few. On the other hand, pages that have not been used for ages will possibly remain unused for a

The WSClock Page Replacement Algorithm
1259 views
The WSClock Page Replacement Algorithm

The main working set algorithm is unwieldy, since the entire page table has to be scanned at each page fault until a suitable candidate is located. An improved algorithm, that is based on the clock algorithm but also uses the working set information, is called WSClock (Carr and

Summary of Page Replacement Algorithms
932 views
Summary of Page Replacement Algorithms

We have now considered a variety of page replacement algorithms. In this section we will briefly summarize them. The list of algorithms discussed is given in Figure 1.

Page 1 of 2 Previous 1 2 Next