Concepts with Symbian OS (779878), страница 23
Текст из файла (страница 23)
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. It canload arbitrary code and execute it at run time; it can interact withusers through applications.
At the same time, the operating system mustsupport real-time functionality, especially where communication functions are concerned. This combination of requirements makes schedulinginteresting.Because of the real-time requirements, Symbian OS is implemented asa real-time operating system. It is built to run on multiple phone platforms,without specialized hardware, so the operating system is considered tobe a soft real-time system. It needs enough real-time capabilities to runthe protocols for mobile protocol stacks, such as GSM and 3G (not tomention future protocols).
In fact, Symbian OS considers scheduling tobe such a basic service that the nanokernel provides it.The combination of general-purpose functionality with real-time system requirements means that the best choice for implementation is asystem that uses a static, monotonic scheduling strategy, augmented bytime slices. Static, monotonic scheduling is a simple strategy to use – itorganizes processes with the shortest deadline first – and the introductionof time slices means that processes with the same deadline (or no deadline)can be assigned time slices and scheduling using a priority-schedulingscheme. There are 64 levels of priority in Symbian OS.As we discussed before, a key to soft real-time performance is predictable execution time.
If an operating system can predict how long aprocess will run, then a static, monotonic scheduling strategy will work,since it makes some big assumptions about run time. Predicting execution106PROCESS SCHEDULINGtime is based on the process and several system characteristics. There areseveral important characteristics that must be predictable, including:• latency times: an important benchmark is the latency of handlinginterrupts: the time from an interrupt to a user thread and from aninterrupt to a kernel thread• the time to get information about processes: for example, the time ittakes to find the highest priority thread in the ready state• the time to move threads between queues and the CPU: manipulatingscheduling queues – for example, moving processes to and from theready queue – must be bounded. This functionality is used all thetime and it must have a bound on it or the system cannot predictperformance.Predicting these quantities is important and is reflected in the designof the scheduler.
For example, in order for Symbian OS to predict thetime for finding the highest-priority thread, the operating system uses 64separate queues, one for each priority level. In addition, there is a 64-bitmask, where a bit being on in the mask indicates that there are processesin the corresponding queue. This means that to choose a process from aqueue the operating system scans the mask and chooses the first processin the first available queue, instead of searching over a single queue withan unknown number of processes in it.5.6 SummaryIn this chapter, we have looked at the requirements of sharing a computer’s CPU between processes.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
