To explore the cost and the benefit of allocating resources among processes based on their behavior.top
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.topFor 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:
- We start assessing the usefulness of our idea with the programs that consist of only a single process (e.g., gzip, merge, and sort) in which the mutual relation is not a concern. In this case, our scheduler alters the execution behavior of a process by allowing a process to continue its execution even though its quantum has already expired, when it is predicted based on observed results that a process needs a little bit more CPU time before it issues an I/O operation. And our experimental results show that the processing time of a process can be reduced by using this scheduler.
For more information about this, see some selected papers.
- The above results motivate the next question whether programs consisting of multiple processes such as servers also provide better performance using the POS idea. We used a WWW server for our research, since it is the most commonly used type of servers. In this case, our scheduler alters the execution behavior of a WWW server by giving preferential use of the resources (e.g., a CPU, a disk drive) to any process of a server that is predicted to be a server process handling an HTML file request. And our results show that the response time is improved when using this scheduler.
For more information about, see some selected papers.
top
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.
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.topOverview/Introduction
Program Consisting of a Single Process (e.g., gzip, sort, merge)
- S. Suranauwarat and H. Taniguchi, " The Design, Implementation and Initial Evaluation of an Advanced Knowledge-based Process Scheduler ," ACM Operating Systems Review , vol.35, no.4, pp.61-81, Oct. 2001.
- H. Taniguchi, "Realizing Efficient Input/Output Processing based on Learning the Flow of Input/Output Request - Realizing Efficient Input Processing -," In Proc. of the 1997 IPSJ Computer System Symposium , pp.141-148, 1997. (in Japanese)
- H. Taniguchi, "POS : Program Oriented Schedule," In Proc. of the 1996 IPSJ Computer System Symposium , pp.123-130, 1996. (in Japanese)
Program Consisting of Multiple Processes (e.g., WWW server program)
- S. Suranauwarat and H. Taniguchi, " The Design, Implementation and Initial Evaluation of an Advanced Knowledge-based Process Scheduler ," ACM Operating Systems Review , vol.35, no.4, pp.61-81, Oct. 2001.
- S. Suranauwarat and H. Taniguchi, " The Implementation and Evaluation of a Disk Scheduling Policy for a WWW Server Based on Its Contents ," J. IPS Japan , vol.42, no.6, pp.1472-1482, June 2001. (in Japanese)
- S. Suranauwarat and H. Taniguchi, " Evaluation of a Process Scheduling Policy for a Web Server Based on Its Contents ," IEICE Trans. Inf. Syst. , vol.E83-D, no.9, pp.1752-1761, Sep. 2000.
- S. Suranauwarat and H. Taniguchi, " Process Scheduling Policy for a WWW Server Based on Its Contents ," J. IPS Japan , vol.40, no.6, pp.2510-2522, June 1999. (in Japanese)