File management & how it relates to the internal operating system of a computer

2.1.2 Scheduling

Scheduling of processes is performed on two levels:

 high-level scheduling is used for long-term processing (anywhere from an hour to a day to a week)

 dispatching is short-term scheduling

High-level scheduling determines when a process will be admitted to the system.

 In an interactive (online) environment, processes will be automatically accep ted unless the job would overload the system.

 In a batch environment, the high-level scheduler is used to control the long-term load on a system.

An example of high-level scheduling would be a system that runs interactive and short run-time batch processes during the day, and schedules longer-running processes for the night and weekend periods.

Dispatching makes the instant-by-instant decisions on which of the processes that are ready should be given CPU execution time. There are several algorithms that the dispatcher uses to make these decisions. These algorithms are divided into two classes:

 Nonpreemptive scheduling allows a process to run to completion or until it voluntarily surrenders the CPU. This method is unpredictable because there is no control over very long-running processes or processes that are blocked while waiting for resources.

 Preemptive scheduling allows the CPU to be taken away from the process when it has become blocked or after it has run a specified time. The method is both predictable and more efficient in its use of the CPU.

Six types of scheduling are discussed below and then their impact upon the sequence of executing a queue of processes is shown in Example 6-2. You should click on the desired scheduling algorithm to see the order of processing.

Three non-preemptive algorithms are:

 First-in, first-out (FIFO) Each process is placed into a queue as it is admitted to the ready process. The dispatcher selects the process at the head of the list to have access to the CPU with no consideration of memory requirements, CPU time estimates, or priority requirements. Click on first-in, first-out in Example 6- 2 and see Figure 6-5a.

 Shortest job first The dispatcher selects the process with the shortest estimated run time to have access to the CPU. This will maximize the number of processes that are handled in any given time. Click on shortest job first in Example 6-2 and see Self-Assessment question 1.

 Nonpreemptive priority queue Processes are assigned a priority and then placed in a FIFO priority-based queue. The dispatcher selects the highest priority queue first and then the job at the head of that queue for access to the CPU. After the highest priority queue is emptied, the processes in the next highest priority queue can be selected. Click on nonpreemptive priority queue in Example 6-2 and see Self-Assessment question 2.

Three preemptive algorithms are:

 Round robin Incoming processes are placed in a FIFO queue. When a process is given access to the CPU, it retains that access until it completes, is blocked, or exceeds a pre-established time limit. At that time it is removed from the CPU. Timed-out processes are reentered into the queue. Blocked processes are reentered into the queue when they wake up. Click on round robin in Example 6-2 and see Figure 6-2b.

 Shortest remaining time Processes are selected for the CPU based on the shortest estimated running time. If the process becomes blocked while executing, it is removed, and then the process is allowed to reenter the queue using the remaining estimated run time after it wakes up. Click on shortest remaining time in Example 6-2 and see Self-Assessment question 3.

 Round robin with priority queues Processes are placed in priority-based round robin queues. The highest priority queues are emptied before lower priority queues. If a process times out, it is reentered into its priority queue. If a process with access to the CPU becomes blocked, it is removed until it wakes up, and then it reenters its priority queue.

Figures 6-5a and 6-5b demonstrate the increased efficiency of the preemptive scheduling algorithm over the non- preemptive scheduling algorithm, and show the timing of switching processes in and out of the CPU. In order to make the comparisons, we assume a computer has the following four processes that have arrived in the ready queue in the sequence shown:

 Process 1 with a run time of 20 seconds, a priority of 1, will require 20 seconds of I/O after 10 seconds of execution.

 Process 2 with a run time of 30 seconds and a priority of 2.

 Process 3 with a run time of 15 seconds, a priority of 2, will require 10 seconds of I/O after 5 seconds of execution.

 Process 4 with a run time of 5 seconds and a priority of 1.

Figure 6-5a uses the first-in, first-out non-preemptive scheduling algorithm. Figure 6-5b uses the round robin preemptive scheduling algorithm. Note that the preemptive scheduling algorithms complete in 70 seconds as compared to 100 seconds for the non-preemptive algorithms. This is because the processes waiting for I/O are blocked and thus removed from the run state in preemptive scheduling.

Figure 6-5a First-in, First-out Scheduling Algorithm

Figure 6-5b Round Robin Scheduling Algorithm

2.2.3 Variable-Partition Multiprogramming

A more flexible approach to memory management is variable-partition multiprogramming where the operating system is allowed to add, subtract, or modify the size of partitions. As programs are moved into and out of memory, holes are created. The holes are the wasted space not being used by programs.

Figure 6-10 shows holes could be created as programs are terminated and added

 shows memory with three programs and one hole

 shows memory after program 2 has been completed and removed from memory, leaving a second hole

 shows memory after program 4 has filled part of the hole, leaving a smaller hole

In Figure 6-10, there were two holes for the 60 Kb program, a 26 Kb hole and an 80 Kb hole, but the decision was an easy one because only the 80 Kb hole was big enough. In most situations, there would be more than one hole big enough in which to put a program.

Three basic algorithms can be used to determine which hole fits:

 First-fit selects the first available space in memory that can hold the program.

 Best-fit selects the memory location that is closest in size to the program.

 Worst-fit selects the biggest available hole so that the remaining hole will be the largest.

These three strategies are shown in Figure 6-11 with the holes shown in yellow. The decision of which strategy to use is determined when the parameters for the operating system are established.

Figure 6-10 Variable-Partition Multiprogramming

Figure 6-11 Memory Placement Strategies

A problem with both partitioning schemes is that the final address in memory where a program will be loaded for execution is not known. The resolution to that problem is to use base addressing where the operating system uses a base register to hold the location that corresponds to the starting location of the program.