What is CPU scheduling? Determining which processes run when there are multiple runnable processes. Why is it important? Because it can have a big effect on resource utilization and the overall performance of the system.

Basic assumptions behind most scheduling algorithms:

· There is a pool of runnable processes contending for the CPU.

· The processes are independent and compete for resources.

· The job of the scheduler is to distribute the scarce resource of the CPU to the different processes “fairly'’ (according to some definition of fairness) and in a way that optimizes some performance criteria.

How do processes behave? First, CPU/IO burst cycle. A process will run for a while (the CPU burst), perform some IO (the IO burst), then run for a while more (the next CPU burst). How long between IO operations? Depends on the process.

· IO Bound processes: processes that perform lots of IO operations. Each IO operation is followed by a short CPU burst to process the IO, then more IO happens.

· CPU bound processes: processes that perform lots of computation and do little IO. Tend to have a few long CPU bursts.

One of the things a scheduler will typically do is switch the CPU to another process when one process does IO. Why? The IO will take a long time, and don’t want to leave the CPU idle while wait for the IO to finish.

What are possible process states?

· Running - process is running on CPU.

· Ready - ready to run, but not actually running on the CPU.

· Waiting - waiting for some event like IO to happen.

· When do scheduling decisions take place? When does CPU choose which process to run? Are a variety of possibilities:

· When process switches from running to waiting. Could be because of IO request, because wait for child to terminate, or wait for synchronization operation (like lock acquisition) to complete.

· When process switches from running to ready - on completion of interrupt handler, for example. Common example of interrupt handler - timer interrupt in interactive systems. If scheduler switches processes in this case, it has preempted the running process. Another common case interrupt handler is the IO completion handler.

· When process switches from waiting to ready state (on completion of IO or acquisition of a lock, for example).

· When a process terminates.