Concepts with Symbian OS (779878), страница 22
Текст из файла (страница 22)
In a round-robin strategy, all processes are given thesame time slice and are pre-empted and placed on the ready queue inthe order they ran on the CPU. The ready queue becomes a simple list ofprocesses that are ready to run and each process is placed on the end ofthat list when pre-empted from the CPU.98PROCESS SCHEDULINGP1P2P3P410Figure 5.4P120P2P330P4P1 P3 P44050P1P160Processes scheduled using a round-robin strategyFor example, consider the processes below:ProcessP1P2P3P4Time Needed2591315Let’s say the time slice in this system is 5 time units. A roundrobin scheduling strategy would produce a timeline like that shown inFigure 5.4.There is very little to manage about a round-robin strategy. The onlyvariable in the scheme is the length of the time slice – the amount oftime spent on the processor.
Setting this time to be too short – say closeto the time it takes to perform a context switch – is counterproductive. Itlets the context-switching time dominate performance and lowers CPUefficiency. However, making a time slice too long gets away from thebenefits of a round-robin strategy. Response time decreases for shortrequests.In addition, the round-robin strategy (in common with the FCFS andSJF strategies) ignores a very important concept: some processes are moreimportant than others and should be run more often.
Kernel processesare usually more important than user processes to the maintenance of anoperating system. Even within kernel processes, some are more importantto efficient use of operating system resources and some are less important.A round-robin strategy puts all processes on an equal footing.Priority StrategyA priority-scheduling strategy takes into account that processes havedifferent importance placed upon them. In priority scheduling, the processSCHEDULING STRATEGIES99in the ready queue with the highest priority is chosen to run. This typeof scheduling can be either pre-emptive or non-pre-emptive, as it is thechoice of the next process that defines a priority-scheduling strategy.Priority scheduling makes certain requirements of the operating system.First, and most obviously, the operating system must employ the conceptof process priority.
The priority is an attribute of a process that measuresthe importance of the process in relationship to others and allows theoperating system to make decisions about scheduling and the amountof time to keep a process on a processor.
In a pre-emptive schedulingenvironment, process priority is a very useful attribute to assign to aprocess. The priority of the process is usually given by a number, whichis kept in the process’s PCB.It is usually required that the operating system be allowed to manipulatepriorities somehow. Priorities are set by the user or the process creator butthe operating system is usually allowed to change priorities dynamically.This is done to reflect the properties of the processes. For example, ifa process spends most of its time waiting for I/O (is I/O-bound) thenwhen it returns from I/O requests, it is usually considered fair play togive it the processor when it wants it.
The operating system requires theability to adjust the priority of such a process as it moves through itsexecution.Priorities themselves usually take the form of numbers, quantitiesthat can be easily compared by the operating system. Microsoft Windowsassigns values from 0 to 31; various Unix implementations assign negativeas well as positive values to reflect user (negative) and system (positive)priority assignment.
As that shows, there is no general agreement onassigning priority values.Consider an example of priority scheduling. Let’s say that requests forthe processor are made in the following order:ProcessP1P2P3P4P5Time NeededPriority114267105411520For the purposes of this example, higher numbers mean higher priority.100PROCESS SCHEDULINGP5P31020P43040P1P250Figure 5.5 Processes scheduled using a priority strategyIf a priority scheduler is used, then the scheduling of processes in a nonpre-emptive scheduling environment could look similar to Figure 5.5.At each stage, the process with the highest priority is chosen to replacethe process leaving the CPU.
The average waiting time is 36.6 time units,which is not better than the other strategies, but the more importantprocesses do get executed sooner.Priority scheduling seems to address the reality of scheduling processesin an appropriate manner. However, there are a few issues that we mustattend to in order to implement priority scheduling correctly. The first isprocess starvation, an issue we have addressed with other strategies.
It ispossible to construct a sequence of process-scheduling requests wherethere is a process that is never scheduled, because each new request hasa higher priority. In this scenario, the process at the lowest priority levelis starved and never gets the CPU. This is an issue especially for heavilyloaded systems, where there are many processes and the likelihood of ahigh-priority process is great.The solution to starvation is to include the concept of aging into priorityscheduling.
The idea is to change the priority of a process as time goesby. This can be done by reducing the priority of higher-priority processesor by raising the priority of starved processes. Usually, higher-priorityprocesses are reduced in priority because that has a more rapid effect.Consider the big picture of processes: which process should have thelowest priority? On most operating systems, the process with the lowestpriority is the process that does the most menial of tasks.
It is the processthat, should it never get scheduled, no harm is done.On Microsoft Windows, this process is called the ‘System Idle Process’and is exactly what its name implies: an idle process. When the systemis idle, this process is eventually run. It does nothing – just takes up CPUcycles until something else needs the processor.In a Unix system such as Solaris, this idle process is the scheduler itself.When the system boots, it starts all processes by starting the scheduler.This scheduler starts the system initializer, called ‘init’, that spawns allSCHEDULING STRATEGIES101other processes.
When all processes are idle, the scheduler schedulesitself and runs code that burns up CPU time without doing anything.Multiple-Queuing StrategyWe have described priority scheduling as a matter of choice: choosingthe process with the highest priority to schedule on the processor. Inmany operating systems, processes do not have unique priorities. Theremay be many processes with the same priority. Many system processeshave the same high priority. This means that the scheduler is eventuallygoing to have to choose between processes with the same priority.Priority scheduling is often implemented with priority queues.
A priority queue holds processes of a certain priority value or range of values.The idea is that, if returning a process to the ready queue places thatprocess in one of several priority queues, scheduling is simply a matterof taking the head of the next nonempty queue and placing that processon the processor. The result is a faster scheduling choice when lookingfor a process to run on the CPU, but a slower return of that process to theready queue (or queues).We can generalize on this idea. If we think about grouping processesinto various classes, each class can have its own scheduling queue. Thismultiple-queuing scheduling strategy could even use multiple strategies:different scheduling strategies for different queues.
Processes are eitherpermanently assigned to a specific queue, based on their characteristicsupon entering the system, or they can move between queues, based ontheir changing characteristics as they are executed in the system. Notethat this assumes that certain characteristics are either derivable from aprocess or that the process states its characteristics as it enters the system.In turn, allowing a process to change queues implies that a process cancommunicate with the operating system about its changing requirements(know as multilevel feedback ) or that the operating system can somehowderive that a process’s needs have changed.Real-time StrategyAs we briefly mentioned in Chapter 1, real-time systems can be classifiedas one of two different system types, each with different schedulingneeds.
Hard real-time systems guarantee that time constraints are met.In hard real-time systems, there is usually a specific amount of time102PROCESS SCHEDULINGthat is specified along with the process-scheduling request. The systemguarantees that the process is run in the specified amount of time or thatthe process is not run at all. The system first responds by either acceptingthe process for scheduling or rejecting the request as not possible. Ifthe system accepts a hard real-time process-scheduling request, it mustbase this decision on its knowledge of the request and its characteristicsmatched against its knowledge of the system upon which it is runningand its resource characteristics. In order for a system to know itself thiswell, specialized software and hardware are typically needed.Soft real-time systems place a priority on time-critical processes andare less restrictive. Soft real-time systems do not guarantee performance;they give real-time processes favorable treatment and keep certain latencytimes to a minimum.
A real-time operating system must be able to assumethat scheduling overhead is restricted to a certain time. Specifically,two benchmarks must be bounded for the operating system to able toschedule in real time: the time from an interrupt to a user thread and thetime from an interrupt to a kernel thread. If these times are accuratelypredictable, even a general-purpose operating system can support softreal-time scheduling.Soft real-time systems are usually scheduled using one of two methods.A process has a fixed amount of time in which it can execute, calledits deadline.
If an operating system can manipulate process priority suchthat real-time processes are scheduled in increasing deadline order, andbefore non-real-time processes, then it can be shown that this abidesby the rules of real-time scheduling. This method is known as static,monotonic scheduling. It does not produce optimal scheduling, but it is‘good enough’ for many real-time needs. It is simple and efficient, suitablefor memory-limited systems.When it is not sufficient to be ‘good enough’, an operating systemmust make scheduling choices by paying closer attention to deadlines.In deadline-driven scheduling schemes, choices are made based on thepriority of the process in addition to some consideration of deadlines.For example, in an earliest-deadline-first scheduling strategy, choices aremade by computing how close a process is to its deadline. The choice ofthe next process to schedule is the process closest to its completion.Real-time scheduling is a complex issue.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
