Process Scheduling and Synchronization
Process Scheduling and Synchronization:
are two core concepts in operating systems that
ensure efficient CPU usage and safe execution of multiple processes.
Process scheduling is
a crucial function of the operating system that manages the execution of
processes by the CPU. It involves selecting which process will run at any given
time, ensuring efficient use of CPU resources and maintaining system
responsiveness.
Process synchronization ensures
that multiple processes accessing shared resources do so in a controlled
manner, preventing race conditions, data inconsistency,
and deadlocks. Synchronization is especially critical
in multi-processing environments where processes may be cooperative or competitive.
Process Scheduling
Process scheduling decides which process gets the
CPU and for how long.
Goals
Maximize CPU utilization
Minimize waiting time
Ensure fairness (impartial)
Improve response time
Types of Scheduling
1. Long-Term Scheduling
Decides which processes are admitted to the system
Controls degree of multiprogramming
2. Short-Term Scheduling (CPU Scheduler)
Selects process from ready queue
Runs very frequently
3. Medium-Term Scheduling
Suspends/resumes processes (swapping)
CPU Scheduling:
CPU scheduling is the method an operating
system uses to decide which process in the ready queue gets CPU time.
Since a CPU can execute only one process at a time, efficient scheduling is
crucial to maximize CPU utilization, minimize waiting time,
and improve throughput.
Scheduling Criteria
The scheduling criteria in CPU scheduling include:
CPU Utilization: The goal is to keep the CPU as busy as possible.
Throughput: The number of processes that complete their execution per time unit.
Turnaround Time: The total time taken from submission to completion of a process.
Waiting Time: The total time a process has been in the ready queue.
Response Time: The time from submission of a request until the first response is produced.
These criteria help in analyzing and prioritizing tasks for efficient CPU scheduling.
(Throughput, Turnaround Time, Waiting Time)
1. CPU utilization: The main objective of any CPU scheduling
algorithm is to keep the CPU as busy as possible. Theoretically, CPU
utilization can range from 0 to 100 but in a real-time system, it varies
from 40 to 90 percent depending on the load upon the system.
2. Throughput: A measure of the work done by the CPU is the
number of processes being executed and completed per unit of time. This is
called throughput. The throughput may vary depending on the length or duration
of the processes.
3. Turnaround Time: For a particular process, an important
criterion is how long it takes to execute that process. The time elapsed from
the time of submission of a process to the time of completion is known as the
turnaround time. Turn-around time is the sum of times spent waiting to get into
memory, waiting in the ready queue, executing in CPU and waiting for I/O.
Turn Around Time = Completion Time - Arrival
Time. (The
arrival time refers to the moment in time when a process enters the ready queue and is
awaiting execution by the CPU.)
4. Waiting Time: A scheduling algorithm does not affect the
time required to complete the process once it starts execution. It only affects
the waiting time of a process i.e. time spent by a process waiting in the ready
queue.
Waiting Time = Turnaround Time - Burst Time. (Burst time, also referred to as “execution
time”. It is the amount of CPU time the process requires to complete its
execution. It is the amount of processing time required by a process to execute
a specific task or unit of a job.)
5. Response Time: In an interactive system, turn-around time is
not the best criterion. A process may produce some output fairly early and
continue computing new results while previous results are being output to the
user. Thus, another criterion is the time taken from submission of the process
of the request until the first response is produced. This measure is called
response time.
Response Time = CPU Allocation Time (when the
CPU was allocated for the first) - Arrival Time
6. Completion Time: The completion time is the time when the
process stops executing, which means that the process has completed its burst
time and is completely executed.
7. Priority: If the operating system assigns priorities to
processes, the scheduling mechanism should favour the higher-priority
processes.
8. Predictability: A given process always should run in about
the same amount of time under a similar system load.
Scheduling Algorithms:
Scheduling
algorithms are essential for managing how processes are assigned to the CPU for
execution. They ensure efficient CPU utilization, minimize waiting time, and
improve overall system performance. These algorithms can be broadly categorized
into pre-emptive (where a
running process can be interrupted) and non-pre-emptive (where a
process runs to completion once started).
FCFS
FCFS
(First Come First Serve) is a basic CPU scheduling algorithm used in Operating
Systems.
Definition
FCFS
means the process that arrives first gets executed first. It follows a FIFO
(First in First Out) order.
This method schedules
processes in the order they arrive, without considering priority or other
factors.
Example
Just
like a queue at a ticket counter:
Like customers lining up at
a grocery store.
First person in line → served first.
How it works
Ø Processes enter the ready queue in order they
arrival
Ø CPU selects the first process
Ø It runs until completion (no interruption)
Ø Then the next process starts
Type
Non-pre-emptive
algorithm
once a process starts, it cannot be
stopped until it finishes
Example
|
Process |
Arrival Time |
Burst Time |
|
P1 |
0 |
5 |
|
P2 |
1 |
3 |
|
P3 |
2 |
2 |
Execution order: P1 → P2 → P3
Advantages
Ø Simple and easy to implement
Ø Fair (no priority system)
Ø No starvation in normal cases
Disadvantages
Ø High waiting time
Ø Convoy effect (small processes wait for big
ones)
Ø Not suitable for interactive systems
Key Point (Exam Ready)
FCFS
= Arrival time based + Non-pre-emptive + FIFO queue
Numerical
problems (Gantt chart, waiting time, turnaround time) step-by-step
Great!
Let’s solve an FCFS numerical problem step-by-step with Gantt chart, Waiting
Time (WT), and Turnaround Time (TAT).
Given Problem
|
Process |
Arrival Time (AT) |
Burst Time (BT) |
|
P1 |
0 |
5 |
|
P2 |
1 |
3 |
|
P3 |
2 |
2 |
Step 1: Order of Execution (FCFS)
Based
on arrival time:
P1 → P2 → P3
Step 2: Gantt Chart
| P1
| P2 |
P3 |
0 5 8
10
Step 3: Completion Time (CT)
|
Process |
CT |
|
P1 |
5 |
|
P2 |
8 |
|
P3 |
10 |
Step 4: Turnaround Time (TAT)
Formula:
TAT = CT − AT
|
Process |
CT |
AT |
TAT = CT-AT |
|
P1 |
5 |
0 |
5 |
|
P2 |
8 |
1 |
7 |
|
P3 |
10 |
2 |
8 |
Step 5: Waiting Time (WT)
Formula:
WT = TAT − BT
|
Process |
TAT |
BT |
WT = TAT-BT |
|
P1 |
5 |
5 |
0 |
|
P2 |
7 |
3 |
4 |
|
P3 |
8 |
2 |
6 |
Step 6: Average Times
Average Waiting Time (AWT)
= (0 + 4 + 6) / 3 = 3.33
Average Turnaround Time (ATAT)
= (5 + 7 + 8) / 3 = 6.67
Final Answer
Gantt chart: 0 | P1 | 5
| P2 | 8 | P3 | 10
Average Waiting Time: 3.33
Average Turnaround Time: 6.67
Always follow arrival
order
First
process WT = 0
Use formulas:
TAT = CT − AT
WT = TAT − BT
SJF
SJF
(Shortest Job First) Scheduling
SJF is a CPU scheduling algorithm where the process
with the smallest burst time (execution time) is executed first.
The Shortest Job First (SJF) Scheduling algorithm
selects the process with the smallest burst time for execution. But in some
cases, the exact burst time of a process may not be known in advance.
Goal:
Minimize average waiting time and turnaround time.
Types
of SJF
Non-Pre-emptive SJF → Once a process starts, it finishes completely.
The short-term scheduler is invoked when a process completes or when a new process arrives in an empty ready
queue
Pre-emptive SJF (SRTF -
Shortest Remaining Time First) → CPU can switch if a shorter job
arrives.
The short-term scheduler is invoked when a new process arrives or an existing process completes.
|
|
Process |
Arrival Time (AT) |
Burst Time (BT) |
|
P1 |
0 |
6 |
|
P2 |
1 |
3 |
|
P3 |
2 |
1 |
|
P4 |
3 |
2 |
Step 1: Select Shortest Job
At time 0 → Only P1 available → run P1
After that, choose shortest among remaining
Order
becomes:
P1 → P3 → P4 → P2
Step 2: Gantt Chart
| P1 | P3 | P4 | P2 |
0 6 7
9 12
Step 3: Completion Time (CT)
|
Process |
CT |
|
P1 |
6 |
|
P3 |
7 |
|
P4 |
9 |
|
P2 |
12 |
Step 4: Turnaround Time (TAT)
TAT = CT − AT
|
Process |
CT |
AT |
TAT |
|
P1 |
6 |
0 |
6 |
|
P2 |
12 |
1 |
11 |
|
P3 |
7 |
2 |
5 |
|
P4 |
9 |
3 |
6 |
Step 5: Waiting Time (WT)
WT = TAT − BT
|
Process |
TAT |
BT |
WT |
|
P1 |
6 |
6 |
0 |
|
P2 |
11 |
3 |
8 |
|
P3 |
5 |
1 |
4 |
|
P4 |
6 |
2 |
4 |
Step 6: Average Times
Average
Waiting Time
= (0 + 8 + 4 + 4) / 4 = 4
Average
Turnaround Time
= (6 + 11 + 5 + 6) / 4 = 7
Final
Answer
Execution Order: P1 → P3 → P4 → P2
Average WT: 4
Average TAT: 7
Advantages
Minimum average waiting time
Efficient for batch systems
Disadvantages
Long processes may suffer (starvation)
Requires knowing burst time in advance
Pre-emptive SJF (SRTF -
Shortest Remaining Time First)
Example with Gantt chart
Suppose we have 4 processes:
|
Process |
Arrival Time |
Burst Time |
|
P1 |
0 |
6 |
|
P2 |
1 |
8 |
|
P3 |
2 |
7 |
|
P4 |
3 |
3 |
Non-Pre-emptive SJF Execution Order:
- At time 0 → P1
starts (burst 6).
- At time 6 → P4 has
arrived with burst 3 → runs next.
- At time 9 → P3
(burst 7).
- At time 16 → P2
(burst 8).
Gantt Chart:
| P1 | P4 | P3 | P2 |
0 6 9 16 24
Waiting Times:
- P1: 0
- P2: 16 - 1 = 15
- P3: 9 - 2 = 7
- P4: 6 - 3 = 3
Average Waiting Time = (0 + 15 + 7 + 3) / 4 = 6.25
Notice how this is much lower than FCFS, which
would give a higher average waiting time.
Advantages
- Minimizes average
waiting time.
- Efficient for batch
systems.
- Fair for short
processes.
Disadvantages
- Starvation: Long jobs may wait indefinitely.
- Burst time
prediction is difficult in
practice.
- More complex than
FCFS.
No comments:
Post a Comment