POS (Program Oriented Schedule) Project

[Objective] [Introduction] [An Example] [Publications] [Contact us]

Objective

To explore the cost and the benefit of allocating resources among processes based on their behavior.
top

Introduction

Traditional process schedulers in operating systems control the sharing of the processor resources among processes using a fixed scheduling policy based on the utilization of a computer system such as a real-time or a time-sharing system. Since the control over processor allocation is based on a fixed policy, not based on contents or behavior of processes, this can hinder an effective use of a processor or can extend the processing time of a process unnecessarily.

For example, when a process uses up its timeslice just before it initiates an I/O operation, it will voluntarily relinquishes the CPU (i.e., the process blocks itself pending the completion of the I/O operation) immediately after the beginning of its next timeslice. If we had predicted the behavior of the process and delayed process switching according to the predicted behavior allowing the process to continue its execution until it initiated an I/O operation, then the extra costs mentioned above would have been avoided.

Therefore, we developed a resource scheduling idea called POS (Program Oriented Schedule). The idea of POS is by increasing an operating system's ability to alter the execution behavior of a program using the knowledge of processes' behavior obtained from the program's previous execution(s), an operating system could optimize the execution behavior of the program allowing user requirements (e.g., performance enhancement) to be satisfied. We have implemented a couple POS idea based resource scheduling mechanisms and examined the cost and the benifit of them.

See an example of how our scheduler works and how it improves performance, click here

What have we done so far:

top

An Example



Figure 1 is a simple example used to identify how our scheduler works and how it improves the performance. In Fig.1, process A and process B need respectively 3.4 seconds and 2.1 seconds of CPU time to complete their jobs. Both processes have the same priority and a timeslice of 1 second. Figure 1(a) and Figure 1(b) show the processing times of process A and process B when using a conventional timesharing scheduler and when using our scheduler respectively. In Fig.1(a), the processing times of process A and process B are 5.5 seconds and 4.1 seconds respectively, while in Fig.1(b), based on the advanced knowledge PFS that process B needs only 0.1 seconds more CPU time to complete its job, the scheduler delays process switching by 0.1 seconds to allow process B to complete its job. Delaying process switching causes the processing time of process B to be reduced to 3.1 seconds while that of process A is still the same as in Fig.1(a). Moreover, the number of process switches decreases from 6 to 4.
top

Publications

Only the main papers are shown here. See the POS Project reports page for a complete listing of papers and reports on the POS Project.

Overview/Introduction

Program Consisting of a Single Process (e.g., gzip, sort, merge)
Program Consisting of Multiple Processes (e.g., WWW server program)

top

Contact us

top
Last updated: November 4, 2004.