Smartphone Operating System (779883), страница 21
Текст из файла (страница 21)
Microsoft Windows 3.1used a non-pre-emptive scheduler. Applications could give up control inseveral ways. They could give it up knowingly or they could give it upthrough certain system calls or I/O functions.Early Apple Macintosh operating systems were also non-pre-emptivelyscheduled. Early systems were based on the Mach kernel, an open sourcedesign developed at Carnegie Mellon University to support operatingsystem research, primarily distributed and parallel computation. In version10, MacOS was based on FreeBSD (technically the XNU kernel), whichis pre-emptively scheduled.The part of the operating system that actually performs the pre-emptivecontext switch is called the dispatcher. The dispatcher is comprised of92PROCESS SCHEDULINGthe set of functions that moves control of the CPU from one process toanother.
The dispatcher must enter kernel mode, interrupt the processthat is currently running on the processor, move that process to the readyqueue, choose the next process to use, activate that process’s code,switch to user mode, and cause the processor to begin execution at theappropriate point in the new process. This is a tall order; there are manyprocedures to be performed. While the dispatcher must run as fast aspossible, there is overhead involved with doing its job and therefore thereis a certain latency that is experienced when the dispatcher is called in todo a context switch. This dispatch latency is inherent in the system.Scheduling CriteriaThe dispatcher is supposed to make decisions about when to removea process from the CPU and which process to assign the CPU to next.The dispatcher makes its decisions using several criteria.
There has beenmuch research devoted to the best way to schedule a CPU.The CPU must be kept as busy as possible. CPU utilization is acriterion that measures the percentage of time the CPU is busy; we wantthis percentage as high as possible. Because of the reality of executingprograms, CPU utilization is rarely at 100 percent, but a well-managedsystem can achieve high CPU utilizations of 75 to 90 percent.Another measure of CPU activity is the amount of work done over aperiod of time. Called CPU throughput, this measure can be calculatedin several different ways. For example, the number of jobs per day is acoarse measure.
A finer measure is the number of processes completed ina time unit. Short database transactions could be measured in processesper second while longer computations might be measured in processesper hour or per day.Another issue in scheduling is fairness, i.e., a measure of how muchtime each process spends on the CPU. We want to make an effort to makethe times fair. Note here that ‘fair’ does not mean ‘equal’ in all situations.Sometimes, certain processes need to spend more time on the CPU thanothers.Turnaround time is yet another criterion upon which we can basescheduling decisions. Turnaround time refers to the amount of time aprocess takes to execute.
This is measured from the time of definitionto the operating system (i.e., the time it left the create state) to the timeof termination (the time it entered the terminate state). Turnaround timelooks at all the activities of a process – including all time spent runningon the CPU, all time waiting for I/O, all time in the ready queue, etc.BASIC CONCEPTS93Another criterion is the amount of waiting time a process does. Waitingtime is the total amount of time waiting in the ready queue. Waiting timedoes not include the amount of time waiting for the system – such as I/Otime – because these times are not affected by CPU scheduling.Finally, response time is a criterion often used in making schedulingdecisions.
Response time is most often used in scheduling for interactivesystems. In interactive systems, measures such as turnaround time arenot as important as how a process responds to requests. The time fromsubmitting a request to receiving a response is how response time isdefined.In general, the goal of any scheduling strategy is to maximize CPUusage and throughput while minimizing turnaround time, waiting time,and response time. Over the running of an operating system, it is oftennecessary to consider averages of these measures or the minimum ormaximum of them.Scheduling strategies often use different criteria for different types ofsystems.
Batch-mode systems concentrate on receiving tasks and gettingthem done with little or no human interaction. For these systems, responsetime is of little interest, but minimizing turnaround time is very important.Similarly, a server-based system would want to maximize response timeas it is based on request and response pairings. A desktop system wouldwant to maximize response time and minimize waiting time.Microkernels use an interesting set of criteria.
Microkernels are usedfor both general-purpose operating systems and for specialized systemssuch as mobile phones. Because of this, different criteria are applied fordifferent situations. A microkernel usually moves scheduling from serversand makes it a kernel-mode activity, thus acting like a general-purposeoperating system. However, a microkernel must pay close attention tofairness, because many of the processes in user space implement systemfunctions. In addition, there is a fair amount of overhead in a microkernelsystem, because system processes communicate with each other bypassing messages (rather than through kernel memory).
Keeping CPUutilization high, the communication overhead low and scheduling fair isa difficult thing for microkernels.A mobile phone system is a microkernel with a mixture of system types.It has elements of real-time systems and elements of interactive systems.A phone-based operating system would want to minimize response timeand waiting time, but turnaround time is not very important as there arefew applications that are started to do short, specific tasks. Throughputis hard to measure on a phone-based system, because processes are94PROCESS SCHEDULINGdesigned to service requests in the long-term and they stay running forrelatively long periods of time.5.2 Scheduling StrategiesWe have just discussed the concepts involved in scheduling processes toshare a CPU and the criteria used to make decisions about CPU usage.There are several strategies that use scheduling concepts and criteria toimplement CPU sharing.
As we discuss these strategies, note that wefocus on the problems of deciding which process should use the CPUand when a process should be removed from using the CPU.First-Come-First-Served StrategyPerhaps the easiest way to schedule a CPU is on a first-come-first-served(FCFS) basis. This scheduling strategy allows the first process that requestsa CPU to use the CPU until the process is completed. When one processis using the CPU, other processes that need the CPU simply queue upin the ready queue. This allows the head of the ready queue to be usedas the next process to be scheduled. This scheduling strategy is nonpre-emptive. Processes are removed from the CPU only when they are inthe waiting state or they have terminated.Consider the following set of processes that arrive to use a CPU in theorder stated:ProcessTime NeededP1P2P3P4295154An FCFS scheduler would schedule them as shown in Figure 5.1.P110Figure 5.1P22030P340P450Processes scheduled using a first-come-first-served strategySCHEDULING STRATEGIES95We can state the turnaround time and the waiting time for the processesin the following table:ProcessTurnaround TimeWaiting Time293449530293449P1P2P3P4The throughput of our imaginary system is 4 processes in 53 time units,or 0.075 processes per time unit.It is also useful to consider average measures, such as the averagewaiting time.
In our example, the average waiting time is 28 time units.The order in which the processes are granted requests makes a largedifference to the measurements we take. Consider a different ordering ofprocesses, shown by the time bar in Figure 5.2.In this situation, we can measure time in the following way:ProcessTurnaround TimeWaiting Time59245305924P2P4P3P1In this scenario, the throughput of our system is the same: 4 processesin 53 time units.
But the waiting time is much better: the average waitingtime for this example is 9.5 time units.It is easy to see how a FCFS strategy does not guarantee minimal criteriaand measures may vary substantially depending on process executionP2P4P310P120304050Figure 5.2 Processes scheduled using a FCFS strategy in a different order96PROCESS SCHEDULINGtimes and the order of execution. Fairness issues hurt the consideration ofthis scheduling strategy. FCFS is inherently unpredictable and may verylikely produce unfair schedules.Shortest-Job-First StrategyAnother non-pre-emptive strategy can be invented from the examplesabove. The first example ran the longest process first (because it requestedfirst) and, in doing so, worsened the measurements that we took (anaverage wait time of 28 time units rather than the 9.5 time units whenwe scheduled the shorter processes first).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
