Smartphone Operating System (779883), страница 23
Текст из файла (страница 23)
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. Much research work hasbeen done on this topic that proves complicated scheduling can beaccomplished by adopting some simpler policies. [Leung and Whitehead1982] and [Liu and Layland 1973] are well worth reading for some moreinformation on this topic.SCHEDULING IN LINUX1035.3 Scheduling in LinuxProcess scheduling in Linux tries to accommodate all kinds of needs.
Itis a time-sharing system, giving general-purpose processes a time sliceand multiplexing the CPU based on those time slices. This means that theLinux process scheduler is a pre-emptive scheduler. Understanding theimportance of certain processes over others, Linux also uses a dynamicprocess-priority strategy. In addition, Linux uses a real-time schedulingstrategy with deadline scheduling for real-time processes.
Thus, Linuxhandles all types of processes, from interactive processes through batchprocessing, even real-time processes.The Linux scheduling algorithm divides CPU time into epochs. At thebeginning of each epoch, the time slice of every process waiting to bescheduled is recomputed. This means that different processes generallyhave different sizes of time slice.
If a process does not exhaust its time slice(for example, it goes into the wait state before its time slice is complete),it can be rescheduled on the CPU for the remainder of the time slice. Anepoch is complete when all processes have run for their time slice.Priority values affect which process with remaining time in its time sliceis chosen next for the CPU. As stated previously, Linux uses dynamic priorities for conventional process scheduling.
Linux computes the dynamicpriority as the sum of the time slice quantity and the amount of time leftuntil the end of the time slice.Real-time scheduling in Linux is performed by raising the priority ofreal-time processes and by tuning the operating system to make boundson system overhead. If a real-time process is running, pre-emption shouldnot allow a lower-priority process to take over the CPU ahead of anyother real-time process.Process scheduling in Linux is relatively straightforward. The epochmethod ensures that all processes are run in a certain time period, butthat more important processes are executed first.• This algorithm is good for a variety of uses – interactive, batchmode – that do not stretch a system to the limit.
In this environment, the Linux algorithm can run all the processes, avoid processstarvation and even service real-time processes.• If the number of processes is large, recalculating the process timeslices before each epoch is quite inefficient. System responsivenessdepends on the average time-slice duration of processes in the readystate.
For systems under high loads, choosing this time-slice quantity104PROCESS SCHEDULINGcan be tricky and the time slice chosen by the Linux schedulingalgorithm is often too large.• Linux has a strategy of dynamically raising the priority for I/O-boundprocesses. This ensures a short response time for interactive processesand provides an aging strategy to avoid starvation. However, processesthat wait for I/O but do not require user interaction also have theirpriority artificially boosted.
Thus, if a system has many I/O-boundprocesses, all processes – even those with user interaction and littleI/O – suffer.• Real-time support is based on the fact that real-time processes arescheduled often and that all system latencies are predictable. Thesecriteria are supported in Linux (providing the operating system ispre-emptively scheduled) but there are other issues. It is possible, forexample, for a lower-priority process to block a real-time process.This can occur when the lower-priority process is running when thereal-time process enters the ready state. This phenomenon is knownas priority inversion. In addition, a real-time process could need asystem service that is servicing the request of a lower-priority process.This problem is known as hidden scheduling.
Linux allows bothpriority inversion and hidden scheduling and thus has weak supportfor real-time processes.5.4 Scheduling in a Microkernel ArchitectureRecall that a microkernel architecture is an attempt to minimize the sizeof kernel-level structures and to push as much functionality as possibleto the user level. The question with regard to scheduling in microkernelsis where to place the scheduler. Is process scheduling a kernel-level or auser-level function?Placing scheduling at the user-level has a certain appeal. Schedulingpolicies can change more easily – even at a user’s discretion.
Systemscan be customizable – users can set their own scheduling strategies andapplications can alter how scheduling is done.Placing scheduling functionality at the kernel level has a few advantages. Essentially, scheduling relies on kernel information. A schedulermust know, for instance, how long a process has been using the CPUand what the priorities of processes are. A scheduler must also accesskernel-level structures, including process queues and PCBs, and handleSCHEDULING IN SYMBIAN OS105kernel-level events, such as interrupts. Because a scheduler must accessso many kernel-level objects, scheduling is typically a kernel-level function, even in a microkernel.
Because the overhead of making lots ofkernel requests is high, placing scheduling at the user level would hurtan implementation. Allowing a scheduler access to information is muchfaster than making many requests for the same information.This means that scheduling is one of the basic functions of an operatingsystem that is kept at the kernel level by a microkernel. Whateverthe structure of an operating system – monolithic to microkernel – thescheduler is built into the kernel.5.5 Scheduling in Symbian OSSymbian OS is a mobile phone operating system that is intended tohave the functionality of a general-purpose operating system.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
