Big Data -Part -1

Operating Systems
 Operating
system
OS Road Map
Concepts
+
Process
synchronization
+
Processes& +
Threads

+
CPU
Scheduling

+
Memory
©Ahmed Hagag Operating Systems Management
2
 Reference
Computer Operating System Concepts
• Author: Silberschatz
• Publisher: Wiley
• Edition: Sixth
• ISBN: 0471250600
 (OS)
System Concepts
• Operating System
• Single processor
• Multiprocessor Systems
• Distributed Systems
• Clustered System
• Real -Time Systems
• Handheld Systems
 Operating System
• What is an Operating System?
• It acts as an intermediary between a user and his hardware
• Operating system objective
• Executes users programs
• Solves its problems
 Operating System
• It controls and coordinates the use of the HW among the various
application programs for the various users
• It manages and allocates resources
• It controls the execution of user programs and operations of I/O devices
• Kernel – the one program running at all times
Mainframe Systems
• Reduce setup time by batching similar jobs
• Automatic job sequencing
• Automatically transfers control from one job to another.
• First rudimentary operating system
 Single processor
• Memory Layout for a Simple Batch System
 Single processor
• Multi-programmed Batch Systems
• Several jobs are kept in main memory at the same time, and the CPU is
multiplexed among them
• OS features needed
• I/O routine supplied by the system
• Memory management
• The system must allocate the memory
to several jobs
• CPU scheduling
• The system must choose among
several jobs ready to run
 Single processor

• Time-Sharing Systems (Interactive Computing )

• The CPU is multiplexed among several jobs that are kept in memory and on disk

• The CPU is allocated to a job only if the job is in memory

• A job swapped in and out of memory to the disk

• On-line communication between the user and the system is provided

• When the operating system finishes the execution of one command, it seeks the next “control
statement” from the user’s keyboard
 Parallel Systems
• Systems with more than one CPU in close communication
• Also known as multiprocessor systems
• Tightly coupled system
• processors share memory and a clock; communication usually takes place
through the shared memory
• Advantages of parallel system:
• Increased throughput
• Economical
• Increased reliability
• graceful degradation
Distributed Systems
• Distribute the computation among several physical processors
• Loosely coupled system
• Each processor has its own local memory
• processors communicate with one another through various communications
lines, such as high-speed buses or telephone lines
• Advantages of distributed systems
• Resources Sharing
• Computation speed up
• Reliability
Distributed Systems Cont’d
• Requires networking infrastructure
• Local area networks (LAN) or Wide area networks (WAN)
• May be either client-server or peer-to-peer systems
Clustered Systems
• Clustering allows two or more systems to share

storage

• Provides high reliability

• Asymmetric clustering: one server runs the

application or applications while other servers

standby

• Symmetric clustering: all N hosts are running

the application or applications

Real-Time Systems
• Often used as a control device in a dedicated application such as
controlling scientific experiments, medical imaging systems, industrial
control systems, and some display systems
• Well-defined fixed-time constraints
• Real-Time systems may be either hard or soft real-time
Real-Time Systems Cont’d
• Hard real-time:
• Secondary storage limited or absent, data stored in short term memory, or
read-only memory (ROM)
• Conflicts with time-sharing systems, not supported by general-purpose
operating systems
• Soft real-time
• Limited utility in industrial control of robotics
• Integrate-able with time-share systems
• Useful in applications (multimedia, virtual reality) requiring tight response
times
 Handheld Systems
• Personal Digital Assistants (PDAs)
• Cellular telephones
• Issues:
• Limited memory
• Slow processors
• Small display screens

Note OS before android

https://www.zdnet.com/article/android-before-android-the-long-strange-history-of-symbian-and-why-it-
matters-for-nokias-future/
Migration of Operating-System Concepts and
Features
 What Operating Systems Do
• OS is a resource allocator
➢ Manages all resources.
➢ Decides between conflicting requests for efficient and fair resource
use.

• OS is a control program
➢ Controls execution of programs to prevent errors and improper
use of the computer.

©Ahmed Hagag Operating Systems 19

 Computer System Terms

Computer Startup (1/2)

• bootstrap program is loaded at power-up or reboot
➢ Typically stored in ROM or electrically erasable programmable read-only
memory (EPROM), generally known as firmware.
➢ Initializes all aspects of system.
➢ Loads operating system kernel and starts execution.

©Ahmed Hagag Operating Systems 20

 Computer System Organization (2/3)
Computer Startup (2/2)

©Ahmed Hagag Operating Systems 21

 Computer System Terms
Interrupts (1/2)
• The occurrence of an event is usually signaled by an
interrupt from either the hardware or the software.
➢ Hardware may trigger an interrupt at any time by sending a signal to
the CPU, usually by way of the system bus.
➢ Software may trigger an interrupt by executing a special operation
called a system call (also called a monitor call).

• Interrupts are an important part of a computer architecture. Each

computer design has its own interrupt mechanism, but several
functions are common.
©Ahmed Hagag Operating Systems 22
 Computer System Organization
Interrupts (2/2)
• Interrupt transfers control to the interrupt service routine generally, through
the interrupt vector, which contains the addresses of all the service
routines.
• Interrupt architecture must save the address of the interrupted instruction.
• A trap or exception is a software-generated interrupt caused either by an
error or a user request.
• An operating system is interrupt driven.

©Ahmed Hagag Operating Systems 23

 Operating system
Processes

©Ahmed Hagag Operating Systems 24

 Process Concept

Program vs. Process

• A program is a passive entity such as the file that contains the list of
instructions stored on a disk always referred to as an executable file.
• A program becomes a process when an executable file is loaded into
the memory and then becomes an active entity.

©Ahmed Hagag Operating Systems 25

 Process Concept
• The fundamental task of any operating system is the
process management.
• Processes include not only a text but also include a set of resources such as
open files and pending signals. Processes also contain internal kernel data,
processor state, an address space, and a data section.

©Ahmed Hagag Operating Systems 26

 Process Concept
• OS must allocate resources to processes, enable sharing of information,
protect resources, and enable the synchronization among processes.

©Ahmed Hagag Operating Systems 27

 Process Elements

• Segments of a process represents the following

• components:
➢ Text Section: the program code. This is typically read-only, and might be shared by a
number of processes.
➢ Data Section: containing global variables.
➢ Heap: containing memory dynamically allocated during run time.
➢ Stack: containing temporary data.
• Function parameters, return addresses, local variables.

©Ahmed Hagag Operating Systems 28

 Process Concept
• Process in Memory

©Ahmed Hagag Operating Systems 29

 Process Control Block (PCB)

• For better control of processes, operating

systems need to consider their
dynamic behaviors.
• Each process is represented in the OS by a
Process Control Block (PCB).

©Ahmed Hagag Operating Systems 30

 Process Control Block (PCB)
• Process Control Block (PCB) (1/3)
➢ Process identification information
▪ Process identifier: numeric identifiers represent the
unique process identifier
▪ User identifier: the user who is responsible for the job).
▪ Identifier of the parent process that created this process.

©Ahmed Hagag Operating Systems 31

 Process Control Block (PCB)

• Process Control Block (PCB) (2/3)

➢ Processor state Information
▪ Process state – running, waiting, etc
➢ Program counter
▪ location of instruction to next execute
➢ CPU registers
▪ contents of all process-centric registers

©Ahmed Hagag Operating Systems 32

 Process Control Block (PCB)
• Process Control Block (PCB) (3/3)
➢ CPU scheduling information
▪ priorities, scheduling queue pointers
➢ Memory-management information
▪ memory allocated to the process
➢ Accounting information
▪ CPU used, clock time elapsed since start, time limits
➢ I/O status information
▪ I/O devices allocated to process, list of open files
©Ahmed Hagag Operating Systems 33
 Process State

• As a process executes, it changes state

➢ new: The process is being created
➢ running: Instructions are being executed
➢ waiting: The process is waiting for some event to occur
➢ ready: The process is waiting to be assigned to a processor
➢ terminated: The process has finished execution

©Ahmed Hagag Operating Systems 34

 Process State
• Diagram of Process State

©Ahmed Hagag Operating Systems 35

 Process State

©Ahmed Hagag Operating Systems 36

 Process State

©Ahmed Hagag Operating Systems 37

 Process State

©Ahmed Hagag Operating Systems 38

 Process State

©Ahmed Hagag Operating Systems 39

 Process State

©Ahmed Hagag Operating Systems 40

 Process State

©Ahmed Hagag Operating Systems 41

 CPU Switch From Process to Process

©Ahmed Hagag Operating Systems 42

 Process Scheduling
• Job queue – set of all processes in the system
• Ready queue – set of all processes residing in main memory,
ready and waiting to execute
• Device queues – set of processes waiting for an I/O device
• Processes migrate among the various queues

©Ahmed Hagag Operating Systems 43

 Process Scheduling

©Ahmed Hagag Operating Systems 44

 Process Scheduling
• Short-term scheduler (or CPU scheduler)
➢ Selects which process should be executed next and allocates CPU.
➢ Invoked frequently (milliseconds) →(must be fast).
• Long-term scheduler (or job scheduler)
➢ Selects which processes should be brought into the ready queue.
➢ Invoked infrequently (seconds, minutes) →(may be slow).
➢ Controls the degree of multiprogramming.

©Ahmed Hagag Operating Systems 45

 Process Scheduling
Medium-term scheduler
➢ Can be added if degree of multiple programming needs to decrease
➢ Remove process from memory, store on disk, bring back in from disk to
continue execution: swapping

©Ahmed Hagag Operating Systems 46

 Operating systems
Threads

©Ahmed Hagag Operating Systems 47

 Introduction

• A thread is a basic unit of CPU utilization; it comprises a thread ID, a

program counter, a register set, and a stack.

• It shares with other threads belonging to the same process its code section,

data section, and other operating-system resources, such as open files and

signals.
©Ahmed Hagag Operating Systems 48
 Introduction

• Let's say, for example, a program is not capable of drawing pictures while

reading keystrokes. The program must give its full attention to the

keyboard input lacking the ability to handle more than one event at a time.

• The ideal solution to this problem is the seamless execution of two or more

sections of a program at the same time. Threads allows us to do this.

©Ahmed Hagag Operating Systems 49

 Introduction

©Ahmed Hagag Operating Systems 50

 Introduction
• Most software applications that run on modern
computers are multithreaded.
• An application typically is implemented as a
separate process with several threads of control.
➢ A web browser might have one thread display images or text while another
thread retrieves data from the network, for example.
➢ A word processor may have a thread for displaying graphics, another thread for
responding to keystrokes from the user, and a third thread for performing
spelling and grammar checking in the background.

©Ahmed Hagag Operating Systems 51

 Introduction
• Multithreaded server architecture

©Ahmed Hagag Operating Systems 52

Operating Systems
CPU Scheduling
 Operating system
CPU Scheduling

©Ahmed Hagag Operating Systems 54

 Basic Concepts
• CPU scheduling is the central in multi-programming system.

• Maximum CPU utilization obtained with

multiprogramming (prevent CPU from being idle).
• Processes residing in the main memory is selected by the Scheduler
that is:
➢ Concerned with deciding a policy about which process is to be
selected.
➢ Process selection based on a scheduling algorithm.

©Ahmed Hagag Operating Systems 55

 Basic Concepts

©Ahmed Hagag Operating Systems 56

 Basic Concepts

©Ahmed Hagag Operating Systems 57

 Basic Concepts
• Process execution consists of a cycle of
CPU execution and I/O wait.
• Processes alternate between these two
states. Process execution begins with a
CPU burst. That is followed by an I/O
burst, which is followed by another
CPU burst, then another I/O burst, and
so on.
• CPU bursts vary greatly from process to
process and from computer to computer.

©Ahmed Hagag Operating Systems 58

 Basic Concepts

Schedulers
• Long-term scheduler chooses some of them to go to memory
(ready queue).
• Then, short-term scheduler (or CPU scheduler) chooses from
ready queue a job to run on CPU.
• Medium-term scheduler may move (swap) some partially-
executed jobs from memory to disk (to enhance performance).

©Ahmed Hagag Operating Systems 59

 Basic Concepts

CPU Scheduler
• Whenever the CPU becomes idle, the operating system must select
one of the processes in the ready queue to be executed. The selection
process is carried out by the short-term scheduler, or CPU
scheduler.

©Ahmed Hagag Operating Systems 60

 Basic Concepts

CPU scheduling decisions may take place when a process:

1. Switches from running to waiting state
2. Switches from running to ready state
3. Switches from waiting to ready
4. Terminates

©Ahmed Hagag Operating Systems 61

 Basic Concepts
Scheduling can be
• Non-preemptive
➢ Once a process is allocated the CPU, it does not leave
until terminate.
• Preemptive
➢ OS can force (preempt) a process from CPU at anytime.
✓ Say, to allocate CPU to another higher-priority process.

©Ahmed Hagag Operating Systems 62

 Basic Concepts

Non-preemptive and Preemptive

Which is harder to implement? and why?

©Ahmed Hagag Operating Systems 63

 Basic Concepts

Non-preemptive and Preemptive

• Preemptive is harder: Need to maintain consistency of data shared
between processes, and more importantly, kernel data structures (e.g., I/O
queues).

©Ahmed Hagag Operating Systems 64

 Basic Concepts
Dispatcher
• Dispatcher module gives control of the CPU to the process
selected by the short-term scheduler; this involves:
➢ Switching context.
➢ Switching to user mode.
➢ Jumping to the proper location in the user program to restart that
program.
• Dispatch latency – time it takes for the dispatcher to stop one
process and start another running.

©Ahmed Hagag Operating Systems 65

 Basic Concepts
Dispatcher

©Ahmed Hagag Operating Systems 66

 Basic Concepts
Dispatcher

©Ahmed Hagag Operating Systems 67

 Basic Concepts
Dispatcher

©Ahmed Hagag Operating Systems 68

 Basic Concepts
Dispatcher

©Ahmed Hagag Operating Systems 69

 Basic Concepts
• CPU utilization – keep the CPU as busy as possible.
• Throughput – #of processes that complete their execution per time unit.
• Turnaround time – amount of time to execute a particular process. (time from
submission to termination)
• Waiting time – amount of time a process has been waiting in the ready queue.
• Response time – amount of time it takes from when a request was submitted until the
first response is produced, not output.

©Ahmed Hagag Operating Systems 70

 Scheduling Criteria
Scheduling Algorithm Optimization Criteria

• Max CPU utilization.

• Max throughput.
• Min turnaround time.
• Min waiting time.
• Min response time.

©Ahmed Hagag Operating Systems 71

 Scheduling Algorithms
• There are many different CPU-scheduling algorithms:
1. First Come, First Served (FCFS).
2. Shortest Job First (SJF).
➢ Preemptive SJF.
➢ Non-Preemptive SJF.
3. Priority.
4. Round Robin.
5. Multilevel queues.

©Ahmed Hagag Operating Systems 72

 Scheduling Algorithms
1. First-Come, First-Served (FCFS) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:

Note: A process may have many CPU bursts, but in the following
examples we show only one for simplicity.

©Ahmed Hagag Operating Systems 73

 Scheduling Algorithms
1. First-Come, First-Served (FCFS) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:

P1
0

©Ahmed Hagag Operating Systems 74

 Scheduling Algorithms
1. First-Come, First-Served (FCFS) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:

P1
0

©Ahmed Hagag Operating Systems 75

 Scheduling Algorithms
1. First-Come, First-Served (FCFS) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:

P1
0

©Ahmed Hagag Operating Systems 76

 Scheduling Algorithms
1. First-Come, First-Served (FCFS) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:

P1
0
Waiting Time
𝑷𝟏 𝑷𝟐 𝑷𝟑

©Ahmed Hagag Operating Systems 77

 Scheduling Algorithms
1. First-Come, First-Served (FCFS) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:

P1
0
Waiting Time
𝑷𝟏 𝑷𝟐 𝑷𝟑
0 24 27

Average waiting time: (0 + 24 + 27)/3 = 17

©Ahmed Hagag Operating Systems 78
 Scheduling Algorithms
1. First-Come, First-Served (FCFS) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:

P1
0
Turnaround Time
𝑷𝟏 𝑷𝟐 𝑷𝟑

©Ahmed Hagag Operating Systems 79

 Scheduling Algorithms
1. First-Come, First-Served (FCFS) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:

P1
0
Turnaround Time
𝑷𝟏 𝑷𝟐 𝑷𝟑
24 27 30

Average turnaround time: (24 + 27 + 30)/3 = 27

©Ahmed Hagag Operating Systems 80
 Scheduling Algorithms
1. First-Come, First-Served (FCFS) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:

P1
0
Response Time
𝑷𝟏 𝑷𝟐 𝑷𝟑

©Ahmed Hagag Operating Systems 81

 Scheduling Algorithms
1. First-Come, First-Served (FCFS) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:

P1
0
Response Time
𝑷𝟏 𝑷𝟐 𝑷𝟑
0 24 27

Average response time: (0 + 24 + 27)/3 = 17

©Ahmed Hagag Operating Systems 82
 Scheduling Algorithms
1. First-Come, First-Served (FCFS) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P2 , P3 , P1
The Gantt Chart for the schedule is:

©Ahmed Hagag Operating Systems 83

 Scheduling Algorithms
1. First-Come, First-Served (FCFS) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P2 , P3 , P1
The Gantt Chart for the schedule is:

P2 P3 P
0

©Ahmed Hagag Operating Systems 84

 Scheduling Algorithms
1. First-Come, First-Served (FCFS) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P2 , P3 , P1
The Gantt Chart for the schedule is:

P2 P3 P
0

©Ahmed Hagag Operating Systems 85

 Scheduling Algorithms
1. First-Come, First-Served (FCFS) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P2 , P3 , P1
The Gantt Chart for the schedule is:

P2 P3 P
0

©Ahmed Hagag Operating Systems 86

 Scheduling Algorithms
1. First-Come, First-Served (FCFS) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P2 , P3 , P1
The Gantt Chart for the schedule is:

P2 P3 P
0

Waiting Time
𝑷𝟏 𝑷𝟐 𝑷𝟑

©Ahmed Hagag Operating Systems 87

 Scheduling Algorithms
1. First-Come, First-Served (FCFS) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P2 , P3 , P1
The Gantt Chart for the schedule is:

P2 P3 P
0

Waiting Time
𝑷𝟏 𝑷𝟐 𝑷𝟑
6 0 3

Average waiting time: (6 + 0 + 3)/3 = 3

©Ahmed Hagag Operating Systems 88

 Scheduling Algorithms
1. First-Come, First-Served (FCFS) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P2 , P3 , P1
The Gantt Chart for the schedule is:

P2 P3 P
0

Turnaround Time
𝑷𝟏 𝑷𝟐 𝑷𝟑

©Ahmed Hagag Operating Systems 89

 Scheduling Algorithms
1. First-Come, First-Served (FCFS) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P2 , P3 , P1
The Gantt Chart for the schedule is:

P2 P3 P
0

Turnaround Time
𝑷𝟏 𝑷𝟐 𝑷𝟑
30 3 6

Average turnaround time: (30 + 3 + 6)/3 = 13

©Ahmed Hagag Operating Systems 90
 Scheduling Algorithms
1. First-Come, First-Served (FCFS) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P2 , P3 , P1
The Gantt Chart for the schedule is:

P2 P3 P
0

Response Time
𝑷𝟏 𝑷𝟐 𝑷𝟑

©Ahmed Hagag Operating Systems 91

 Scheduling Algorithms
1. First-Come, First-Served (FCFS) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P2 , P3 , P1
The Gantt Chart for the schedule is:

P2 P3 P
0

Response Time
𝑷𝟏 𝑷𝟐 𝑷𝟑
6 0 3

Average response time: (6 + 0 + 3)/3 = 3

©Ahmed Hagag Operating Systems 92
 Scheduling Algorithms

1. First-Come, First-Served (FCFS) Scheduling

• FCFS is fair in the formal sense or human sense of
fairness.
• but it is unfair in the sense that long jobs take priority
over short jobs and unimportant jobs make important
jobs wait.
• One of the major drawbacks of this scheme is that the
waiting time and the average turnaround time is often
quite long.
©Ahmed Hagag Operating Systems 93
 Scheduling Algorithms
2. Shortest-Job-First (SJF) Scheduling
• Associate with each process the length of its next CPU
burst.
➢ Use these lengths to schedule the process with the
shortest time.
• SJF is optimal – gives minimum average waiting time
for a given set of processes.
➢ The difficulty is knowing the length of the next CPU
request.
➢ Could ask the user.

©Ahmed Hagag Operating Systems 94

 Scheduling Algorithms
2.1 Shortest-Job-First (SJF) Scheduling
Process Burst Time
P1 6
P2 8
P3 7
P4 3
SJF scheduling chart

©Ahmed Hagag Operating Systems 95

 Scheduling Algorithms
2.1 Shortest-Job-First (SJF) Scheduling
Process Burst Time
P1 6
P2 8
P3 7
P4 3
SJF scheduling chart

P4 P1 P3 P2
0 3 9 16 24

©Ahmed Hagag Operating Systems 96

 Scheduling Algorithms
2.1 Shortest-Job-First (SJF) Scheduling
Process Burst Time
P1 6
P2 8
P3 7
P4 3
SJF scheduling chart

P4 P1 P3 P2
0 3 9 16 24

©Ahmed Hagag Operating Systems 97

 Scheduling Algorithms
2.1 Shortest-Job-First (SJF) Scheduling
Process Burst Time
P1 6
P2 8
P3 7
P4 3
SJF scheduling chart

P4 P1 P3 P2
0 3 9 16 24

©Ahmed Hagag Operating Systems 98

 Scheduling Algorithms
2.1 Shortest-Job-First (SJF) Scheduling
Process Burst Time
P1 6
P2 8
P3 7
P4 3
SJF scheduling chart

P4 P1 P3 P2
0 3 9 16 24

©Ahmed Hagag Operating Systems 99

 Scheduling Algorithms
2.1 Shortest-Job-First (SJF) Scheduling
Process Burst Time
P1 6
P2 8
P3 7
P4 3
SJF scheduling chart

P4 P1 P3 P2
0 3 9 16 24

Waiting Time
𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒

©Ahmed Hagag Operating Systems 100

 Scheduling Algorithms
2.1 Shortest-Job-First (SJF) Scheduling
Process Burst Time
P1 6
P2 8
P3 7
P4 3
SJF scheduling chart

P4 P1 P3 P2
0 3 9 16 24

Waiting Time
𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒
3 16 9 0

Average waiting time: (3 + 16 + 9 + 0)/4 = 7

©Ahmed Hagag Operating Systems 101

 Scheduling Algorithms
2.1 Shortest-Job-First (SJF) Scheduling
Process Burst Time
P1 6
P2 8
P3 7
P4 3
SJF scheduling chart

P4 P1 P3 P2
0 3 9 16 24

Turnaround Time
𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒

©Ahmed Hagag Operating Systems 102

 Scheduling Algorithms
2.1 Shortest-Job-First (SJF) Scheduling
Process Burst Time
P1 6
P2 8
P3 7
P4 3
SJF scheduling chart

P4 P1 P3 P2
0 3 9 16 24

Turnaround Time
𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒
9 24 16 3

Average Turnaround time: (9 + 24 + 16 + 3)/4 = 13

©Ahmed Hagag Operating Systems 103

 Scheduling Algorithms
2.1 Shortest-Job-First (SJF) Scheduling
Process Burst Time
P1 6
P2 8
P3 7
P4 3
SJF scheduling chart

P4 P1 P3 P2
0 3 9 16 24

Response Time
𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒

©Ahmed Hagag Operating Systems 104

 Scheduling Algorithms
2.1 Shortest-Job-First (SJF) Scheduling
Process Burst Time
P1 6
P2 8
P3 7
P4 3
SJF scheduling chart

P4 P1 P3 P2
0 3 9 16 24

Response Time
𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒
3 16 9 0

Average Response time: (3 + 16 + 9 + 0)/4 = 7

©Ahmed Hagag Operating Systems 105

 Scheduling Algorithms
2.1 Shortest-Job-First (SJF) (Non-Preemptive SJF )
Now we add the concepts of varying arrival times and preemption to the
analysis
Process Arrival Time Burst Time
P1 0 1
P2 1 4
P3 2 7
P4 3 5
Non-Preemptive SJF Gantt Chart

©Ahmed Hagag Operating Systems 106

 Scheduling Algorithms
2.1 Shortest-Job-First (SJF) (Non-Preemptive SJF )
Now we add the concepts of varying arrival times and preemption to the
analysis
Process Arrival Time Burst Time
P1 0 1
P2 1 4
P3 2 7
P4 3 5
Non-Preemptive SJF Gantt Chart

P1 P2 P4 P1 P3
0 1 5 10 17 26

©Ahmed Hagag Operating Systems 107

 Scheduling Algorithms
2.1 Shortest-Job-First (SJF) (Non-Preemptive SJF )
Now we add the concepts of varying arrival times and preemption to the
analysis
Process Arrival Time Burst Time
P1 0 1
P2 1 4
P3 2 7
P4 3 5
Non-Preemptive SJF Gantt Chart

P1 P2 P4 P1
P3
0 1 5 10 17 26

©Ahmed Hagag Operating Systems 108

 Scheduling Algorithms
2.1 Shortest-Job-First (SJF) (Non-Preemptive SJF )
Now we add the concepts of varying arrival times and preemption to the
analysis
Process Arrival Time Burst Time
P1 0 1
P2 1 4
P3 2 7
P4 3 5
Non-Preemptive SJF Gantt Chart

P1 P2 P4 P1 P3
0 1 5 10 17
2
6

©Ahmed Hagag Operating Systems 109

 Scheduling Algorithms
2.1 Shortest-Job-First (SJF) (Non-Preemptive SJF )
Now we add the concepts of varying arrival times and preemption to the
analysis
Process Arrival Time Burst Time
P1 0 1
P2 1 4
P3 2 7
P4 3 5
Non-Preemptive SJF Gantt Chart

©Ahmed Hagag Operating Systems 110

 Scheduling Algorithms
2.1 Shortest-Job-First (SJF) (Non-Preemptive SJF )
Now we add the concepts of varying arrival times and preemption to the
analysis
Process Arrival Time Burst Time
P1 0 1
P2 1 4
P3 2 7
P4 3 5
Non-Preemptive SJF Gantt Chart
Waiting Time
𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒

©Ahmed Hagag Operating Systems 111

 Scheduling Algorithms
2.1 Shortest-Job-First (SJF) (Non-Preemptive SJF )
Now we add the concepts of varying arrival times and preemption to the
analysis
Process Arrival Time Burst Time
P1 0 1
P2 1 4
P3 2 7
P4 3 5
Non-Preemptive SJF Gantt Chart
Waiting Time
𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒
(0 − 0) (1 − 1) (10 − 2) (5 − 3)

Average waiting time: (0 + 0 + 8 + 2)/4 = 2.5 msec

©Ahmed Hagag Operating Systems 112

 Scheduling Algorithms
2.1 Shortest-Job-First (SJF) (Non-Preemptive SJF )
Now we add the concepts of varying arrival times and preemption to the
analysis
Process Arrival Time Burst Time
P1 0 1
P2 1 4
P3 2 7
P4 3 5
Non-Preemptive SJF Gantt Chart
Turnaround Time
𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒

©Ahmed Hagag Operating Systems 113

 Scheduling Algorithms
2.1 Shortest-Job-First (SJF) (Non-Preemptive SJF )
Now we add the concepts of varying arrival times and preemption to the
analysis
Process Arrival Time Burst Time
P1 0 1
P2 1 4
P3 2 7
P4 3 5
Non-Preemptive SJF Gantt Chart
Turnaround Time
𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒
(1 − 0) (5 − 1) (17 − 2) (10 − 3)

Average Turnaround time: (1 + 4 + 15 + 7)/4 = 6.75 msec

©Ahmed Hagag Operating Systems 114

 Scheduling Algorithms
2.1 Shortest-Job-First (SJF) (Non-Preemptive SJF )
Now we add the concepts of varying arrival times and preemption to the
analysis
Process Arrival Time Burst Time
P1 0 1
P2 1 4
P3 2 7
P4 3 5
Non-Preemptive SJF Gantt Chart
Response Time
𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒

©Ahmed Hagag Operating Systems 115

 Scheduling Algorithms
2.1 Shortest-Job-First (SJF) (Non-Preemptive SJF )
Now we add the concepts of varying arrival times and preemption to the
analysis
Process Arrival Time Burst Time
P1 0 1
P2 1 4
P3 2 7
P4 3 5
Non-Preemptive SJF Gantt Chart
Response Time
𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒
(0 − 0) (1 − 1) (10 − 2) (5 − 3)

Average Response time: (0 + 0 + 8 + 2)/4 = 2.5 msec

©Ahmed Hagag Operating Systems 116

 Scheduling Algorithms
Determining Length of Next CPU Burst
Can only estimate the length – should be similar to the previous one
Then pick process with shortest predicted next CPU burst

Can be done by using the length of previous CPU bursts, using exponential
averaging
1. t n = actual length of n th CPU burst

2.n+1 = predicted value for the next CPU burst

3. ,0    1
4. Define :  n=1 =  t n + (1− )n.

Commonly, set to½

Preemptive version called shortest-remaining-time-first

©Ahmed Hagag Operating Systems 117

 Scheduling Algorithms
Prediction of the Length of the Next CPU Burst

©Ahmed Hagag Operating Systems 118

 Scheduling Algorithms
2.2 Shortest-remaining-time-first (Preemptive SJF )
Now we add the concepts of varying arrival times and preemption to the
analysis
Process Arrival Time Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5
Preemptive SJF Gantt Chart

©Ahmed Hagag Operating Systems 119

 Scheduling Algorithms
2.2 Shortest-remaining-time-first (Preemptive SJF )
Now we add the concepts of varying arrival times and preemption to the
analysis
Process Arrival Time Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5 0 ms
Preemptive SJF Gantt Chart

©Ahmed Hagag Operating Systems 120

 Scheduling Algorithms
2.2 Shortest-remaining-time-first (Preemptive SJF )
Now we add the concepts of varying arrival times and preemption to the
analysis
Process Arrival Time Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5 0 ms
Preemptive SJF Gantt Chart

P1 P2 P4 P1 P3
0 1 5 10 17 26

©Ahmed Hagag Operating Systems 121

 Scheduling Algorithms
2.2 Shortest-remaining-time-first (Preemptive SJF )
Now we add the concepts of varying arrival times and preemption to the
analysis
Process Arrival Time Burst Time
P1 0 8 7
P2 1 4
P3 2 9
P4 3 5 1 ms
Preemptive SJF Gantt Chart

P1 P2 P4 P1 P3
0 1 5 10 17 26

©Ahmed Hagag Operating Systems 122

 Scheduling Algorithms
2.2 Shortest-remaining-time-first (Preemptive SJF )
Now we add the concepts of varying arrival times and preemption to the
analysis
Process Arrival Time Burst Time
P1 0 8 7
P2 1 4 3
P3 2 9
P4 3 5 2 ms
Preemptive SJF Gantt Chart

P1 P2 P4 P1 P3
0 1 2 3 5 10 17
26

©Ahmed Hagag Operating Systems 123

 Scheduling Algorithms
2.2 Shortest-remaining-time-first (Preemptive SJF )
Now we add the concepts of varying arrival times and preemption to the
analysis
Process Arrival Time Burst Time
P1 0 8 7
P2 1 4 3 2
P3 2 9
P4 3 5 3 ms
Preemptive SJF Gantt Chart

P1 P2 P4 P1
P3
0 1 2 3 5 10 17 26

©Ahmed Hagag Operating Systems 124

 Scheduling Algorithms
2.2 Shortest-remaining-time-first (Preemptive SJF )
Now we add the concepts of varying arrival times and preemption to the
analysis
Process Arrival Time Burst Time
P1 0 8 7
P2 1 4 3 2
P3 2 9
P4 3 5 3 ms
Preemptive SJF Gantt Chart

P1 P2 P4 P1
P3
0 1 2 3 5 10 17 26

©Ahmed Hagag Operating Systems 125

 Scheduling Algorithms
2.2 Shortest-remaining-time-first (Preemptive SJF )
Now we add the concepts of varying arrival times and preemption to the
analysis
Process Arrival Time Burst Time
P1 0 8 7
P2 1 4 3 2
P3 2 9
P4 3 5 5 ms
Preemptive SJF Gantt Chart

P1 P2 P4 P1
P3
0 1 5 10 17 26

©Ahmed Hagag Operating Systems 126

 Scheduling Algorithms
2.2 Shortest-remaining-time-first (Preemptive SJF )
Now we add the concepts of varying arrival times and preemption to the
analysis
Process Arrival Time Burst Time
P1 0 8 7
P2 1 4 3 2
P3 2 9
P4 3 5 10 ms
Preemptive SJF Gantt Chart

P1 P2 P4 P1 P3
0 1 5 10 17
2
6

©Ahmed Hagag Operating Systems 127

 Scheduling Algorithms
2.2 Shortest-remaining-time-first (Preemptive SJF )
Now we add the concepts of varying arrival times and preemption to the
analysis
Process Arrival Time Burst Time
P1 0 8 7
P2 1 4 3 2
P3 2 9
P4 3 5 17 ms
Preemptive SJF Gantt Chart

P1 P2 P4 P1 P
3
0 1 5 10 17 26

©Ahmed Hagag Operating Systems 128

 Scheduling Algorithms
2.2 Shortest-remaining-time-first (Preemptive SJF )
Now we add the concepts of varying arrival times and preemption to the
analysis
Process Arrival Time Burst Time
P1 0 8 7
P2 1 4 3 2
P3 2 9
P4 3 5 26 ms
Preemptive SJF Gantt Chart

P1 P2 P4 P1 P3
0 1 5 10 17 26

©Ahmed Hagag Operating Systems 129

 Scheduling Algorithms
2.2 Shortest-remaining-time-first (Preemptive SJF )
Process Arrival Time Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5
Preemptive SJF Gantt Chart

P1 P2 P4 P1 P3
0 1 5 10 17 26

Waiting Time
𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒

©Ahmed Hagag Operating Systems 130

 Scheduling Algorithms
2.2 Shortest-remaining-time-first (Preemptive SJF )
Process Arrival Time Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5
Preemptive SJF Gantt Chart

P1 P2 P4 P1 P3
0 1 5 10 17 26

Waiting Time
𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒
10 − 1 1−1 17 − 2 5−3
= 𝟗 = 𝟎 = 𝟏𝟓 = 𝟐 Average waiting time = [9+0+15+2]/4 = 26/4 = 6.5 msec
©Ahmed Hagag Operating Systems 131
 Scheduling Algorithms
2.2 Shortest-remaining-time-first (Preemptive SJF )
Process Arrival Time Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5
Preemptive SJF Gantt Chart

P1 P2 P4 P1 P3
0 1 5 10 17 26

Turnaround Time
𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒

©Ahmed Hagag Operating Systems 132

 Scheduling Algorithms
2.2 Shortest-remaining-time-first (Preemptive SJF )
Process Arrival Time Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5
Preemptive SJF Gantt Chart

P1 P2 P4 P1 P3
0 1 5 10 17 26

Turnaround Time
𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒
17 − 0 5−1 26 − 2 10 − 3
= 𝟏𝟕 = 𝟒 = 𝟐𝟒 = 𝟕 Average turnaround time = [17+4+24+7]/4 = 52/4 = 13 msec

©Ahmed Hagag Operating Systems 133

 Scheduling Algorithms
2.2 Shortest-remaining-time-first (Preemptive SJF )
Process Arrival Time Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5
Preemptive SJF Gantt Chart

P1 P2 P4 P1 P3
0 1 5 10 17 26

Response Time
𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒

©Ahmed Hagag Operating Systems 134

 Scheduling Algorithms
2.2 Shortest-remaining-time-first (Preemptive SJF )
Process Arrival Time Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5
Preemptive SJF Gantt Chart

P1 P2 P4 P1 P3
0 1 5 10 17 26

Response Time
𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒
0−0 1−1 17 − 2 5−3
= 𝟎 = 𝟎 = 𝟏𝟓 = 𝟐 Average response time = [0+0+15+2]/4 = 17/4 = 4.25 msec

©Ahmed Hagag Operating Systems 135

 Scheduling Criteria
• CPU utilization – keep the CPU as busy as possible.
• Throughput – #of processes that complete their execution per time unit.
• Turnaround time – amount of time to execute a particular process. (time from
submission to termination)
• Waiting time – amount of time a process has been waiting in the ready queue.
• Response time – amount of time it takes from when a request was submitted
until the first response is produced, not output.

©Ahmed Hagag Operating Systems 136

 Scheduling Criteria
Scheduling Algorithm Optimization Criteria

• Max CPU utilization.

• Max throughput.
• Min turnaround time.
• Min waiting time.
• Min response time.

©Ahmed Hagag Operating Systems 137

 Scheduling Algorithms
• There are many different CPU-scheduling algorithms:
1. First Come, First Served (FCFS).
2. Shortest Job First (SJF).
➢ Preemptive SJF.
➢ Non-Preemptive SJF.
3. Priority.
4. Round Robin.
5. Multilevel queues.

©Ahmed Hagag Operating Systems 138

 Scheduling Algorithms
3. Priority Scheduling
A priority number (integer) is associated with each process

The CPU is allocated to the process with the highest priority (smallest integer
 highest priority)
Preemptive
Nonpreemptive

SJF is priority scheduling where priority is the inverse of predicted next CPU
burst time

Problem  Starvation – low priority processes may never execute

Solution  Aging – as time progresses increase the priority of the process

©Ahmed Hagag Operating Systems 139

 Scheduling Algorithms
3. Priority Scheduling
Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
Priority scheduling Gantt Chart

©Ahmed Hagag Operating Systems 140

 Scheduling Algorithms
3. Priority Scheduling
Process Burst Time Priority
P1 10 3
P2 1 1 Highest priority
P3 2 4
P4 1 5
P5 5 2
Priority scheduling Gantt Chart

©Ahmed Hagag Operating Systems 141

 Scheduling Algorithms
3. Priority Scheduling
Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
Priority scheduling Gantt Chart

©Ahmed Hagag Operating Systems 142

 Scheduling Algorithms
3. Priority Scheduling
Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
Priority scheduling Gantt Chart

©Ahmed Hagag Operating Systems 143

 Scheduling Algorithms
3. Priority Scheduling
Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
Priority scheduling Gantt Chart

©Ahmed Hagag Operating Systems 144

 Scheduling Algorithms
3. Priority Scheduling
Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
Priority scheduling Gantt Chart

©Ahmed Hagag Operating Systems 145

 Scheduling Algorithms
3. Priority Scheduling
Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
Priority scheduling Gantt Chart

©Ahmed Hagag Operating Systems 146

 Scheduling Algorithms
3. Priority Scheduling
Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
Priority scheduling Gantt Chart

Waiting Time
𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒 𝑷𝟓

©Ahmed Hagag Operating Systems 147

 Scheduling Algorithms
3. Priority Scheduling
Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
Priority scheduling Gantt Chart

Waiting Time
𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒 𝑷𝟓
6 0 16 18 1 Average Waiting time = [6+0+16+18+1]/5 = 8.2 msec

©Ahmed Hagag Operating Systems 148

 Scheduling Algorithms
3. Priority Scheduling
Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
Priority scheduling Gantt Chart

Turnaround Time
𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒 𝑷𝟓

©Ahmed Hagag Operating Systems 149

 Scheduling Algorithms
3. Priority Scheduling
Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
Priority scheduling Gantt Chart

Turnaround Time
𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒 𝑷𝟓
16 1 18 19 6 Average Turnaround time = [16+1+18+19+6]/5 = 12 msec

©Ahmed Hagag Operating Systems 150

 Scheduling Algorithms
3. Priority Scheduling
Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
Priority scheduling Gantt Chart

Response Time
𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒 𝑷𝟓

©Ahmed Hagag Operating Systems 151

 Scheduling Algorithms
3. Priority Scheduling
Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
Priority scheduling Gantt Chart

Response Time
𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒 𝑷𝟓
6 0 16 18 1 Average Response time = [6+0+16+18+1]/5 = 8.2 msec

©Ahmed Hagag Operating Systems 152

 Scheduling Algorithms
4. Round Robin (RR) Scheduling
Each process gets a small unit of CPU time (time quantum q),
usually 10-100 milliseconds. After this time has elapsed, the
process is preempted and added to the end of the ready queue.
If there are 𝑛processes in the ready queue and the time quantum
is 𝑞, then each process gets 1/𝑛 of the CPU time in chunks of at
most 𝑞time units at once.
No process waits more than (𝑛 − 1)𝑞 time units.

©Ahmed Hagag Operating Systems 153

 Scheduling Algorithms
4. Round Robin (RR) Scheduling

©Ahmed Hagag Operating Systems 154

 Scheduling Algorithms
4. Round Robin (RR) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
All the processes arrive at the same time 0.
Round Robin (RR) scheduling of quantum: 4 ms

©Ahmed Hagag Operating Systems 155

 Scheduling Algorithms
4. Round Robin (RR) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
All the processes arrive at the same time 0.
Round Robin (RR) scheduling of quantum: 4 ms

P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30

©Ahmed Hagag Operating Systems 156

 Scheduling Algorithms
4. Round Robin (RR) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
All the processes arrive at the same time 0.
Round Robin (RR) scheduling of quantum: 4 ms

P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30

©Ahmed Hagag Operating Systems 157

 Scheduling Algorithms
4. Round Robin (RR) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
All the processes arrive at the same time 0.
Round Robin (RR) scheduling of quantum: 4 ms

P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30

©Ahmed Hagag Operating Systems 158

 Scheduling Algorithms
4. Round Robin (RR) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
All the processes arrive at the same time 0.
Round Robin (RR) scheduling of quantum: 4 ms

P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30

©Ahmed Hagag Operating Systems 159

 Scheduling Algorithms
4. Round Robin (RR) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
All the processes arrive at the same time 0.
Round Robin (RR) scheduling of quantum: 4 ms

P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30

©Ahmed Hagag Operating Systems 160

 Scheduling Algorithms
4. Round Robin (RR) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
All the processes arrive at the same time 0.
Round Robin (RR) scheduling of quantum: 4 ms

P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30

©Ahmed Hagag Operating Systems 161

 Scheduling Algorithms
4. Round Robin (RR) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
All the processes arrive at the same time 0.
Round Robin (RR) scheduling of quantum: 4 ms

P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30

©Ahmed Hagag Operating Systems 162

 Scheduling Algorithms
4. Round Robin (RR) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
All the processes arrive at the same time 0.
Round Robin (RR) scheduling of quantum: 4 ms

P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30

©Ahmed Hagag Operating Systems 163

 Scheduling Algorithms
4. Round Robin (RR) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
All the processes arrive at the same time 0.
Round Robin (RR) scheduling of quantum: 4 ms

P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30

©Ahmed Hagag Operating Systems 164

 Scheduling Algorithms
4. Round Robin (RR) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
All the processes arrive at the same time 0.
Round Robin (RR) scheduling of quantum: 4 ms

P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30

# of context switches = ??

©Ahmed Hagag Operating Systems 165

 Scheduling Algorithms
4. Round Robin (RR) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
All the processes arrive at the same time 0.
Round Robin (RR) scheduling of quantum: 4 ms

P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30

# of context switches = 7

©Ahmed Hagag Operating Systems 166

 Scheduling Algorithms
4. Round Robin (RR) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
All the processes arrive at the same time 0.
Round Robin (RR) scheduling of quantum: 4 ms

P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30

Waiting Time
𝑷𝟏 𝑷𝟐 𝑷𝟑

©Ahmed Hagag Operating Systems 167

 Scheduling Algorithms
4. Round Robin (RR) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
All the processes arrive at the same time 0.
Round Robin (RR) scheduling of quantum: 4 ms

P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30

Waiting Time
𝑷𝟏 𝑷𝟐 𝑷𝟑
0 + (10 − 4) 4 7

Average waiting time: (6 + 4 + 7)/3 = 5.667 ms

©Ahmed Hagag Operating Systems 168

 Scheduling Algorithms
4. Round Robin (RR) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
All the processes arrive at the same time 0.
Round Robin (RR) scheduling of quantum: 4 ms

P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30

Turnaround Time
𝑷𝟏 𝑷𝟐 𝑷𝟑

©Ahmed Hagag Operating Systems 169

 Scheduling Algorithms
4. Round Robin (RR) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
All the processes arrive at the same time 0.
Round Robin (RR) scheduling of quantum: 4 ms

P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30

Turnaround Time
𝑷𝟏 𝑷𝟐 𝑷𝟑
30 7 10

Average Turnaround time: (30 + 7 + 10)/3 = 15.667 ms

©Ahmed Hagag Operating Systems 170

 Scheduling Algorithms
4. Round Robin (RR) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
All the processes arrive at the same time 0.
Round Robin (RR) scheduling of quantum: 4 ms

P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30

Response Time
𝑷𝟏 𝑷𝟐 𝑷𝟑

©Ahmed Hagag Operating Systems 171

 Scheduling Algorithms
4. Round Robin (RR) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
All the processes arrive at the same time 0.
Round Robin (RR) scheduling of quantum: 4 ms

P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30

Response Time
𝑷𝟏 𝑷𝟐 𝑷𝟑
0 4 7

Average Response time: (0 + 4 + 7)/3 = 3.667 ms

©Ahmed Hagag Operating Systems 172

 Scheduling Algorithms
• There are many different CPU-scheduling algorithms:
1. First Come, First Served (FCFS).
2. Shortest Job First (SJF).
➢ Preemptive SJF.
➢ Non-Preemptive SJF.
3. Priority.
4. Round Robin.
5. Multilevel queues.

©Ahmed Hagag Operating Systems 173

 Scheduling Algorithms
5. Multilevel Queue Scheduling
Ready queue is partitioned into separate queues, eg:
foreground (interactive)
background (batch)
Process permanently in a given queue
Each queue has its own scheduling algorithm:
foreground – RR.
background – FCFS.

©Ahmed Hagag Operating Systems 174

 Scheduling Algorithms
5. Multilevel Queue Scheduling
Scheduling must be done between the queues:
Fixed priority scheduling; (i.e., serve all from foreground
then from background). Possibility of starvation.
Time slice – each queue gets a certain amount of CPU time
which it can schedule amongst its processes; i.e., 80% to
foreground in RR.
20% to background in FCFS.

©Ahmed Hagag Operating Systems 175

 Scheduling Algorithms
5. Multilevel Queue Scheduling

©Ahmed Hagag Operating Systems 176

 Scheduling Algorithms
5. Multilevel Queue Scheduling
Three queues:
Q0 – RR with time quantum 8 milliseconds
Q1 – RR time quantum 16 milliseconds
Q2 – FCFS

©Ahmed Hagag Operating Systems 177

 Scheduling Algorithms
5. Multilevel Queue Scheduling
Scheduling
A new job enters queue 𝑄0 which is served FCFS
 When it gains CPU, job receives 8 milliseconds.
 If it does not finish in 8 milliseconds, job is moved to queue 𝑄1.

At 𝑄1 job is again served FCFS and receives 16 additional milliseconds

 If it still does not complete, it is preempted and moved to queue 𝑄2.

©Ahmed Hagag Operating Systems 178

 Scheduling Algorithms
5. Multilevel Queue Scheduling
Now we add the concepts of varying arrival times and preemption to the
analysis
Process Arrival Time Burst Time
P1 0 7
P2 1 60
P3 2 20
P4 3 40

Multilevel Queue Fixed priority

non-preemptive

©Ahmed Hagag Operating Systems 179

 Scheduling Algorithms
𝑄0
5. Multilevel Queue Scheduling
Process Arrival Time Burst Time
𝑄1
P1 0 7
P2 1 60
𝑄2
P3 2 20
P4 3 40

𝑄0

𝑄1

𝑄2

©Ahmed Hagag Operating Systems 180

 Scheduling Algorithms
𝑄0
5. Multilevel Queue Scheduling
Process Arrival Time Burst Time
𝑄1
P1 0 7
P2 1 60
𝑄2
P3 2 20
P4 3 40

7ms
7ms
𝑄0 𝑃1

𝑄1

𝑄2

©Ahmed Hagag Operating Systems 181

 Scheduling Algorithms
𝑄0
5. Multilevel Queue Scheduling
Process Arrival Time Burst Time
𝑄1
P1 0 7
P2 1 60
𝑄2
P3 2 20
P4 3 40

7ms
7ms 8ms
𝑄0 𝑃1 𝑃2

𝑄1

𝑄2

©Ahmed Hagag Operating Systems 182

 Scheduling Algorithms
𝑄0
5. Multilevel Queue Scheduling
Process Arrival Time Burst Time
𝑄1
P1 0 7
P2 1 60 52
𝑄2
P3 2 20
P4 3 40

15ms
7ms 8ms
𝑄0 𝑃1 𝑃2

𝑄1

𝑄2

©Ahmed Hagag Operating Systems 183

 Scheduling Algorithms
𝑄0
5. Multilevel Queue Scheduling
Process Arrival Time Burst Time
𝑄1
P1 0 7
P2 1 60 52
𝑄2
P3 2 20
P4 3 40

15ms
7ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3

𝑄1 𝑃2

𝑄2

©Ahmed Hagag Operating Systems 184

 Scheduling Algorithms
5. Multilevel Queue Scheduling
𝑄0
Process Arrival Time Burst Time
P1 0 7
𝑄1 P2 1 60 52 44
P3 2 20 12
𝑄2 P4 3 40

23ms
7ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3

𝑄1 𝑃2

𝑄2

©Ahmed Hagag Operating Systems 185

 Scheduling Algorithms
5. Multilevel Queue Scheduling
𝑄0
Process Arrival Time Burst Time
P1 0 7
𝑄1 P2 1 60 52 44
P3 2 20 12
𝑄2 P4 3 40

23ms
7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4

𝑄1 𝑃2

𝑄2

©Ahmed Hagag Operating Systems 186

 Scheduling Algorithms
5. Multilevel Queue Scheduling
𝑄0
Process Arrival Time Burst Time
P1 0 7
𝑄1 P2 1 60 52 44 36
P3 2 20 12
𝑄2 P4 3 40 32

31ms
7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms
𝑄1 𝑃2

𝑄2

©Ahmed Hagag Operating Systems 187

 Scheduling Algorithms
5. Multilevel Queue Scheduling
𝑄0
Process Arrival Time Burst Time
P1 0 7
𝑄1 P2 1 60 52 44 36
P3 2 20 12
𝑄2 P4 3 40 32

31ms
7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms
𝑄1 𝑃2 𝑃3
36ms
𝑄2 𝑃2

©Ahmed Hagag Operating Systems 188

 Scheduling Algorithms
5. Multilevel Queue Scheduling
𝑄0 Arrival Time Burst Time
Process
P1 0 7
𝑄1 P2 1 60 52 44 36 24
P3 2 20 12
𝑄2 P4 3 40 32

43ms
7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms
𝑄1 𝑃2 𝑃3
36ms
𝑄2 𝑃2

©Ahmed Hagag Operating Systems 189

 Scheduling Algorithms
5. Multilevel Queue Scheduling
𝑄0 Arrival Time Burst Time
Process
P1 0 7
𝑄1 P2 1 60 52 44 36 24
P3 2 20 12
𝑄2 P4 3 40 32

43ms
7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms 16ms
𝑄1 𝑃2 𝑃3 𝑃4
36ms
𝑄2 𝑃2

©Ahmed Hagag Operating Systems 190

 Scheduling Algorithms
5. Multilevel Queue Scheduling
𝑄0
Process Arrival Time Burst Time
P1 0 7
𝑄1 P2 1 60 52 44 36 24 8
P3 2 20 12
𝑄2 P4 3 40 32 16

59ms
7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms 16ms
𝑄1 𝑃2 𝑃3 𝑃4
36ms
𝑄2 𝑃2

©Ahmed Hagag Operating Systems 191

 Scheduling Algorithms
5. Multilevel Queue Scheduling
𝑄0 Arrival Time Burst Time
Process
P1 0 7
𝑄1 P2 1 60 52 44 36 24 8
P3 2 20 12
𝑄2 P4 3 40 32 16

67ms
7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms 16ms
𝑄1 𝑃2 𝑃3 𝑃4
36ms
𝑄2 𝑃2

©Ahmed Hagag Operating Systems 192

 Scheduling Algorithms
5. Multilevel Queue Scheduling
𝑄0 Arrival Time Burst Time
Process
P1 0 7
𝑄1 P2 1 60 52 44 36 24 8
P3 2 20 12
𝑄2 P4 3 40 32 16

67ms
7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms 16ms
𝑄1 𝑃2 𝑃3 𝑃4
36ms 16ms
𝑄2 𝑃2 𝑃4

©Ahmed Hagag Operating Systems 193

 Scheduling Algorithms
5. Multilevel Queue Scheduling
𝑄0 Arrival Time Burst Time
Process
P1 0 7
𝑄1 P2 1 60 52 44 36 24 8
P3 2 20 12
𝑄2 P4 3 40 32 16

83ms
7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms 16ms
𝑄1 𝑃2 𝑃3 𝑃4
36ms 16ms
𝑄2 𝑃2 𝑃4

©Ahmed Hagag Operating Systems 194

 Scheduling Algorithms
5. Multilevel Queue Scheduling
𝑄0 Arrival Time Burst Time
Process
P1 0 7
𝑄1 P2 1 60 52 44 36 24 8
P3 2 20 12
𝑄2 P4 3 40 32 16

7ms 15ms 23ms 31ms 43ms 59ms 67ms 83ms

7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms 16ms
𝑄1 𝑃2 𝑃3 𝑃4
36ms 16ms
𝑄2 𝑃2 𝑃4

©Ahmed Hagag Operating Systems 195

 Scheduling Algorithms
5. Multilevel Queue Scheduling
𝑄0
Process Arrival Time
Waiting Time
P1 0
𝑄1 𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒
P2 1
P3 2
𝑄2 P4 3

7ms 15ms 23ms 31ms 43ms 59ms 67ms 83ms

7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms 16ms
𝑄1 𝑃2 𝑃3 𝑃4
36ms 16ms
𝑄2 𝑃2 𝑃4

©Ahmed Hagag Operating Systems 196

 Scheduling Algorithms
5. Multilevel Queue Scheduling
𝑄0
Process Arrival Time
Waiting Time
P1 0
𝑄1 𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒
P2 1
0
P3 2
= 𝟎
𝑄2 P4 3

7ms 15ms 23ms 31ms 43ms 59ms 67ms 83ms

7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms 16ms
𝑄1 𝑃2 𝑃3 𝑃4
36ms 16ms
𝑄2 𝑃2 𝑃4

©Ahmed Hagag Operating Systems 197

 Scheduling Algorithms
5. Multilevel Queue Scheduling
𝑄0
Process Arrival Time
Waiting Time
P1 0
𝑄1 𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒
P2 1
0 7−1
P3 2
= 𝟎 = 𝟔
𝑄2 P4 3

7ms 15ms 23ms 31ms 43ms 59ms 67ms 83ms

7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms 16ms
𝑄1 𝑃2 𝑃3 𝑃4
36ms 16ms
𝑄2 𝑃2 𝑃4

©Ahmed Hagag Operating Systems 198

 Scheduling Algorithms
5. Multilevel Queue Scheduling
𝑄0
Process Arrival Time
Waiting Time
P1 0
𝑄1 𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒
P2 1
0 7−1 15 + 8 − 2
P3 2
= 𝟎 = 𝟔 = 𝟐𝟏
𝑄2 P4 3

7ms 15ms 23ms 31ms 43ms 59ms 67ms 83ms

7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms 16ms
𝑄1 𝑃2 𝑃3 𝑃4
36ms 16ms
𝑄2 𝑃2 𝑃4

©Ahmed Hagag Operating Systems 199

 Scheduling Algorithms
5. Multilevel Queue Scheduling
𝑄0
Process Arrival Time
Waiting Time
P1 0
𝑄1 𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒
P2 1
0 7−1 15 + 8 − 2 23 + 12 + 8 − 3
P3 2
= 𝟎 = 𝟔 = 𝟐𝟏 = 𝟒𝟎
𝑄2 P4 3

7ms 15ms 23ms 31ms 43ms 59ms 67ms 83ms

7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms 16ms
𝑄1 𝑃2 𝑃3 𝑃4
36ms 16ms
𝑄2 𝑃2 𝑃4

©Ahmed Hagag Operating Systems 200

 Scheduling Algorithms
5. Multilevel Queue Scheduling
𝑄0
Process Arrival Time
Turnaround Time
P1 0
𝑄1 𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒
P2 1
P3 2
𝑄2 P4 3

7ms 15ms 23ms 31ms 43ms 59ms 67ms 83ms

7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms 16ms
𝑄1 𝑃2 𝑃3 𝑃4
36ms 16ms
𝑄2 𝑃2 𝑃4

©Ahmed Hagag Operating Systems 201

 Scheduling Algorithms
5. Multilevel Queue Scheduling
𝑄0
Process Arrival Time
Turnaround Time
P1 0
𝑄1 𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒
P2 1
7−0
P3 2
= 𝟕
𝑄2 P4 3

7ms 15ms 23ms 31ms 43ms 59ms 67ms 83ms

7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms 16ms
𝑄1 𝑃2 𝑃3 𝑃4
36ms 16ms
𝑄2 𝑃2 𝑃4

©Ahmed Hagag Operating Systems 202

 Scheduling Algorithms
5. Multilevel Queue Scheduling
𝑄0
Process Arrival Time
Turnaround Time
P1 0
𝑄1 𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒
P2 1
7−0 67 − 1
P3 2
= 𝟕 = 𝟔𝟔
𝑄2 P4 3

7ms 15ms 23ms 31ms 43ms 59ms 67ms 83ms

7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms 16ms
𝑄1 𝑃2 𝑃3 𝑃4
36ms 16ms
𝑄2 𝑃2 𝑃4

©Ahmed Hagag Operating Systems 203

 Scheduling Algorithms
5. Multilevel Queue Scheduling
𝑄0
Process Arrival Time
Turnaround Time
P1 0
𝑄1 𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒
P2 1
7−0 67 − 1 43 − 2
P3 2
= 𝟕 = 𝟔𝟔 = 𝟒𝟏
𝑄2 P4 3

7ms 15ms 23ms 31ms 43ms 59ms 67ms 83ms

7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms 16ms
𝑄1 𝑃2 𝑃3 𝑃4
36ms 16ms
𝑄2 𝑃2 𝑃4

©Ahmed Hagag Operating Systems 204

 Scheduling Algorithms
5. Multilevel Queue Scheduling
𝑄0
Process Arrival Time
Turnaround Time
P1 0
𝑄1 𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒
P2 1
7−0 67 − 1 43 − 2 83 − 3
P3 2
= 𝟕 = 𝟔𝟔 = 𝟒𝟏 = 𝟖𝟎
𝑄2 P4 3

7ms 15ms 23ms 31ms 43ms 59ms 67ms 83ms

7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms 16ms
𝑄1 𝑃2 𝑃3 𝑃4
36ms 16ms
𝑄2 𝑃2 𝑃4

©Ahmed Hagag Operating Systems 205

 Scheduling Algorithms
5. Multilevel Queue Scheduling
𝑄0
Process Arrival Time
Response Time
P1 0
𝑄1 𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒
P2 1
P3 2
𝑄2 P4 3

7ms 15ms 23ms 31ms 43ms 59ms 67ms 83ms

7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms 16ms
𝑄1 𝑃2 𝑃3 𝑃4
36ms 16ms
𝑄2 𝑃2 𝑃4

©Ahmed Hagag Operating Systems 206

 Scheduling
5. Multilevel Queue Scheduling
Algorithms (24/32)
𝑄0
Process Arrival Time
Response Time
P1 0
𝑄1 𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒
P2 1
0−0
P3 2
= 𝟎
𝑄2 P4 3

7ms 15ms 23ms 31ms 43ms 59ms 67ms 83ms

7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms 16ms
𝑄1 𝑃2 𝑃3 𝑃4
36ms 16ms
𝑄2 𝑃2 𝑃4

©Ahmed Hagag Operating Systems 207

 Scheduling Algorithms
5. Multilevel Queue Scheduling
𝑄0
Process Arrival Time
Response Time
P1 0
𝑄1 𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒
P2 1
0−0 7−1
P3 2
= 𝟎 = 𝟔
𝑄2 P4 3

7ms 15ms 23ms 31ms 43ms 59ms 67ms 83ms

7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms 16ms
𝑄1 𝑃2 𝑃3 𝑃4
36ms 16ms
𝑄2 𝑃2 𝑃4

©Ahmed Hagag Operating Systems 208

 Scheduling Algorithms
5. Multilevel Queue Scheduling
𝑄0
Process Arrival Time
Response Time
P1 0
𝑄1 𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒
P2 1
0−0 7−1 15 − 2
P3 2
= 𝟎 = 𝟔 = 𝟏𝟑
𝑄2 P4 3

7ms 15ms 23ms 31ms 43ms 59ms 67ms 83ms

7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms 16ms
𝑄1 𝑃2 𝑃3 𝑃4
36ms 16ms
𝑄2 𝑃2 𝑃4

©Ahmed Hagag Operating Systems 209

 Scheduling Algorithms
5. Multilevel Queue Scheduling
𝑄0
Process Arrival Time
Response Time
P1 0
𝑄1 𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒
P2 1
0−0 7−1 15 − 2 23 − 3
P3 2
= 𝟎 = 𝟔 = 𝟏𝟑 = 𝟐𝟎
𝑄2 P4 3

7ms 15ms 23ms 31ms 43ms 59ms 67ms 83ms

7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms 16ms
𝑄1 𝑃2 𝑃3 𝑃4
36ms 16ms
𝑄2 𝑃2 𝑃4

©Ahmed Hagag Operating Systems 210

 Scheduling Algorithms
5. Multilevel Queue Scheduling
Now we add the concepts of varying arrival times and preemption to the
analysis
Process Arrival Time Burst Time
P1 0 7
P2 1 60 Using single-
P3 2 20 core processor
P4 3 40

Multilevel Queue Fixed priority

non-preemptive

©Ahmed Hagag Operating Systems 211

 Scheduling Algorithms
𝑄0
5. Multilevel Queue Scheduling
Process Arrival Time Burst Time
𝑄1
P1 0 7
P2 1 60
P3 2 20 𝑄2
P4 3 40

𝑄0

𝑄1

𝑄2

©Ahmed Hagag Operating Systems 212

 Scheduling Algorithms
𝑄0
5. Multilevel Queue Scheduling
Process Arrival Time Burst Time
𝑄1
P1 0 7
P2 1 60
P3 2 20 𝑄2
P4 3 40

7ms
7ms
𝑄0 𝑃1

𝑄1

𝑄2

©Ahmed Hagag Operating Systems 213

 Scheduling Algorithms
𝑄0
5. Multilevel Queue Scheduling
Process Arrival Time Burst Time
𝑄1
P1 0 7
P2 1 60
P3 2 20 𝑄2
P4 3 40

7ms
7ms
𝑄0 𝑃1

𝑄1

𝑄2

©Ahmed Hagag Operating Systems 214

 Scheduling Algorithms
5. Multilevel Queue Scheduling
Process Arrival Time Burst Time
P1 0 7
P2 1 60 52
P3 2 20
P4 3 40
15ms
7ms
7ms 8ms
𝑄0 𝑃1 𝑃2

𝑄1

𝑄2

©Ahmed Hagag Operating Systems 215

 Scheduling Algorithms
5. Multilevel Queue Scheduling
Process Arrival Time Burst Time
P1 0 7
P2 1 60 52
P3 2 20 12
P4 3 40
15ms
7ms 23ms
7ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3

𝑄1

𝑄2

©Ahmed Hagag Operating Systems 216

 Scheduling Algorithms
5. Multilevel Queue Scheduling
Process Arrival Time Burst Time
P1 0 7
P2 1 60 52
P3 2 20 12
P4 3 40 32
15ms 31ms
7ms 23ms
7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4

𝑄1

𝑄2

©Ahmed Hagag Operating Systems 217

 Scheduling Algorithms
5. Multilevel Queue Scheduling
Process Arrival Time Burst Time
P1 0 7
P2 1 60 52 36
P3 2 20 12
P4 3 40 32
15ms 31ms
7ms 23ms 47ms
7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms
𝑄1 𝑃2

𝑄2

©Ahmed Hagag Operating Systems 218

 Scheduling Algorithms
5. Multilevel Queue Scheduling
Process Arrival Time Burst Time
P1 0 7
P2 1 60 52 36
P3 2 20 12
P4 3 40 32
15ms 31ms 59ms
7ms 23ms 47ms
7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms
𝑄1 𝑃2 𝑃3

𝑄2

©Ahmed Hagag Operating Systems 219

 Scheduling Algorithms
5. Multilevel Queue Scheduling
Process Arrival Time Burst Time
P1 0 7
P2 1 60 52 36
P3 2 20 12
P4 3 40 32
15ms 31ms 59ms
7ms 23ms 47ms
7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms
𝑄1 𝑃2 𝑃3

𝑄2

©Ahmed Hagag Operating Systems 220

 Scheduling Algorithms
5. Multilevel Queue Scheduling
Process Arrival Time Burst Time
P1 0 7
P2 1 60 52 36
P3 2 20 12
P4 3 40 32 16
15ms 31ms 59ms
7ms 23ms 47ms 75ms
7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms 16ms
𝑄1 𝑃2 𝑃3 𝑃4

𝑄2

©Ahmed Hagag Operating Systems 221

 Scheduling Algorithms
5. Multilevel Queue Scheduling
Process Arrival Time Burst Time
P1 0 7
P2 1 60 52 36
P3 2 20 12
P4 3 40 32 16
15ms 31ms 59ms
7ms 23ms 47ms 75ms 111ms
7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms 16ms
𝑄1 𝑃2 𝑃3 𝑃4
36ms
𝑄2 𝑃2

©Ahmed Hagag Operating Systems 222

 Scheduling Algorithms
5. Multilevel Queue Scheduling
Process Arrival Time Burst Time
P1 0 7
P2 1 60 52 36
P3 2 20 12
P4 3 40 32 16
15ms 31ms 59ms
7ms 23ms 47ms 75ms 111ms
7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms 16ms
𝑄1 𝑃2 𝑃3 𝑃4
36ms
𝑄2 𝑃2

©Ahmed Hagag Operating Systems 223

 Scheduling Algorithms
5. Multilevel Queue Scheduling
Process Arrival Time Burst Time
P1 0 7
P2 1 60 52 36
P3 2 20 12
P4 3 40 32 16
15ms 31ms 59ms
7ms 23ms 47ms 75ms 111ms 127ms
7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms 16ms
𝑄1 𝑃2 𝑃3 𝑃4
36ms 16ms
𝑄2 𝑃2 𝑃4

©Ahmed Hagag Operating Systems 224

 Scheduling Algorithms
5. Multilevel Queue Scheduling
Process Arrival Time Burst Time
P1 0 7
P2 1 60 52 36
P3 2 20 12
P4 3 40 32 16
15ms 31ms 59ms
7ms 23ms 47ms 75ms 111ms 127ms
7ms 8ms 8ms 8ms
𝑄0 𝑃1 𝑃2 𝑃3 𝑃4
16ms 12ms 16ms
𝑄1 𝑃2 𝑃3 𝑃4
36ms 16ms
𝑄2 𝑃2 𝑃4

©Ahmed Hagag Operating Systems 225

 Scheduling Algorithms
5. Multilevel Queue Scheduling
Process Arrival Time Burst Time
P1 0 7
P2 1 60 52 36
P3 2 20 12
P4 3 40 32 16

15ms 31ms 59ms

7ms 23ms 47ms 75ms 111ms 127ms
7ms 8ms 8ms 8ms 16ms 12ms 16ms 36ms 16ms
𝑃1 𝑃2 𝑃3 𝑃4 𝑃2 𝑃3 𝑃4 𝑃2 𝑃4

©Ahmed Hagag Operating Systems 226

 Scheduling Algorithms
5. Multilevel Queue Scheduling
Process Arrival Time
P1 0
Waiting Time
P2 1
𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒
P3 2 0 6 + 16 13 + 24 20 + 28
P4 3 + 28 + 36
=𝟎 = 𝟓𝟎 = 𝟑𝟕 = 𝟖𝟒

15ms 31ms 59ms

7ms 23ms 47ms 75ms 111ms 127ms
7ms 8ms 8ms 8ms 16ms 12ms 16ms 36ms 16ms
𝑃1 𝑃2 𝑃3 𝑃4 𝑃2 𝑃3 𝑃4 𝑃2 𝑃4

©Ahmed Hagag Operating Systems 227

 Scheduling Algorithms
5. Multilevel Queue Scheduling
Process Arrival Time
P1 0
Turnaround Time
P2 1
𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒
P3 2 7−0 111 − 1 59 − 2 127 − 3
P4 3 = 𝟕 = 𝟏𝟏𝟎 = 𝟓𝟕 = 𝟏𝟐𝟒

15ms 31ms 59ms

7ms 23ms 47ms 75ms 111ms 127ms
7ms 8ms 8ms 8ms 16ms 12ms 16ms 36ms 16ms
𝑃1 𝑃2 𝑃3 𝑃4 𝑃2 𝑃3 𝑃4 𝑃2 𝑃4

©Ahmed Hagag Operating Systems 228

 Scheduling Algorithms
5. Multilevel Queue Scheduling
Process Arrival Time
P1 0
Response Time
P2 1
𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟒
P3 2 0−0 7−1 15 − 2 23 − 3
P4 3 = 𝟎 = 𝟔 = 𝟏𝟑 = 𝟐𝟎

15ms 31ms 59ms

7ms 23ms 47ms 75ms 111ms 127ms
7ms 8ms 8ms 8ms 16ms 12ms 16ms 36ms 16ms
𝑃1 𝑃2 𝑃3 𝑃4 𝑃2 𝑃3 𝑃4 𝑃2 𝑃4

©Ahmed Hagag Operating Systems 229

 Scheduling Algorithms
Student Example:
Using a Multilevel Queue Scheduling algorithm in Fig.1. Consider the
following processes with the relative CPU bursts.
Process Arrival Time Burst Time
P1 0 20
P2 1 60
P3 2 5
P4 2 40

Multilevel Queue Fixed priority

non-preemptive
Fig.1

©Ahmed Hagag Operating Systems 230