CSci 430: Programming Project

ch9-notes.pdf

Home >Computer Science homework help >CSci 430: Programming Project

Operating Systems, Stallings

Chapter 9 Notes

CSci 430 Spring 2019

Overview

In a multiprogramming system, multiple processes exist concurrently in main memory. As we have seen and discussed many times, it is imperative that we support multiple concurrent processes in main memory, so that we can maximize the utilization of the CPU and other peripherals and devices in the computing system. However, when we have (many) more processes than we have CPUs to execute them, this necessitates that we need to periodically switch between the processes in some manner. This is especially true because many processes perform operations that will cause them to have to wait long periods (from the CPUs point of view), and if the CPU does nothing while the process is waiting, the resource is wasted, and useful work that could be done will not be performed. We need advanced memory management techniques, as we studied in the previous 2 chapters, to ensure that we have a su�ciently large number of processes available and able to be chosen from. But, until now, we have not looked at the issues and methods we should use in order to select among available processes in an e�cient manner in order to utilize CPU and other resources wisely.

In this chapter we will begin examining processor scheduling and man- agement issues. In particular, we will break the issue up into 3 di�erent time frames, short, medium and long-term scheduling concerns and methods. In chapter 9, which you are to read through this week and next, we restrict our discussion to systems with a single CPU in terms of the process scheduling issues. In chapter 10, we will look at some of the additional complications we need to consider when we are dealing with systems that have 2 or more available CPUs for scheduling processes in the operating system.

Learning Objectives

After studying this chapter, you should be able to:

� Explain the di�erences among long, medium and short-term schedul- ing.

� Assess the performance of di�erent scheduling policies.

� Be able to simulate di�erent preemptive, and non-preemptive short- term scheduling policies by hand, and understand the issues and mech- anisms involved with their implementation.

9 Uniprocessor Scheduling

9.1 Types of Processor Scheduling

The aim of processor scheduling is to assign processes to be executed by the processor(s) over time, in a way that meets system objectives. We may have many di�erent objectives in mind that we want to try and optimize, and as always in such design decisions, some are mutually exclusive such that optimizing one necessarily means performing worse in some other measure. Objectives might include response time or overall system throughput, or simply trying to maximize CPU utilization if there are processes waiting to execute. In many systems, the scheduling of processes are broken down into three separate functions: long, medium and short-term scheduling. The relative time scales of the activities performed change what the system might focus on, and what measures or features it can successfully try and optimize.

Figure 9.2 is important in understanding the di�erent time frames, and how the scheduling of processes relate to each other on these varying time frames. We will discuss in a little more detail next, but basically short- term scheduling deals with the most basic of our state process model con- cepts (from chapter 3), the ready/running/blocked transitions. Medium- term scheduling involves decision about if and when to suspend some pro- cesses to memory. And generally, long-term scheduling has to do with de- cisions in large systems of when to allow processes to begin running, and possibly terminating processes early if needed.

Long-Term Scheduling

The long-term scheduler determines which programs are admitted to the system for processing. Thus it controls the degree of multi-programming in the system. When the long-term scheduler decides to admit a new job to the system, it can add it to the queue for short-term scheduler, which causes the program to immediately be loaded into memory once it is scheduled. Or it can start the process in a swapped-out condition, which might allow the system to create some structures for the process on disk, but keeps memory free for actively running processes. Most general purpose OS will simply start processes immediately. In big batching systems or HPC computers, a batching system may hold jobs as needed, and only create them when su�cient resources are available. In such a case, the long-term scheduler might admit/create new jobs on a �rst-come-�rst-served (FCFS) basis, or it could us information about the requirements of the jobs to schedule them, for example trying to keep a mix of processor-bound and I/O-bound jobs in the system.

Medium-Term Scheduling

Medium-term scheduling is part of the swapping function. We have discussed many of the issues involved with the swapping decision already. Basically, swapping in/out processes can be used to manage the availability of primary memory on the system. So if memory is tight, the swapper can move some processes completely out of memory for a short period. But if CPU utiliza- tion is becoming low and processes are swapped out, then the medium-term scheduler might attempt to swap back in some processes in order to increase the degree of multiprogramming and thus increase CPU and resource uti- lization.

Short-Term Scheduling

In terms of the frequency of execution, the long-term scheduler usually ex- ecutes rather infrequently, and the medium-term scheduling/swapping deci- sions are also going to be somewhat infrequent. The short-term scheduler, however, often needs to be invoked very frequently. For example, every time a process becomes blocked because of read or write activities, the short-term scheduler will be run to select the next process to get the CPU. Also we often want to allow the system to preemptively cause running processes to be switched, so that we can support the illusion of multiprogramming in the system. Without preemption, the system appears to hang whenever it

executes a program that is CPU bound and runs for a long time without returning for I/O.

9.2 Scheduling Algorithms

The purpose of processes scheduling is to try and maximize performance. In order to successfully maximize performance, we have to have some idea of the criteria we want to measure, and thus try and improve by selecting processes in some speci�c manner. As the text mentions, there are many di�erent cri- teria we might try and maximize. The textbook breaks these criteria into two broad classes, user-oriented criteria and system-oriented criteria. The names should be fairly self explanatory. User-oriented criteria are those mea- sures that are visible to, and most e�ect user perceptions of how the system is performing. A classic example would be the response time of the system, how fast it appears to begin working on any command you ask it to perform. User-oriented criteria can be viewed from the perspective of a human user of the system, or from the view of a single process executing in the system. Ex- amples of system-oriented criteria would be throughput and CPU utilization. A user might just want their jobs or process to be completed as quickly as possible. But overall, from the system perspective, we want to complete as many jobs as possible in the shortest time possible. And, one way to achieve this, is to keep the CPU (and other resources) as busy as possible, given the current set of jobs we are managing. On single user type systems, such as your personal computer or smart phone, system level criteria are probably not important, it is only important that the user is getting the performance they expect from the system. System level performance criteria are more important on large shared-user systems, such as HPC supercomputers and large batching systems and server systems. Table 9.2 of our textbook gives a summary of some of the types of performance criteria you should be familiar with, in the context of the scheduling of processes.

Priorities

While it is �ne in theory to create scheduling algorithms that only look at particular criteria in order to try and �ne tune the scheduling, in practice we often need a more explicit and �ner level of control to be available to the system operators and designers to explicitly tell the system which processes to prefer over which others when scheduling. Priorities are used in many systems to allow this �ne-grained level of control. Priorities can be explicitly assigned to the entities being scheduled (e.g. processes), and the level of the

priority can be taken into account when making scheduling decisions. For example, we could implement a strict priority based scheduler, with round- robin scheduling among processes of equal priority. In a strict priority based mechanism, we would always choose among the highest priority processes currently in the system, and schedule them �rst. As shown in �gure 9.4 of our textbook, one way this could be achieved is by using separate priority queues for each level in our priority scheme. Then, when a process needs to be scheduled, we would �rst see if any processes are in the highest priority queue (and select the one at the head of this queue, if using round-robin scheduling within the priority queuing scheme). Only if the highest priority queue is empty, would we then check the next highest queue for ready processes.

One problem with this pure priority scheduling scheme we have just de- scribed is that lower priority processes may su�er starvation (and thus this scheme can be unfair in its scheduling policy). If there are always high prior- ity processes running or continually entering the system, low priority process will never be scheduled to run. Thus strict priority scheduling policies are rarely used. However, by adding a concept of aging, where the priority of a process can change dynamically, we can �x this problem. For example, the longer a process is in the system, the higher its priority might become. And conversely, the more a process executes, the lower we might set its pri- ority, for some time. Such modi�ed priority schemes are very common in modern operating systems. For example, Unix and windows variants use modi�cations of process priority, with dynamically changing priorities, in their implementations of their process scheduling mechanisms.

Alternative Scheduling Policies

In order to better understand the trades we need to make when thinking about process scheduling mechanisms, our textbook presents and compares several short-term scheduling policies in this section. I will summarize some of the important points made in this section, but you should make sure you understand all of the policies discussed in this section, how they work, and their e�ects on various criteria, such as throughput, response time, etc. Table 9.3 in our text is an important summary of the basic conclusion's about the policies we discuss in this section.

First I will talk about the rows on this table, and then we will summarize brie�y the various scheduling policies. The selection function determines how the policy decides which process will be selected next from among the pool of available ready processes. For example, for the �rst-come-�rst-serve (FCFS) policy, we will select the process that has been waiting the longest as the next to be scheduled to run. The process that has been waiting the longest must have arrived �rst, before any other process that might be waiting. Thus, by selecting the process by max(w), the one that has waited the longest, we are selecting the �rst process to arrive among the currently waiting processes (FCFS). The selection functions for all of the other policies should make sense to you, if you understand what the w (wait time), e (execution time) and s (total service time needed) parameters mean.

The decision mode is an important characteristics of process scheduling policies. Basically, non-preemptive policies are not really suitable for multi- user interactive systems. When the system schedules processes in a non- preemptive manner, this means that once the process is running, it will continue running until it is �nished. This is �ne in a batching system, but in an interactive user-based system, the system cannot fail to respond to user input if there is a long-running process currently scheduled and running. Thus we need to use preemptive scheduling processes for interactive user

systems. In a preemptive system, the running process can be halted and returned back to the ready queue (or a wait queue), based on some events. As discussed in the text, we can support di�erent types of preemption, such as only preempting if needed when a new process arrives (HRRN). However, again if we are talking about a system that supports interactive users, we will need to support time quantum (and I/O blocking based) preemption.

Throughput and response time represent two of the scheduling criteria that we might be interested in in�uencing. As we have discussed, throughput is a system-level criteria, where response time is more user-level focused.

Overhead in this table is a judgment on how costly the algorithm is to implement. If the overhead is high for the policy, it may take a lot of memory and/or CPU cycles in order to implement the data structures and calculate the selection function of the given policy.

The e�ects on process description basically gives some ideas about if the policy is fair or not, and if it is not fair, which types of processes are likely to be favored or penalized by the policy. I/O bound processes are those that need to do a lot of I/O, such as reading or writing large amounts of data to/from disk. The opposite of an I/O bound process is a compute (CPU) bound process, which once loaded into memory does not need additional I/O, and will e�ectively crunch data at a high speed (and not relinquish the CPU voluntarily).

And �nally starvation can be a consideration for some process selection policies. As we mentioned, starvation is possible for strict priority based schedulers, as low priority processes may never be selected to run if high priority processes are always present. We have talked about starvation in previous chapters on concurrency, and starvation is always a possible problem when running concurrent processes. As we see in this table, some process selection policies can be created that are guaranteed to avoid starvation, such as the simple round robin policy.

I will now brie�y mention each of the short term scheduling policies that the textbook presents and analyzes in this section. Make sure you understand how these policies work and are implemented, and the trade-o�s they make in terms of the parameters they are optimizing. Also, we will mention and use the process �nish time, turnaround time (Tr) and the normalized turnaround ratio (Tr/Ts) when we discuss these policies. The start and �nish times should be obvious, the start time is when the process �rst enters the system (not the �rst time step when it is run), and the �nish time is the time step in which the process �nishes execution. The turnaround time, also known as the residence time Tr, is simply the total time the process spent in the system (e.g. �nish time minus start time Tf − Tb) The turnaround times

is not very useful, as it can vary widely as a function of the service time of the process. The service time is how many time steps the process needs to execute in order to complete its task. This is not useful in comparing the relative performance of di�erent policies, because longer processes will have long turnaround times and short process may have short (or not) turnaround times. By dividing the turnaround time by the processes service time, we get a better understanding of the magnitude of time the process spent waiting (Tr/Ts), and we can better average and compare such ratios to judge the relative e�ects of scheduling policies on system responsiveness.

First-Come-First-Served (FCFS)

FCFS is the simplest scheduling policy, and thus has (almost) no overhead in order to implement it on a system. FCFS can also be described as (and called) a strict �rst-in-�rst-out (FIFO) queuing scheme. FCFS just requires a simple queue, and it is non-preemptive in nature. When a process arrives, we just put it on the back of the queue. And when process �nishes or we need to schedule a new process to run, we take the one at the head of the queue and it will execute until it completes (or if we have a blocked/wait state, it executes until its next I/O request). Basic batching systems use this scheduling policy.

FCFS is not particularly good in terms of response time and other char- acteristics, and as mentioned it can be unfair to I/O bound processes, as I/O bound processes will get returned back to the end of the queue, but compute bound processes, once they get scheduled, since there is no preemption, will monopolize the CPU and �nish up, leaving the I/O bound processes waiting around longer than necessary.

Round Robin

Round robin is basically the FCFS, but where we add a preemption mecha- nism. We have 1 queue, and processes that block for I/O are returned to the queue as before. But we also cause the running process to be periodically preempted, when they exceed their time slice (called the time slice quan- tum). Because of this, the RR policy is also sometimes known as a time slicing policy.

By adding the ability to preempt, RR addresses the unfairness of FCFS for I/O bound processes. However, throughput and response time may not be very good with a strict RR preemptive scheduler.

Shortest Process Next (SPN)

The SPN policy is another nonpreemptive policy. Further, in order to imple- ment SPN, each process must state up front how long it will need to execute. The selection function for SPN is to take the policy that is the shortest that is currently waiting to be executed as the next process. There are several problems with this policy in regards to implementation in real systems. As we have already mentioned, since it is nonpreemptive, it is not suitable for most interactive systems. Also for most real systems we don't often really know how long a process will need to execute. Thus we can require that an estimate be given for the length of the process when it is created and submitted. However, then we need to decide what we want to do to pro- cesses that have exceeded their stated execution service time, should the be terminated? All of these considerations need to be tracked in a real imple- mentation, which can mean that SPN needs a fair amount of overhead in order to be implemented.

SPN is actually fairly good in terms of its throughput and response time, at least for short processes. However, SPN can penalize long processes. This should be intuitively obvious, as in a system where lots of short processes continually enter the system, longer processes may have to wait a long time before they get selected to be run. In extreme cases starvation is possible, where a long process is never selected because short processes are continually always available. So SPN can be unfair to long processes.

Shortest Remaining Time (SRT)

In order to implement the SRT policy, we need to keep track of how much execution time each process still has to do. In the version discussed in our textbook, the SRT policy is preemptive, but only at the time of the cre- ation/entry of a new process. Whenever a new process becomes available, the currently running process may be preempted if the new process is shorter than the remaining time on the currently running process. In order to cal- culate the remaining time of processes, we of course need to know how much total time the process needs to run, thus the shortcoming for real implemen- tations that we discussed for SPN are also present for SRT, and it can also need more overhead than other schedulers as well.

SRT can provide good throughput and response times, though it still might penalize long processes, for the same reasons as SPN previously.

Highest Response Ratio Next (HRRN)

In order to understand HRRN, you must understand what the normalized turnaround time is and how it is calculated. If we can calculated the current normalized turnaround time for all of the processes currently in our system, HRRN simply says that we should select the process that has the highest (e.g. the worst) such measure to be the next to execute. This is intuitive if we are trying to maximize the turnaround time (and thus the throughput) of our system. By selecting the process that is doing badly on this measure next, we have a chance to improve its turnaround time, and thus improve our systems overall average. Basically, by calculating and choosing processes based on their turnaround time, we are adding a type of aging mechanism. HRRN is nonpreemptive. And as with the previous 2 policies, we need to know the expected service time in order to calculate the response ratio. This coupled with its nonpreemptive nature makes it unsuitable for interactive systems. However, HRRN does �x some of the de�ciencies that SRT and SPN have in their unfairness towards long processes, as long processes will have increasingly larger response ratios the longer they are in the system, and thus will be guaranteed to be selected at some point to be executed, thus avoiding starvation.

Feedback

The feedback policy as described in our book is basically a type of priority scheme. As discussed in this section, the feedback policy uses a preemptive (time-sliced) based mechanism, coupled with a dynamic priority mechanism. So basically, this is not a strict priority based policy, but a priority sched- uler with dynamic priority mechanism as we mentioned before. Also as we said previously, modern interactive OS systems basically use some form of dynamic priority based time-sliced scheduler, so this policy is the most im- portant to understand in order to comprehend how real OS schedulers work.

The feedback policy schedules processes on a preemptive (at a time quan- tum) basis. Processes when they �rst enter the system have a particular priority assigned to them, usually of the highest priority. After each pre- emption of the process, its priority is lowered by 1 level (down to some minimum priority).

A short process will complete quickly, with migrating very far down the priority hierarchy. A longer process will gradually drift downward. Thus newer, shorter processes are favored over older, longer processes.

The performance characteristics of a feedback/priority scheduler will vary

with the time quantum parameter (as will RR). Also, the details of the dynamic priorities will have large e�ects on the performance characteristics as well. However, since this policy is preemptive it is suitable for interactive systems. And because of the priorities, it can be tuned in various ways, to try and avoid starvation, and to give fair treatment to di�erent types of short and long and I/O and compute bound processes, as needed.