1Computer Science 4500Operating Systems© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 1Operating SystemsModule 6Process Scheduling MethodsIn This Module…Batch and interactive workloadsScheduling basics© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 2The goals of schedulingSelected scheduling algorithmsPolicy and mechanismBatch ProcessingBatch processing was so named because multiple jobs were presented to a system for processing.Today, batch processing is more likely called © 2008 Stanley A. Wileman, Jr. Operating Systems Slide 3ypg ybackground processing, since each job is usually submitted individually, and not as part of a group of jobs.Batch, or background jobs usually don’t perform I/O on terminals or other interactive devices. They don’t have the timing restraints normally associated with those devices.Interactive ProcessingInteractive processes do normally utilize on-line devices like terminals, mice, and other devices designed for human input and output (as well as di k d th d i l d b b t h j b )© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 4disks and other devices also used by batch jobs).As such, it is usually important for these processes to be able to respond to user input in a timely manner.For example, when a user presses a key or moves a mouse, it is important that the terminal quickly report recognition of that input.Scheduling BasicsScheduling is the name given to all activities of a system associated with determining when various actions are to© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 5determining when various actions are to be performed.The scheduling with which we are concerned in this module is that associated with deciding when a process is allowed to use the CPU.Execution Sequences are FiniteActions of a single process are conceptually piecewise sequential, with the sequence in which the pieces are executed determined by itIf i lti ith© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 6input. If a program is run several times with exactly the same input, it should execute exactly the same sequence of instructions.Interactions with other processes may possibly alter the order in which the actions of a process occur, but we can still enumerate all possible sequences of execution without executing the process.2Job SchedulingJob scheduling has to do with deciding when a job (or a sequence of sequential steps) is to be started.© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 7This is done using information about the resources required by the entire job, and the currently available system resources.Job scheduling is sometimes called “high-level” scheduling, since a job is a larger, or higher-level unit of work than an individual process.Non-Multitasking Job SchedulingBefore multitasking, each job was run separately (since it wasn’t possible to have two or more processes executing© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 8have two or more processes executing concurrently).Each job had a time limit specified for its CPU usage, and this limit was used in making job scheduling decisions.Process SchedulingProcess scheduling is sometimes called “low-level” scheduling, since these scheduling decisions are made after a process has been © 2008 Stanley A. Wileman, Jr. Operating Systems Slide 9padmitted to the system.You might image that there is an additional process state associated with processes that have not yet been admitted to the system; processes in this state cannot compete for system resources.Goals of SchedulingFairness: each process should get its “fair share” of the CPU time.Efficiency: the CPU should be kept busy.© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 10ypyResponse time: interactive users should receive timely responses to their actions.Turnaround: batch users should get reasonable response.Throughput: maximize the number of jobs in a given time period.Preemptive vs. Non-Preemptive SchedulingPreemptive scheduling allows processes that are logically runnable to be suspended (i.e. removed from the running state). [Windows NT/98/2000 UNIX OS/390]© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 11NT/98/2000, UNIX, OS/390]Non-preemptive scheduling (also known as run-to-completion scheduling) allows a process to continue using the CPU as long as it wishes. Such scheduling still allows a process to yield the CPU or become blocked. [Windows 3.1]ClocksTo allow preemptive scheduling, virtually all systems include clocks that cause a periodic interrupt.© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 12pEach time this interrupt occurs (typically 50 or 60 times per second), the system updates the time of day clock, starts any actions scheduled for that time, and preempts processes that have had enough CPU time.3Round-Robin SchedulingThe ready state is structured as a queue.Each process is given a finite amount of time, called its quantum, during which it may use the CPU.© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 13teCUIf a process blocks before using its quantum, it naturally moves to the blocked state and the process at the head of the ready queue is moved to the running state.If a process doesn’t use its full quantum, it is moved to the end of the ready queue after leaving the blocked state.A Gedanken ExperimentHow long should a quantum be?If it’s too short, most of the system time is spent doing context switches© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 14spent doing context switches.If it’s too long, response time is sacrificed. (In the limit, this turns into non-preemptive scheduling.)A compromise must be made between efficiency and responsiveness.Priority SchedulingEach process is assigned a priority, which is usually just an integer value in a given range.At any instant, the ready process with the highest priority is allowed to run.Pi iti b tti (th h )© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 15Priorities can be static (they never change) or dynamic (they’re adjusted during the process’ lifetime).Priorities may be altered by the system to cause more efficient use of resources or obtain other goals.Processes with identical priorities can be run in a round-robin fashion.Scheduling VariationsRather than have just a single queue that holds all processes, some systems use multiple queues.Each queue holds processes in different © 2008 Stanley A. Wileman, Jr. Operating Systems Slide 16qpcategories