For problems 1 and 2, a computer has the following four processes that have arrived in the ready queue in the sequence shown below. NOTES: (1) Time slicing is not used, therefore, there are no mandatory time outs. (2) I/O operations only occur one time du

For problems 1 and 2, a computer has the following four processes that have arrived in the ready queue in the sequence shown below. NOTES: (1) Time slicing is not used, therefore, there are no mandatory time outs. (2) I/O operations only occur one time during the process execution.

· Process 1 has a run time of 30 seconds, a priority of 2, and it will require 15 seconds of I/O after an initial 10 seconds of execution.

· Process 2 has a run time of 20 seconds, a priority of 1, and it will require 10 seconds of I/O after an initial 5 seconds of execution.

· Process 3 has a run time of 15 seconds and a priority of 2.

· Process 4 has a run time of 25 seconds and a priority of 1, and it will require 15 seconds of I/O after an initial 10 seconds of execution

 

(HINT for problems 1 and 2: Review Module 6 section 2.1.2 for the definitions of these scheduling algorithms and Self-Assessment problems 1-4.)

 

1. (2.5 points) If the Round Robin Scheduling algorithm is used, which process completes first? Why? At what time does it complete?

 

2. (2.5 points) If the Round Robin with Priority Queues Scheduling algorithm is used, which process completes second? Why? At what time does it complete?

 

3. (2 points) The manual for a popular operating system points out that the number of concurrent users on the system can be increased if the users are sharing programs, such as editors, mail readers, or compilers. What characteristics of virtual storage make this possible?

 

4. (3 points) Using a variable-partitioned multiprogramming memory, which of the four holes shown below will be used to satisfy a 45 KB program requirement under the conditions of:

 

0-45 KB	45-105 KB	105-145 KB	145-185 KB	185-260 KB	260-330 KB	330-350 KB	350-405 KB	405-470 KB
occupied	Hole A	occupied	Hole B	occupied	Hole C	occupied	Hole D	occupied

___ First-fit ___ Best-fit ___ Worst-fit

 

(HINT: See Module 6 section 2.2.3 and Self Assessment problem 6.)

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 accepted 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 nonpreemptive 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. Click on round robin with priority queues in Example 6-2 and see Self-Assessment question 4.

Example 6-2 Nonpreemptive and Preemptive Dispatching Algorithms

Figures 6-5a and 6-5b demonstrate the increased efficiency of the preemptive scheduling algorithm over the nonpreemptive 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 nonpreemptive 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 nonpreemptive 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

Top of Form

Self Assessment: Operating Systems, Programming Tools, and System Administration

After you have completed the readings, answer the following self-assessment questions. These questions will not be graded and should not be submitted to your instructor. The hypertext link provides the answer so that you can assess whether your answers are correct. If you cannot understand how an answer was obtained, you should contact your instructor for a more detailed explanation. For problems 1 to 4, 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, and it 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, and it 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.

Question 1

If the shortest job first scheduling algorithm is used, at what times will each of the four processes complete its execution?

Question 1 options:

Hide Check my answer

Question 2

If the nonpreemptive priority queue scheduling algorithm is used, at what times will each of the four processes be complete?

Question 2 options:

Hide Check my answer

Question 3

If the shortest remaining time scheduling algorithm is used, at what times will each of the four processes be complete?

Question 3 options:

Hide Check my answer

Question 4

If the round robin with priority queues scheduling algorithm is used with a timeout after 15 seconds of execution, at what times will each of the four processes complete its execution?

Question 4 options:

Hide Check my answer

Question 6

Using a variable-partitioned multiprogramming memory, which of the three holes shown below will be used to satisfy a 50 Kb program requirement under the conditions of:

______	First-fit
______	Best-fit
______	Worst-fit

Question 6 options:

Hide Check my answer
__A___first-fit  __C___best-fit __A___worst-fit

Information

The FAT below applies to self-assessment questions 7 through 10.

Bottom of Form