20-04-2011, 04:08 PM
[attachment=12498]
ABSTRACT:
Traditional processor scheduling mechanism in operating systems is rigid. They control the sharing of machine’s CPU resources among threads using one fixed scheduling scheme., typically based on priority. Sometimes variants on basic scheduling algorithms are provided But these various techniques are hard to implement and cannot be easily fulfill needs of individual applications.
This paper represents novel processor scheduling framework based on generalized notion of priority inheritance. In this framework known as CPU inheritance scheduling, arbitrary threads can act as a schedulers for other threads by temporarily denoting their CPU time to selected threads while waiting on events of interest such as clock/timer interrupts. Different scheduling policies can be implemented under the framework and which can coexist in a single system, providing much greater scheduling flexibility. Framework ensures that all different policies work together logically and predictably.
Moreover this framework clearly address priority inversion by providing generalized form of priority inheritance that works within various scheduling policies. CPU inheritance scheduling extend naturally to multiprocessor and support processor management techniques such as processor affinity and scheduler activation
Keywords: scheduler- threads- inheritance- multiprocessor- priority inversion-scheduler activation-processor affinity
1.Introduction
1.1 Problem with existing policies:
Traditional operating system uses fixed scheduling scheme to allocate CPU resources among various threads. For different application we requires different scheduling scheme . For example for interactive process , response time is more important factor ,ie how fast user gets response to their command is more important. For batch jobs, throughput is more important. In hard real time scheduling, deadlines are more important whereas in soft real time scheduling, missing of deadline is unfortunate but not catastrophic. There is no single scheduler that serves all above purposes.
Supporting multiple scheduling policies is also become important because we are using modern system in variety of ways. for example, system that supports multimedia application or video conference needs soft real time scheduling policies but that doesn’t mean that traditional application does not need any focus. user still need quick response for their interactive programs. so for the various applications OS must support multiple coexisting processor scheduling policies so that it can fulfill various application needs and moreover it can manage CPU resources more effectively.
Finally, most existing systems still suffer from various priority inversion problems. Priority inversion occurs when a high-priority thread requesting a service has to wait arbitrarily long for a low-priority thread to finish being serviced. This problem can be addressed in priority-based scheduling algorithms by supporting priority inheritance wherein the thread holding up the service inherits the priority of the highest priority thread waiting for service. In some cases this approach can be adapted to other scheduling policies, such as with ticket transfer in lottery scheduling. However, the problem of resolving priority inversion between threads of different scheduling classes using policies with different and incomparable notions of “priority” has not been addressed so far.
1.2 Basic Idea Of scheduler:
In CPU inheritance scheduling, there is a generalized notion of priority inheritance.In this scheduling, arbitrary threads can act as schedulers for other threads by temporarily donating their CPU time to selected threads while waiting on events of interest such as clock/timer interrupts. The receiving threads can further donate their CPU time to other threads, and so on, forming a logical hierarchy of schedulers as illustrated in
Figure 1. A scheduler thread can be notified when the thread to which it donated its CPU time no longer needs it (e.g., because the target thread has blocked), so that the CPU can be reassigned to another target. The basic thread dispatching mechanism necessary to implement this framework does not have any notion of thread priority, CPU usage, or clocks and timers; all of these functions, when needed, are implemented by threads acting as schedulers. Under this framework, arbitrary scheduling policies can be implemented by ordinary threads cooperating with each other through well-defined interfaces that may cross protection boundaries. For example, a fixed-priority multiprocessor scheduling policy can be implemented by maintaining, among a group of scheduler threads (one for each available CPU), a prioritized queue of “client” threads to be scheduled; each scheduler thread successively picks a thread to run and donates its CPU time to the selected target thread while waiting for an interesting event such as quantum expiration (e.g., a clock interrupt). See Figure 2 for an illustration. If the selected thread blocks, its scheduler thread is notified and the CPU is reassigned. On the
other hand, if a different event causes the scheduler thread to wake up, the running thread is preempted and the CPU is given back to the scheduler immediately.
This scheduling framework has the following features:
1) It supports multiple arbitrary scheduling policies on the same or different processors.
2) Since scheduler threads may run either in the OS kernel or in user mode, applications can easily extend or replace the scheduling policies built into the OS.
3) It provides hierarchical control over the processor resource usage of different logical or administrative domains in a system, such as users, groups, individual processes, and threads within a process.
4) CPU usage accounting can be provided to various degrees of accuracy depending on the resources one is willing to invest.
5) Priority inversion is addressed naturally in the presence of resource contention, without the need for explicit priority inheritance/ceiling protocols.
6) CPU use is attributed properly even in the presence of priority inheritance.
2. CPU inheritance scheduling
2.1 Basic idea:
In this scheduler we use the concept of thread which is similer to the traditional system. thread is virtual CPU whose purpose is to execute instructions.A thread may be in running state or either in block state or in ready queue. A thread can be preempted and its CPU can be reassigned to another ready thread at any given time. In the traditional system, there is a scheduler who decides which thread to schedule next and it is a main component of OS for scheduling. all the performance is dependent on the efficiency of scheduler. In contrast , the basic idea of CPU inheritance scheduling is that threads are scheduled by another threads. Any thread can give its available CPU time at any instant to another thread temporarily to another specific thread instead of using the CPU itself. This operation is similar to priority inheritance in conventional systems, expect that it is done explicitly by donating thread, and no notion of priority is involved here, only direct transfer of CPU from one thread to another ,hence it is called as “CPU inheritance”.
2.2 Architecture:
2.2.1 Scheduler threads:
There is one scheduler thread that spends its most of its time donating its CPU resources to the client threads. client thread are which waiting for CPU time from scheduler thread. client thread thus inherit some portion of the scheduler thread’s CPU resources and treat that portion as their virtual CPU. Client thread can also act as scheduler thread and distributing their CPU time among their own client and so on, forming scheduling hierarchy.
There is a concept of root scheduler thread in the scheduling which is the only thread that inherently have actual CPU time available to it . other threads can only run if CPU time is donated to them. They can’t run if root thread scheduler don’t denote its CPU time to them. There is a root thread scheduler for each real CPU in the system; each CPU is permanently dedicated to supplying CPU time to its associated root scheduler thread. The actions of the root scheduler thread on a given CPU determines the base level scheduling policy for that CPU.
2.2.2 Dispatcher:
Even though all high-level scheduling decisions are performed by threads, a small low-level mechanism is still needed to implement primitive thread management functions. This low-level mechanism is called the dispatcher to distinguish it clearly from high-level schedulers. The role of the dispatcher is to implement thread blocking, unblocking, and CPU donation. The dispatcher fields events and directs them to threads waiting on those events, without actually making any real scheduling decisions.Events can be synchronous, such as an explicit wake-up of a sleeping thread by a running thread, or asynchronous,such an external interrupt (e.g., I/O or timer).The dispatcher itself is not a thread; it merely runs in the context of whatever thread owns the CPU at the time an event of interest occurs. The dispatcher inherently contains no notion of thread priorities, CPU usage, or even clocks and timers. In a kernel supporting CPU inheritance scheduling, the dispatcher is the only scheduling component that must be in the kernel;all other scheduling code could in theory run in usermode threads outside of the kernel (although this purist”approach may be impractical for performance reasons).
