Concepts with Symbian OS (779878), страница 21
Текст из файла (страница 21)
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). If we always chose the processwith the shortest running time first, it would seem that we could improvethe measurements we are watching.As an example, consider a new set of processes:ProcessTime NeededP1P2P3P4203267The shortest-job-first (SJF) scheduling strategy is illustrated in Figure5.3.This ordering produces the following measurements:ProcessTurnaround TimeWaiting Time3103056031030P2P4P1P3P2 P4P11020P3304050Figure 5.3 Processes scheduled using a shortest-job-first strategySCHEDULING STRATEGIES97This order of processing has an average wait time of 10.75 time units.If we had used the FCFS strategy, the average waiting time would be12.25 time units.While it is possible to prove that an SJF strategy is optimal for averagetimes, the strategy has several issues.
First, it penalizes long processessimply for being long. Secondly, it becomes possible to starve a process.Starvation occurs when a process is waiting in the ready queue but nevermakes it to the running state. As long as processes enter the queue withrunning times shorter than it, that process is never run on the CPU.Finally, the hardest thing about an SFJ strategy is very basic: knowinghow long a process will take to run.
Processes typically do not enterthe ready state having determined in advance their running time. In fact,an interactive process – say, a user application with a GUI – may neverterminate (‘never’ is, of course, a relative term; read that as ‘not until theCPU stops functioning’). We can make estimates based on past behavioror estimate running time based on the process type. Typically, if somekind of prediction is to be made of running time, it is a weighted average,using, for example, a binomial distribution:Tn +1 = aTn + (1 − a)Tn −1In this calculation, a represents the weight we want to place on morerecent timing measures.
This type of estimate might take into considerationa long history of timing. This technique is called aging and is applicableto many situations where we must estimate some property in the system.Round-Robin StrategyBoth FCFS and SJF are usually used as non-pre-emptive strategies. However, we still have the criterion of fairness to consider. If we scheduleprocesses to run to completion or we depend on processes to give upthe CPU when they can, we can make measurements but we can makeno statement about fairness. Fairness can only be assured when we use apre-emptive strategy.One of the oldest and simplest pre-emptive strategies is the round-robinscheduling strategy.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
