Abstractions Using Scheduled Algorithms and Time Units March 5, 2007 Tova Ashby Chih-Hung Cho David Greenwood Rodney Levy Chi Toung Yeung Overview This is in response to the project assignment due on the last day of this course. As mentioned in class, we intend to study CPU scheduling in conjunction with process code, process state, process control block, process scheduling, process creation, CPU-I/o burst cycle, CPU scheduler context switching and scheduling algorithms. The following proposal describes the project scope, outlines five scheduling algorithms we intend to implement, and discusses the time, method as well as resource required to complete the project. Background A lot of literature exists on CPU scheduling algorithms. From our text alone, almost the entire chapter five is devoted on this topic. The authors describe algorithms, operating system examples and evaluation of each method?s merit and shortcomings. Clearly, scheduling is an important topic with as many solutions as there are challenges. Each technique has its merit and specific application; some, such as Multi-level scheduling, might be specialized for multi-processors. Other, FCFS, might be best suited for real-time operating systems. Proposal In this project, we will be devoting as much if not more energy in application development than actual measurements and study of CPU performance under different scheduling schemes. In addition to implementing an assortment of scheduling algorithms, we will implement report and measurement mechanism for CPU and processes. Also, some attention will be spent on configurable input and output options. Development method Though C is the language of choice for the course, we as a group have decided to use Java. The benefit of using an object oriented language is immediately apparent. As scheduling algorithms are evolutionary, many techniques contain the behavior and strategy of others. For example, Multi-level feedback-queue scheduling algorithm is a combination of FCFS with priority and multiple queues. Round-robin scheduling is a combination of FCFS scheduling algorithm of time slicing. Most of the common behaviors can be inherited from common classes in our development effort. A second benefit is simplicity. With automatic garbage collection and no pointers, it is much easier to debug a collaborative project. Scheduling Algorithm FCFS ? also known as first come first serve scheduling is probably the simplest technique of all. This is essentially a FIFO queue of processes that waits for CPU. For a real operating system running in 32 bits mode, 2,147,483,647 processes may be a likely number of maximum processes to running concurrently. To offer this flexibility, we will use a link-list to create our FIFO queue. SJF ? also known as shortest job first is simplest in conception. This algorithm sorts jobs base on their next CPU burst. While this algorithm is theoretically optimal, finding the next CPU burst requires predictive calculation in the following form. Tn+1 = ? tn+(1-??)Tn RR ? Round Robin scheduling is similar to FCFS except processes are interrupted when they last longer than the pre-designed time quantum. After popping a job from the FIFO queue, if the job is not completed, it is push back into the end of the queue. The result is a circular queue pattern. Multi-level queue scheduling employs multiple instances of FCFS. Similarly multi- level feedback queue scheduling utilizes multiple queues. However, process in multi- level feedback scheduling are promoted or demoted to different queues base on its CPU burst time. Process control block Here are some units of record in our process control. These variables will offer us a near real time measure of activities and status for our processes and CPU usage. * Process number * Program counter: to index next instruction in ?code?. * Process state: new, ready, running,waiting, terminated. * List of open files * CPU scheduling information * Account information * I/O status information Reports & Measurement In our simulation, we will measure and report CPU activities such as utilization, throughput, turn-around time, waiting time ( units spent in a ?new?, ?ready? and ?wait? state ) and response time. We will also evaluate context switching by interrupts from I/O bound activities. Input & Output Artificial tasks may be read in from ASCII files containing CPU burst or I/O wait periods. For example, a CPU bound process could look like this: 1111111111111111111111100001111111111111111111100001111111111111111... And an I/O bound process could look like this: 111000000000000000000000000000000000000000111000000000000000000011... Output data will consist of a chronological recording of process control block as well as CPU units as described in the above mentioned section. Feasibility We do not anticipate any problems in designing, implementing or integrating this project. We project that the project will be completed by the deadline date. Procedure In a group effort of six individuals, we will accomplish the following tasks in chronological order. 1. Design and explore project scope - We design the coverage of our project; algorithms to implement, development language, input & output for our simulation. 2. Project design architecture ? We design a workflow that functionally describes our object components and their inter-relationship. Design common class interface, methods and member variables. 3. Implementation - We divide our development effort amongst team members. Each member will be responsible for his/her algorithm / class development. 4. Integration - We will combine each team member?s object code into a single application. Much testing and debugging is expected here. 5. Evaluation & Analysis ? measurement of performance for each scheduling algorithm will be studied and scrutinized. 6. Report ? Some conclusive data will be gained based on the merits and short coming of each scheduling strategy. Result The end product of this project will consist of a Java language simulation application, performance data of various scheduling techniques and a report detailing strengths and weakness of our scheduling techniques. Information Sources At present, we have most of the basic theoretical knowledge required to begin work on this project. For fine details of scheduling algorithms, we will obtain from our class text as well as others from Internet and/or library. Project Schedule The following is a tentative schedule for the project. Week 3: Project discussion Week 4: Proposal Week 5: Project design architecture Week 6: Algorithms assigned to individual team members Week 8: Individual algorithm assignment complete Week 9: Individual class tested and debug Week 12: Integration of simulation application complete Week 13: Project application tested and debug Week 14: Evaluation and analysis complete Week 15: Report and paper complete Tentative Bibliography Silberschatz, Galvin, Gagne, Operating System Concept, 7th edition, John Wiley & Sons. Inc, 2005