Agenda

• Announcements
• Process Creation from Lecture 2
• CPU Scheduling
• Project 1 - Discrete Event Simulation

Announcements

Process Creation from Lecture 2

CPU Scheduling

CPU scheduling can be done at three different levels:

1. Long-term Scheduling - also known as batch scheduling. Decide which jobs/processes are allowed into the system.
2. Short-term Scheduling - or interactive scheduling. Decide from a collection of ready processes which gets the CPU next.
3. Medium-term Scheduling - or memory scheduling. Decide if/when a process should be "swapped out" or back in based on memory available.

We will discuss primarily short-term scheduling here, though we will discuss all of the algorithms that Tanenbaum splits between batch and interactive scheduling.

A typical process alternates between the need for CPU and the need for I/O service throughout its lifespan. This is called the CPU-I/O burst cycle.

It is this fact that makes multiprogramming essential. When a process needs I/O, it's good to have another process ready to move in and take advantage of the available CPU resource.

The amount of time that it can make use of the CPU is known as its CPU burst time.

A typical distribution of CPU burst times looks like this:

Processes may be categorized as:

The type of processes in the system will affect the performance of scheduling algorithms.

A short-term CPU scheduling decision is needed when a process:

1. switches from a running to a waiting state (non-preemptive)
2. switches from a running to a ready state (preemptive)
3. switches from a waiting to a ready state (preemptive)
4. terminates (non-preemptive)

Goals of a CPU scheduler. (In parens is whether this is a goal of the owners of the system or the users of the system)

Response Time's Relationship to Throughput

First-Come, First-Served (FCFS) Scheduling

As its name suggests, the first process to arrive gets to go first. It is a non-preemptive FIFO system.

Example:

Consider 4 processes P₁, P₂, and P₃ that have burst times of 24, 3, and 3, respectively.

If the processes arrive in the order P₁, P₂, P₃, FCFS will service them in that order. We visualize this with a Gantt Chart:

|---------P1----------|-P2-|-P3-|
0                    24   27   30

Waiting times: P₁ = 0; P₂ = 24; P₃ = 27, Avg: (0+24+27)/(3)=17.

But what if the processes arrive P₂, P₃, P₁?

|-P2-|-P3-|---------P1-----------|
0    3    6                     30

Waiting times: P₁ = 6; P₂ = 0; P₃ = 3, Avg: (6+0+3)/(3)=3.

FCFS characteristics:

Remainder moved to Lecture 4 notes.

Project 1 - Discrete Event Simulation