Nell Dale & John Lewis

(adaptation by Michael Goldwasser and Erin Chambers)

Operating Systems and scheduling

Computing Resources

Computing systems include many resources

Processor(s)

Main Memory

I/O Devices (keyboard, screen, mouse, …)

Storage Devices (harddisk, various drives)

Networking Devices

The Operating System (OS)

Operating system

System software that

manages computer resources, such as memory and input/output devices

provides an interface through which a human can interact with the computer

allows an application program to interact with these other system resources

“The good old days…”

On early computers, a single program was executed at a time.

That program had full control over all of the computer’s resources

A human operator would control access to the computer, prioritizing which job to complete.

Batch Processing

Figure 10.2 In early systems, human operators would organize jobs into batches

Modern Operating Systems

Modern computing systems allow for many different users and programs to coexist in the system at the same time, through a technique known as multiprogramming.

An operating system manages all of a computer’s resources, controlling how they should be shared by the many users and programs which may exist.

Operating System

Figure 10.1
An operating system interacts with many
aspects of a computer system.

Popular Operating Systems

Windows (98, NT, 2000, ME, XP, …)

UNIX

Linux (version of UNIX for PCs)

MacOS (though OS X is Unix based)

Roles of an OS

The various roles of an operating system generally revolve around the idea of “sharing nicely”

An operating system manages resources, and these resources are often shared in one way or another among programs that want to use them

Resource Management

CPU scheduling determines which process in memory is executed by the CPU at any given point

Memory management keeps track of what programs are in memory and where in memory they reside.

Network Communication

File Systems (who can read/write files)

Memory Management

Every time a program starts running, the CPU must determine where to put that program in memory

Remember, memory is small compared to the hard drive!

What happens when we don't leave enough space, or the program is too large to fit?

Single Contiguous MM

There are only two programs in memory

The operating system

The application program

This approach is called single contiguous memory management

Figure 10.4 Main memory divided into two sections

Single Contiguous MM

In concrete terms:

A logical address is simply an integer value relative to the starting point of the program

A physical address is a logical address added to the starting location of the program in main memory

Single Contiguous MM

Figure 10.5 Binding a logical address to a physical one

If A is location 100, and

the application program

is Program 1, then

sum is stored at location

123.

Partition Memory Management

Single contiguous MM has only the OS and one other program in memory at one time

Partition MM has the OS and any number of other programs in memory at one time

There are two schemes for dividing up memory for programs:

Fixed partitions Main memory is divided into a fixed number of partitions into which programs can be loaded

Dymanic partitions Partitions are created as needed to fit the programs waiting to be loaded

Partition Memory Management

Memory is divided into a set of partitions, some empty and some allocated to programs

Base register

A register that holds the beginning address of the current partition (the one that is running)

Bounds register

A register that holds the length of the current partition

Partition Memory Management

Figure 10.6
Address resolution
in partition memory management

Why check?

Partition Selection Algorithms

Which partition should we allocate to a new program?

First fit Allocate program to the first partition big enough to hold it

Best fit Allocated program to the smallest partition big enough to hold it

Worst fit Allocate program to the largest partition big enough to hold it

Can you give a rationale for each?

Partition Selection Algorithms

A: 1000

B: 700

C: 750

D: 1500

E: 300

F: 350

Requests come in for blocks of

the following sizes:

1000, 25, 780, 1600, and 325

What block will be assigned

to each request if the

first-fit algorithm is used?

best-fit algorithm is used?

worst-fig algorithm is used?

(Treat each request as an

independent event)

Processes

Programs on a machine might be executed by the same user, by different users, or started by other applications.

We call an executing program a process.

(actually programs may control several processes)

During its life cycle, a process will need to use varying system resources.

Process Management

Process management is performed by the operating system. For each process, the OS must carefully track its progress, current state, all of its resource usage, etc.

Windows: see the “Task Manager”

Macintosh: see the “Activity Monitor”

Unix/Linux: see “top” command

Activity Monitor

Process Control Block

The OS generally keeps what is called a Process Control Block (PCB) for each active process.

Such a PCB stores all needed information regarding that process.

Process State

Processes come and go. At any given time, a process is in one of these states:

“new” – being created as we speak

“running” – currently using the CPU

“ready” – would use the CPU if offered

“waiting” – even if offered CPU, it would still be waiting for other reasons

“terminated” – completed execution

Process Life Cycle

Figure 10.8 The process life cycle

Sharing the CPU

Though many processes appear to run simultaneously, the CPU can execute only one program at a given time.

The Operating System is in charge of controlling the use of the CPU.

A variety of CPU scheduling policies can be used.

CPU Scheduling

Nonpreemptive scheduling: occurs when the currently executing process gives up the CPU voluntarily.

Preemptive scheduling: occurs when the operating system decides to favor another process, preempting the currently executing process.

With preemptive scheduling, a special operation called an interrupt is used to break the normal flow of control.

Interrupts & Context Switches

The CPU has many registers which are used to store data while a process is running. (e.g. Program Counter, Accumulator)

If a process is about to be interrupted, all of the register contents must be stored in the PCB.

Thus, the contents of the CPU registers can be re-established when the process resumes.

Notice, some CPU time used by the operating system to implement a context switch.

A Real Life Analogy

The Grocery Store

Many people are waiting at the deli. In what order should they be helped?

Many people are waiting to check out. In what order should they be helped?

Once the store starts processing a person, can that process be interrupted and later resumed? What are the implications?

Evaluating a Scheduling Policy

For a specific process, key criteria may be the turnaround time: amount of time between its arrival and its completion.

For the overall system, not so clear what is best criteria. One candidate is average turnaround time.

Potential Scheduling Policies

We will look at a variety of non-preemptive and preemptive scheduling policies discussed in the book.

We go a step further than the text. Specifically, in text’s examples, all processes arrive in system at same time.

We consider jobs which arrive in the system at varying times.

First-Come, First-Served

First policy we consider is “FCFS”

Processes are scheduled in the order in which they arrive in the running state.

FCFS scheduling is nonpreemptive (a new arrival does not effect current job)

First-Come, First-Served

Page 336

940

815

535

215

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

940

0

p5

815

0

p4

535

0

p3

215

0

p2

140

0

p1

Average Turnaround time: 529

First-Come, First-Served

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

0

p1

0



First-Come, First-Served

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

0

p1

0

p1



First-Come, First-Served

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

0

p1

0

p1



40

First-Come, First-Served

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

0

p1

0

p1



50

First-Come, First-Served

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

0

p1

0

140

p1



First-Come, First-Served

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

140

0

p1

0

140

p1



First-Come, First-Served

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

140

0

p1

0

140

p1

p2



First-Come, First-Served

215

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

140

0

p1

0

140

215

p1

p2



First-Come, First-Served

215

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

175

40

p2

140

0

p1

0

140

215

p1

p2



First-Come, First-Served

215

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

175

40

p2

140

0

p1

0

140

215

p1

p2

p3



First-Come, First-Served

215

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

175

40

p2

140

0

p1

0

140

215

p1

p2

p3



300

First-Come, First-Served

215

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

175

40

p2

140

0

p1

0

140

215

p1

p2

p3



315

First-Come, First-Served

535

215

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

175

40

p2

140

0

p1

0

140

215

p1

p2

p3

535



First-Come, First-Served

535

215

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

485

50

p3

175

40

p2

140

0

p1

0

140

215

p1

p2

p3

535



First-Come, First-Served

815

535

215

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

485

50

p3

175

40

p2

140

0

p1

0

140

215

p1

p2

p3

535

815

p4



First-Come, First-Served

815

535

215

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

515

300

p4

485

50

p3

175

40

p2

140

0

p1

0

140

215

p1

p2

p3

535

815

p4



First-Come, First-Served

815

535

215

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

515

300

p4

485

50

p3

175

40

p2

140

0

p1



0

140

215

p1

p2

p3

535

p5

815

p4

First-Come, First-Served

940

815

535

215

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

515

300

p4

485

50

p3

175

40

p2

140

0

p1

0

140

215

p1

p2

p3

535

p5

815

p4

940



First-Come, First-Served

940

815

535

215

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

625

315

p5

515

300

p4

485

50

p3

175

40

p2

140

0

p1

Average Turnaround time: 388

0

140

215

p1

p2

p3

535

p5

815

p4

940



Shortest Job Next (SJN)

When choosing next job to run, look at all processes in the ready state and dispatch the one with the smallest service time.

(assuming we know the service times!)

We consider it as a nonpreemptive algorithm. That is a new job will not be given a chance at the CPU until the current job finishes (even if new job is shorter).

Shortest Job Next

Page 337

200

620

940

75

340

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

200

0

p5

620

0

p4

940

0

p3

75

0

p2

340

0

p1

Average Turnaround time: 435

Shortest Job Next

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

0

p1

0



Shortest Job Next

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

0

p1

0

p1



Shortest Job Next

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

0

p1

0

p1



40

Shortest Job Next

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

0

p1

0

p1



50

Shortest Job Next

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

0

p1

0

140

p1



Shortest Job Next

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

140

0

p1

0

140

p1



Shortest Job Next

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

140

0

p1

0

140

p1

p2



Shortest Job Next

215

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

140

0

p1

0

140

215

p1

p2



Shortest Job Next

215

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

175

40

p2

140

0

p1

0

140

215

p1

p2



Shortest Job Next

215

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

175

40

p2

140

0

p1

0

140

215

p1

p2

p3



Shortest Job Next

215

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

175

40

p2

140

0

p1

0

140

215

p1

p2

p3



300

Shortest Job Next

215

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

175

40

p2

140

0

p1

0

140

215

p1

p2

p3



315

Shortest Job Next

535

215

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

175

40

p2

140

0

p1

0

140

215

p1

p2

p3

535



Shortest Job Next

535

215

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

485

50

p3

175

40

p2

140

0

p1

0

140

215

p1

p2

p3

535



Shortest Job Next

535

215

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

485

50

p3

175

40

p2

140

0

p1

0

140

215

p1

p2

p3

535

p5



Shortest Job Next

660

535

215

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

315

p5

300

p4

485

50

p3

175

40

p2

140

0

p1

0

140

215

p1

p2

p3

535

p5

660



Shortest Job Next

660

535

215

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

345

315

p5

300

p4

485

50

p3

175

40

p2

140

0

p1

0

140

215

p1

p2

p3

535

p5

660



Shortest Job Next

660

535

215

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

345

315

p5

300

p4

485

50

p3

175

40

p2

140

0

p1

0

140

215

p1

p2

p3

535

p5

660

p4



Shortest Job Next

660

940

535

215

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

345

315

p5

300

p4

485

50

p3

175

40

p2

140

0

p1

0

140

215

p1

p2

p3

535

p5

660

p4

940



Shortest Job Next

660

940

535

215

140

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

345

315

p5

640

300

p4

485

50

p3

175

40

p2

140

0

p1

Average Turnaround time: 357

0

140

215

p1

p2

p3

535

p5

660

p4

940

Shortest Remaining Processing Time

SRPT is a preemptive variant of Shortest Job Next. It allows a job to be interrupted if a new job arrives which is even shorter than the remaining processing time of the current job.

Later, when choosing job to dispatch, base on each job’s remaining processing time, rather than the original times.

SRPT example

Completion Time

125

280

320

75

140

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

0

p1

0



SRPT example

Completion Time

125

280

320

75

140

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

0

p1

0

p1



SRPT example

Completion Time

125

280

320

75

100

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

0

p1

0

40

p1



SRPT example

Completion Time

125

280

320

75

100

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

0

p1

0

40

p1



SRPT example

Completion Time

125

280

320

75

100

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

0

p1

0

40

p1

p2



SRPT example

Completion Time

125

280

320

65

100

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

0

p1

0

40

p1

p2



50

SRPT example

115

Completion Time

125

280

320

0

100

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

0

p1

0

40

115

p1

p2



SRPT example

115

Completion Time

125

280

320

0

100

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

75

40

p2

0

p1

0

40

115

p1

p2



SRPT example

115

Completion Time

125

280

320

0

100

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

75

40

p2

0

p1

0

40

115

p1

p2

p1



SRPT example

115

215

Completion Time

125

280

320

0

0

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

75

40

p2

0

p1

0

40

115

215

p1

p2

p1



SRPT example

115

215

Completion Time

125

280

320

0

0

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

75

40

p2

215

0

p1

0

40

115

215

p1

p2

p1



SRPT example

115

215

Completion Time

125

280

320

0

0

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

75

40

p2

215

0

p1

0

40

115

215

p1

p2

p1

p3



SRPT example

115

215

Completion Time

125

280

235

0

0

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

75

40

p2

215

0

p1

0

40

115

215

p1

p2

p1



300

p3

SRPT example

115

215

Completion Time

125

280

220

0

0

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

75

40

p2

215

0

p1

0

40

115

215

p1

p2

p1

315



p3

SRPT example

115

215

Completion Time

125

280

220

0

0

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

75

40

p2

215

0

p1

0

40

115

215

p1

p2

p1

315

p3



SRPT example

115

215

Completion Time

125

280

220

0

0

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

75

40

p2

215

0

p1

0

40

115

215

p1

p2

p1

315

p3

p5



SRPT example

440

115

215

Completion Time

0

280

220

0

0

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

75

40

p2

215

0

p1

0

40

115

215

p1

p2

p1

315

p3

440

p5



SRPT example

440

115

215

Completion Time

0

280

220

0

0

Remaining

Turnaround

Arrival Time

Process

125

315

p5

300

p4

50

p3

75

40

p2

215

0

p1

0

40

115

215

p1

p2

p1

315

p3

440

p5



SRPT example

440

115

215

Completion Time

0

280

220

0

0

Remaining

Turnaround

Arrival Time

Process

125

315

p5

300

p4

50

p3

75

40

p2

215

0

p1

0

40

115

215

p1

p2

p1

315

p3

440

p5

p3



SRPT example

440

660

115

215

Completion Time

0

280

0

0

0

Remaining

Turnaround

Arrival Time

Process

125

315

p5

300

p4

50

p3

75

40

p2

215

0

p1

0

40

115

215

p1

p2

p1

315

p3

440

p5

p3

660



SRPT example

440

660

115

215

Completion Time

0

280

0

0

0

Remaining

Turnaround

Arrival Time

Process

125

315

p5

300

p4

610

50

p3

75

40

p2

215

0

p1

0

40

115

215

p1

p2

p1

315

p3

440

p5

p3

660



SRPT example

440

660

115

215

Completion Time

0

280

0

0

0

Remaining

Turnaround

Arrival Time

Process

125

315

p5

300

p4

610

50

p3

75

40

p2

215

0

p1

0

40

115

215

p1

p2

p1

315

p3

440

p5

p3

660

p4



SRPT example

440

940

660

115

215

Completion Time

0

0

0

0

0

Remaining

Turnaround

Arrival Time

Process

125

315

p5

300

p4

610

50

p3

75

40

p2

215

0

p1

0

40

115

215

p1

p2

p1

315

p3

440

p5

p3

660

p4

940



SRPT example

440

940

660

115

215

Completion Time

0

0

0

0

0

Remaining

Turnaround

Arrival Time

Process

125

315

p5

640

300

p4

610

50

p3

75

40

p2

215

0

p1

Average Turnaround time: 333

0

40

115

215

p1

p2

p1

315

p3

440

p5

p3

660

p4

940



Round Robin

Distributes the processing time (equitably?) among all ready processes

The algorithm uses a particular time slice (or time quantum), which is the amount of time each process receives before being preempted in lieu of another process.

Round Robin
(with time slice of 50)

Page 339

640

920

940

325

515

Completion Time

125

280

320

75

140

Service Time

Turnaround

Arrival Time

Process

640

0

p5

920

0

p4

940

0

p3

325

0

p2

515

0

p1

Average Turnaround time: 668

Completion Time

125

280

320

75

140

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

0

p1

0

Round Robin
(with time slice of 50)



Completion Time

125

280

320

75

140

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

0

p1

0

p1

Round Robin
(with time slice of 50)



Completion Time

125

280

320

75

100

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

0

p1

0

p1

40

Round Robin
(with time slice of 50)



Completion Time

125

280

320

75

90

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

0

p1

0

p1

50

Round Robin
(with time slice of 50)



Completion Time

125

280

320

75

90

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

0

p1

0

p1

50

Round Robin
(with time slice of 50)



Completion Time

125

280

320

25

90

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

0

p1

0

p1

p2

100

Round Robin
(with time slice of 50)



Completion Time

125

280

270

25

90

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

0

p1

0

p1

p2

p3

150

Round Robin
(with time slice of 50)



Completion Time

125

280

270

25

40

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

40

p2

0

p1

0

p1

p2

p3

p1

200

Round Robin
(with time slice of 50)



225

Completion Time

125

280

270

0

40

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

185

40

p2

0

p1

0

p1

p2

p3

p1

225

p2

Round Robin
(with time slice of 50)



225

Completion Time

125

280

220

0

40

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

185

40

p2

0

p1

0

p1

p2

p3

p1

225

p2

p3

275

Round Robin
(with time slice of 50)



225

Completion Time

125

280

220

0

40

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

185

40

p2

0

p1

0

p1

p2

p3

p1

225

p2

p3

275

Round Robin
(with time slice of 50)



p1

225

Completion Time

125

280

220

0

15

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

185

40

p2

0

p1

0

p1

p2

p3

p1

225

p2

p3

Round Robin
(with time slice of 50)



p1

300

225

315

Completion Time

125

280

220

0

0

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

185

40

p2

315

0

p1

0

p1

p2

p3

p1

225

p2

p3

315

p1

Round Robin
(with time slice of 50)



225

315

Completion Time

125

280

220

0

0

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

185

40

p2

315

0

p1

0

p1

p2

p3

p1

225

p2

p3

315

p1

Round Robin
(with time slice of 50)



225

315

Completion Time

125

280

170

0

0

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

185

40

p2

315

0

p1

0

p1

p2

p3

p1

225

p2

p3

315

p1

p3

365

Round Robin
(with time slice of 50)



225

315

Completion Time

125

230

170

0

0

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

185

40

p2

315

0

p1

0

p1

p2

p3

p1

225

p2

p3

315

p1

p3

p4

415

Round Robin
(with time slice of 50)



225

315

Completion Time

75

230

170

0

0

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

185

40

p2

315

0

p1

0

p1

p2

p3

p1

225

p2

p3

315

p1

p3

p4

p5

465

Round Robin
(with time slice of 50)



225

315

Completion Time

75

230

120

0

0

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

185

40

p2

315

0

p1

0

p1

p2

p3

p1

225

p2

p3

315

p1

p3

p4

p5

p3

515

Round Robin
(with time slice of 50)



225

315

Completion Time

75

180

120

0

0

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

185

40

p2

315

0

p1

0

p1

p2

p3

p1

225

p2

p3

315

p1

p3

p4

p5

p3

p4

565

Round Robin
(with time slice of 50)



225

315

Completion Time

25

180

120

0

0

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

185

40

p2

315

0

p1

0

p1

p2

p3

p1

225

p2

p3

315

p1

p3

p4

p5

p3

p4

p5

615

Round Robin
(with time slice of 50)



225

315

Completion Time

25

180

70

0

0

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

185

40

p2

315

0

p1

0

p1

p2

p3

p1

225

p2

p3

315

p1

p3

p4

p5

p3

p4

p5

p3

665

Round Robin
(with time slice of 50)



225

315

Completion Time

25

130

70

0

0

Remaining

Turnaround

Arrival Time

Process

315

p5

300

p4

50

p3

185

40

p2

315

0

p1

0

p1

p2

p3

p1

225

p2

p3

315

p1

p3

p4

p5

p3

p4

p5

p3

p4

715

Round Robin
(with time slice of 50)



740

225

315

Completion Time

0

130

70

0

0

Remaining

Turnaround

Arrival Time

Process

425

315

p5

300

p4

50

p3

185

40

p2

315

0

p1

0

p1

p2

p3

p1

225

p2

p3

315

p1

p3

p4

p5

p3

p4

p5

p3

p4

p5

740

Round Robin
(with time slice of 50)



740

225

315

Completion Time

0

130

20

0

0

Remaining

Turnaround

Arrival Time

Process

425

315

p5

300

p4

50

p3

185

40

p2

315

0

p1

0

p1

p2

p3

p1

225

p2

p3

315

p1

p3

p4

p5

p3

p4

p5

p3

p4

p5

740

p3

790

Round Robin
(with time slice of 50)



740

225

315

Completion Time

0

80

20

0

0

Remaining

Turnaround

Arrival Time

Process

425

315

p5

300

p4

50

p3

185

40

p2

315

0

p1

0

p1

p2

p3

p1

225

p2

p3

315

p1

p3

p4

p5

p3

p4

p5

p3

p4

p5

740

p3

p4

840

Round Robin
(with time slice of 50)



740

860

225

315

Completion Time

0

80

0

0

0

Remaining

Turnaround

Arrival Time

Process

425

315

p5

300

p4

810

50

p3

185

40

p2

315

0

p1

0

p1

p2

p3

p1

225

p2

p3

315

p1

p3

p4

p5

p3

p4

p5

p3

p4

p5

740

p3

p3

p4

860

Round Robin
(with time slice of 50)



740

860

225

315

Completion Time

0

30

0

0

0

Remaining

Turnaround

Arrival Time

Process

425

315

p5

300

p4

810

50

p3

185

40

p2

315

0

p1

0

p1

910

p2

p3

p1

225

p2

p3

315

p1

p3

p4

p5

p3

p4

p5

p3

p4

p5

740

p3

p3

p4

860

p4

Round Robin
(with time slice of 50)



740

940

860

225

315

Completion Time

0

0

0

0

0

Remaining

Turnaround

Arrival Time

Process

425

315

p5

640

300

p4

810

50

p3

185

40

p2

315

0

p1

Average Turnaround time: 475

0

p1

940

p2

p3

p1

225

p2

p3

315

p1

p3

p4

p5

p3

p4

p5

p3

p4

p5

740

p3

p3

p4

860

p4

Round Robin
(with time slice of 50)



p4

Conclusions

What are the relative advantages and	disadvantages of various approaches?

First-Come, First-Served

Shortest Job Next

Shortest Remaining Processing Time

Round Robin

Round Robin (with priorities)

PowerPoint Presentation

Jones & Bartlett Publishers

2002-06-09T13:56:08