Operating systems _MCA_Mangalore_University_1st Sem
VenugopalRao1
6 views
113 slides
Aug 05, 2024
Slide 1 of 113
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
About This Presentation
This file is the PPT of the Operating systems for MCA under Mangalore Uniresity
Slide Content
Venugopala Rao A S
Head –Computer Applications Department
PIM Udupi
Operating Systems
MCAH102
Head –Computer Applications Department
PIM Udupi
Operating Systems
MCAH102
Unit 2
•CPU Scheduling:
•Scheduling Criteria,
•Scheduling Algorithms,
•Thread Scheduling,
•Multiprocessor Scheduling,
•Real-Time Scheduling,
•Linux Scheduling,
•Windows Vista Scheduling.
•Virtual Memory:
•Hardware and Control Structures,
•Operating System Software,
•UNIX and Solaris Memory
Management,
•Linux Memory Management,
•Windows Vista Memory Management
19-05-2024 PIM, Udupi 2
•CPU Scheduling:
•Scheduling Criteria,
•Scheduling Algorithms,
•Thread Scheduling,
•Multiprocessor Scheduling,
•Real-Time Scheduling,
•Linux Scheduling,
•Windows Vista Scheduling.
•Virtual Memory:
•Hardware and Control Structures,
•Operating System Software,
•UNIX and Solaris Memory
Management,
•Linux Memory Management,
•Windows Vista Memory Management
19-05-2024 PIM, Udupi 2
CPU Scheduling
•What is CPU scheduling?
•Scheduling of processes/work is done to finish the work on time.
•CPU Scheduling is a process that allows one process to use the CPU while another
process is delayed (in standby) due to unavailability of any resources such as I / O
etc, thus making full use of the CPU.
•In short, CPU scheduling decides the order and priority of the processes to run and
allocates the CPU time based on various parameters such as CPU usage,
throughput, waiting time, and response time.
•The purpose of CPU Scheduling is to make the system more efficient, faster, and
fairer..
19-05-2024 PIM, Udupi 3
•What is CPU scheduling?
•Scheduling of processes/work is done to finish the work on time.
•CPU Scheduling is a process that allows one process to use the CPU while another
process is delayed (in standby) due to unavailability of any resources such as I / O
etc, thus making full use of the CPU.
•In short, CPU scheduling decides the order and priority of the processes to run and
allocates the CPU time based on various parameters such as CPU usage,
throughput, waiting time, and response time.
•The purpose of CPU Scheduling is to make the system more efficient, faster, and
fairer..
19-05-2024 PIM, Udupi 3
CPU Scheduling
•CPU scheduling is essential for the system’s performance and ensures that
processes are executed correctly and on time.
•Each CPU scheduling algorithms has a set of properties and the choice of a
particular algorithm depends on various factors.
•Criteria of CPU Scheduling
•Many criteria have been suggested for comparing CPU scheduling algorithms
•CPU utilization
•The main objective of any CPU scheduling algorithm is to keep the CPU busy.
•Theoretically, CPU utilization can range from 0 to 100% but in a real-time system,
it varies from 40 to 90% depending on the load upon the system. .
19-05-2024 PIM, Udupi 4
•CPU scheduling is essential for the system’s performance and ensures that
processes are executed correctly and on time.
•Each CPU scheduling algorithms has a set of properties and the choice of a
particular algorithm depends on various factors.
•Criteria of CPU Scheduling
•Many criteria have been suggested for comparing CPU scheduling algorithms
•CPU utilization
•The main objective of any CPU scheduling algorithm is to keep the CPU busy.
•Theoretically, CPU utilization can range from 0 to 100% but in a real-time system,
it varies from 40 to 90% depending on the load upon the system. .
19-05-2024 PIM, Udupi 4
CPU Scheduling
•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..
•Turnaround Time
•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.
19-05-2024 PIM, Udupi 5
•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..
•Turnaround Time
•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.
19-05-2024 PIM, Udupi 5
CPU Scheduling
•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.
19-05-2024 PIM, Udupi 6
•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.
19-05-2024 PIM, Udupi 6
CPU Scheduling
•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.
•Priority
•If the operating system assigns priorities to processes, the scheduling mechanism
should favor the higher-priority processes.
•These criteria can be categorized along two dimensions -user-orientedand
system-orientedcriteria
•User oriented criteria relate to the behavior of the system as perceived by the
individual user or process
•E.g.: response time
19-05-2024 PIM, Udupi 7
•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.
•Priority
•If the operating system assigns priorities to processes, the scheduling mechanism
should favor the higher-priority processes.
•These criteria can be categorized along two dimensions -user-orientedand
system-orientedcriteria
•User oriented criteria relate to the behavior of the system as perceived by the
individual user or process
•E.g.: response time
19-05-2024 PIM, Udupi 7
CPU Scheduling
•System oriented -focus is on effective and efficient utilization of the processor.
•E.g.: Throughput
•The rate at which processes are completed.
•This is a measure of system performance and one we would like to maximize.
•It focuses on system performance rather than service provided to the user.
•Thus, throughput is of concern to a system administrator but not to the user
population.
•User-oriented criteria are important on all systems, system-oriented criteria are of
less importance on single-user systems.
19-05-2024 PIM, Udupi 8
•System oriented -focus is on effective and efficient utilization of the processor.
•E.g.: Throughput
•The rate at which processes are completed.
•This is a measure of system performance and one we would like to maximize.
•It focuses on system performance rather than service provided to the user.
•Thus, throughput is of concern to a system administrator but not to the user
population.
•User-oriented criteria are important on all systems, system-oriented criteria are of
less importance on single-user systems.
19-05-2024 PIM, Udupi 8
CPU Scheduling
•Types of Scheduling.
•Long-term scheduling -The decision to add to the pool of processes to be
executed
•Medium-term schedulingThe decision to add to the number of processes that are
partially or fully in main memory
•Short-term schedulingThe decision as to which available process will be executed
by the processor
•I/O schedulingThe decision as to which process’s pending I/O request shall be
handled by an available I/O device
19-05-2024 PIM, Udupi 9
•Types of Scheduling.
•Long-term scheduling -The decision to add to the pool of processes to be
executed
•Medium-term schedulingThe decision to add to the number of processes that are
partially or fully in main memory
•Short-term schedulingThe decision as to which available process will be executed
by the processor
•I/O schedulingThe decision as to which process’s pending I/O request shall be
handled by an available I/O device
19-05-2024 PIM, Udupi 9
CPU Scheduling
•Factors Influencing CPU Scheduling Algorithms
•There are many factors that influence the choice of CPU scheduling algorithm as
listed below
•The number of processes.
•The processing time required.
•The urgency of tasks.
•The system requirements.
•Selecting the correct algorithm will ensure that the system will use system
resources efficiently, increase productivity, and improve user satisfaction.
19-05-2024 PIM, Udupi 10
•Factors Influencing CPU Scheduling Algorithms
•There are many factors that influence the choice of CPU scheduling algorithm as
listed below
•The number of processes.
•The processing time required.
•The urgency of tasks.
•The system requirements.
•Selecting the correct algorithm will ensure that the system will use system
resources efficiently, increase productivity, and improve user satisfaction.
19-05-2024 PIM, Udupi 10
CPU Scheduling
•FIRST-COME-FIRST-SERVED
•The simplest scheduling policy is first-come-first-served (FCFS), also known as
first-in-first-out (FIFO) or a strict queuing scheme.
•As each process becomes ready, it joins the ready queue.
•When the currently running process ceases to execute, the process that has been in
the ready queue the longest is selected for running.
•FCFS performs much better for long processes than short ones
•The average waiting time under the FCFS is often quite long
•Consider the following set of processes that arrive at time 0, with the length of the
CPU-burst time given in milliseconds:
19-05-2024 PIM, Udupi 11
•FIRST-COME-FIRST-SERVED
•The simplest scheduling policy is first-come-first-served (FCFS), also known as
first-in-first-out (FIFO) or a strict queuing scheme.
•As each process becomes ready, it joins the ready queue.
•When the currently running process ceases to execute, the process that has been in
the ready queue the longest is selected for running.
•FCFS performs much better for long processes than short ones
•The average waiting time under the FCFS is often quite long
•Consider the following set of processes that arrive at time 0, with the length of the
CPU-burst time given in milliseconds:
19-05-2024 PIM, Udupi 11
CPU Scheduling
•If the processes arrive in the order P1, P2, P3, and are served in FCFS order, we
get the result shown in the following Gantt chart:
•The waiting time is 0 milliseconds for process P1, 24 milliseconds for process P2,
and 27 milliseconds for process P3.
•Thus, the average waiting time is (0 + 24 + 27)/3 = 17 milliseconds.
19-05-2024 PIM, Udupi 12
•If the processes arrive in the order P1, P2, P3, and are served in FCFS order, we
get the result shown in the following Gantt chart:
•The waiting time is 0 milliseconds for process P1, 24 milliseconds for process P2,
and 27 milliseconds for process P3.
•Thus, the average waiting time is (0 + 24 + 27)/3 = 17 milliseconds.
19-05-2024 PIM, Udupi 12
CPU Scheduling
•If the processes arrive in the order P2, P3, Pl, the results will be as shown in the
following Gantt chart:.
•The average waiting time is now (0 + 3 + 4)/3 = 2.1 milliseconds.
•This reduction is substantial.
•Thus, the average waiting time under a FCFS policy is generally not minimal, and
may vary substantially if the process CPU-burst times vary greatly.
•The FCFS scheduling algorithm is non-preemptive.
•Once the CPU has been allocated to a process, that process keeps the CPU until it
releases the CPU, either by terminating or by requesting I/O.
19-05-2024 PIM, Udupi 13
•If the processes arrive in the order P2, P3, Pl, the results will be as shown in the
following Gantt chart:.
•The average waiting time is now (0 + 3 + 4)/3 = 2.1 milliseconds.
•This reduction is substantial.
•Thus, the average waiting time under a FCFS policy is generally not minimal, and
may vary substantially if the process CPU-burst times vary greatly.
•The FCFS scheduling algorithm is non-preemptive.
•Once the CPU has been allocated to a process, that process keeps the CPU until it
releases the CPU, either by terminating or by requesting I/O.
19-05-2024 PIM, Udupi 13
CPU Scheduling
•Shortest-Job-First Scheduling
•The shortest job first (SJF) is a scheduling policy that selects the waiting process
with the smallest execution time to execute next.
•SJF scheduling algorithm associates with each process, the length of its next CPU
burst and use these lengths to schedule the process with the shortest time.
•When the CPU is available, it is assigned to the process that has the smallest next
CPU burst.
•If two processes have the same length next CPU burst, FCFS scheduling is used to
break the tie.
•The scheduling is done by examining the length of the next CPU burst of a
process, rather than its total length.
19-05-2024 PIM, Udupi 14
•Shortest-Job-First Scheduling
•The shortest job first (SJF) is a scheduling policy that selects the waiting process
with the smallest execution time to execute next.
•SJF scheduling algorithm associates with each process, the length of its next CPU
burst and use these lengths to schedule the process with the shortest time.
•When the CPU is available, it is assigned to the process that has the smallest next
CPU burst.
•If two processes have the same length next CPU burst, FCFS scheduling is used to
break the tie.
•The scheduling is done by examining the length of the next CPU burst of a
process, rather than its total length.
19-05-2024 PIM, Udupi 14
CPU Scheduling
•As an example, consider the following set of processes, with the length of the
CPU-burst time given in milliseconds:
19-05-2024 PIM, Udupi 15
•As an example, consider the following set of processes, with the length of the
CPU-burst time given in milliseconds:
19-05-2024 PIM, Udupi 15
CPU Scheduling
•.
19-05-2024 PIM, Udupi 16
•.
19-05-2024 PIM, Udupi 16
CPU Scheduling
•The waiting time is
•0 milliseconds for process P4
•3 milliseconds for process P1,
•9 milliseconds for process P3, and
•16 milliseconds for process P2.
•Thus, the average waiting time is (3 + 16 + 9 + 0)/4 = 7 milliseconds.
•If we were using the FCFS scheduling scheme, then the average waiting time
would be 10.25 milliseconds..
19-05-2024 PIM, Udupi 17
•The waiting time is
•0 milliseconds for process P4
•3 milliseconds for process P1,
•9 milliseconds for process P3, and
•16 milliseconds for process P2.
•Thus, the average waiting time is (3 + 16 + 9 + 0)/4 = 7 milliseconds.
•If we were using the FCFS scheduling scheme, then the average waiting time
would be 10.25 milliseconds..
19-05-2024 PIM, Udupi 17
CPU Scheduling
•Working of Non-Preemptive Shortest Job First CPU Scheduling Algorithm:
•Consider the following table of arrival time and burst time for five processes P1,
P2, P3, P4 and P5.
19-05-2024 PIM, Udupi 18
•Working of Non-Preemptive Shortest Job First CPU Scheduling Algorithm:
•Consider the following table of arrival time and burst time for five processes P1,
P2, P3, P4 and P5.
19-05-2024 PIM, Udupi 18
CPU Scheduling
•The Shortest Job First CPU Scheduling Algorithm will work on the basis of steps
as mentioned below:
•At time = 0 Process P4 arrives and starts executing.
•At time= 1, Process P3 arrives.
•But, as P4 still needs 2 execution units to complete.
•Thus, P3 will wait till P4 gets executed.
19-05-2024 PIM, Udupi 19
•The Shortest Job First CPU Scheduling Algorithm will work on the basis of steps
as mentioned below:
•At time = 0 Process P4 arrives and starts executing.
•At time= 1, Process P3 arrives.
•But, as P4 still needs 2 execution units to complete.
•Thus, P3 will wait till P4 gets executed.
19-05-2024 PIM, Udupi 19
CPU Scheduling
•At time =2,
•Process P1 arrives and is added to the waiting table, P4 will continue its execution.
19-05-2024 PIM, Udupi 20
•At time =2,
•Process P1 arrives and is added to the waiting table, P4 will continue its execution.
19-05-2024 PIM, Udupi 20
CPU Scheduling
•At time = 3,
•Process P4 will finish its execution.
•Then, the burst time of P3 and P1 is compared.
•Process P1 is executed because its burst time is less as compared to P3.
19-05-2024 PIM, Udupi 21
•At time = 3,
•Process P4 will finish its execution.
•Then, the burst time of P3 and P1 is compared.
•Process P1 is executed because its burst time is less as compared to P3.
19-05-2024 PIM, Udupi 21
CPU Scheduling
•At time = 4,
•Process P5 arrives and is added to the waiting Table. P1 will continue execution.
19-05-2024 PIM, Udupi 22
•At time = 4,
•Process P5 arrives and is added to the waiting Table. P1 will continue execution.
19-05-2024 PIM, Udupi 22
CPU Scheduling
•At time = 5,
•Process P2 arrives and is added to the waiting Table. P1 will continue execution.
19-05-2024 PIM, Udupi 23
•At time = 5,
•Process P2 arrives and is added to the waiting Table. P1 will continue execution.
19-05-2024 PIM, Udupi 23
CPU Scheduling
•At time = 6-9
•Process P1 will finish its execution. The burst time of P3, P5, and P2 is compared.
•Process P2 is executed because its burst time is the lowest among all.
19-05-2024 PIM, Udupi 24
•At time = 6-9
•Process P1 will finish its execution. The burst time of P3, P5, and P2 is compared.
•Process P2 is executed because its burst time is the lowest among all.
19-05-2024 PIM, Udupi 24
CPU Scheduling
•At time=9,
•Process P2 is executing and P3 and P5 are in the waiting Table.
19-05-2024 PIM, Udupi 25
•At time=9,
•Process P2 is executing and P3 and P5 are in the waiting Table.
19-05-2024 PIM, Udupi 25
CPU Scheduling
•At time = 11,
•The execution of P2 will be done. The burst time of P3 and P5 is compared.
•Process P5 is executed because its burst time is lower than P3.
19-05-2024 PIM, Udupi 26
•At time = 11,
•The execution of P2 will be done. The burst time of P3 and P5 is compared.
•Process P5 is executed because its burst time is lower than P3.
19-05-2024 PIM, Udupi 26
CPU Scheduling
•At time = 15,
•Process P5 will finish its execution.
•At time = 23,
•Process P3 will finish its execution.
•The overall execution of the processes will be as shown below:
19-05-2024 PIM, Udupi 27
•At time = 15,
•Process P5 will finish its execution.
•At time = 23,
•Process P3 will finish its execution.
•The overall execution of the processes will be as shown below:
19-05-2024 PIM, Udupi 27
CPU Scheduling
•Gantt chart for above execution is as shown below
•Average waiting time
•P4 0 –0 = 0
•P1 3 –2 = 1
•P2 9 –5 = 4
•P5 11 –4 = 7
•P3 15 –1 = 14
•Average Waiting Time = 0 + 1 + 4 + 7 + 14/5 = 26/5 = 5.2
19-05-2024 PIM, Udupi 28
•Gantt chart for above execution is as shown below
•Average waiting time
•P4 0 –0 = 0
•P1 3 –2 = 1
•P2 9 –5 = 4
•P5 11 –4 = 7
•P3 15 –1 = 14
•Average Waiting Time = 0 + 1 + 4 + 7 + 14/5 = 26/5 = 5.2
19-05-2024 PIM, Udupi 28
CPU Scheduling
•Shortest-remaining-time-first scheduling.
•The SJF algorithm may be either preemptive or non-preemptive.
•The choice arises when a new process arrives at the ready queue while a previous
process is executing.
•The new process may have a shorter next CPU burst than what is left of the
currently executing process.
•A preemptive SJF algorithm will preempt the currently executing process, whereas
a non-preemptive SJF algorithm will allow the currently running process to finish
its CPU burst.
19-05-2024 PIM, Udupi 29
•Shortest-remaining-time-first scheduling.
•The SJF algorithm may be either preemptive or non-preemptive.
•The choice arises when a new process arrives at the ready queue while a previous
process is executing.
•The new process may have a shorter next CPU burst than what is left of the
currently executing process.
•A preemptive SJF algorithm will preempt the currently executing process, whereas
a non-preemptive SJF algorithm will allow the currently running process to finish
its CPU burst.
19-05-2024 PIM, Udupi 29
CPU Scheduling
•Preemptive SJF scheduling is called shortest-remaining-time-firstscheduling.
19-05-2024 PIM, Udupi 30
•Preemptive SJF scheduling is called shortest-remaining-time-firstscheduling.
19-05-2024 PIM, Udupi 30
CPU Scheduling
•If the same jobs scheduled using SJN.
19-05-2024 PIM, Udupi 31
•If the same jobs scheduled using SJN.
19-05-2024 PIM, Udupi 31
CPU Scheduling
•Longest Job First (LJF) CPU Scheduling:
•This is a non-preemptive scheduling algorithm.
•This algorithm is based on the burst time of the processes.
•The processes are put into the ready queue based on descending order of the burst
times.
•The process with the largest burst time is processed first.
•The burst time of only those processes is considered that have arrived in the
system until that time.
•Its preemptive version is called Longest Remaining Time First (LRTF) algorithm
19-05-2024 PIM, Udupi 32
•Longest Job First (LJF) CPU Scheduling:
•This is a non-preemptive scheduling algorithm.
•This algorithm is based on the burst time of the processes.
•The processes are put into the ready queue based on descending order of the burst
times.
•The process with the largest burst time is processed first.
•The burst time of only those processes is considered that have arrived in the
system until that time.
•Its preemptive version is called Longest Remaining Time First (LRTF) algorithm
19-05-2024 PIM, Udupi 32
CPU Scheduling
•Consider the following table of arrival time and burst time for four processes P1,
P2, P3 and P4.
•At time = 1, Available Process : P1. So, select P1 and start executing.
19-05-2024 PIM, Udupi 33
ProcessesArrival time Burst Time
P1 1 ms 2 ms
P2 2 ms 4 ms
P3 3 ms 6 ms
P4 4 ms 8 ms
•Consider the following table of arrival time and burst time for four processes P1,
P2, P3 and P4.
•At time = 1, Available Process : P1. So, select P1 and start executing.
19-05-2024 PIM, Udupi 33
ProcessesArrival time Burst Time
P1 1 ms 2 ms
P2 2 ms 4 ms
P3 3 ms 6 ms
P4 4 ms 8 ms
CPU Scheduling
•At time = 2,
•Process P2 arrives As P1 is executing, Process P2 will wait in the waiting queue.
19-05-2024 PIM, Udupi 34
•At time = 2,
•Process P2 arrives As P1 is executing, Process P2 will wait in the waiting queue.
19-05-2024 PIM, Udupi 34
CPU Scheduling
•At time = 3,
•P1 gets executed, and process P3 arrives
•Available Process: P2, P3. So, select P3 and execute 6 ms(since B.T(P3)=6 which
is higher than B.T(P2) = 4)
19-05-2024 PIM, Udupi 35
•At time = 3,
•P1 gets executed, and process P3 arrives
•Available Process: P2, P3. So, select P3 and execute 6 ms(since B.T(P3)=6 which
is higher than B.T(P2) = 4)
19-05-2024 PIM, Udupi 35
CPU Scheduling
•At time = 4,
•Process P4 arrives, As P3 is executing, Process P4 will wait in the waiting queue.
19-05-2024 PIM, Udupi 36
•At time = 4,
•Process P4 arrives, As P3 is executing, Process P4 will wait in the waiting queue.
19-05-2024 PIM, Udupi 36
CPU Scheduling
•Priority CPU Scheduling
•Priority scheduling is one of the most common scheduling algorithms in batch
systems.
•Each process is assigned a priority. The process with the highest priority is to be
executed first and so on.
•Processes with the same priority are executed on a first-come first served basis.
•Priority can be decided based on memory requirements, time requirements or any
other resource requirement.
•Also priority can be decided on the ratio of average I/O to average CPU burst
time.
19-05-2024 PIM, Udupi 37
•Priority CPU Scheduling
•Priority scheduling is one of the most common scheduling algorithms in batch
systems.
•Each process is assigned a priority. The process with the highest priority is to be
executed first and so on.
•Processes with the same priority are executed on a first-come first served basis.
•Priority can be decided based on memory requirements, time requirements or any
other resource requirement.
•Also priority can be decided on the ratio of average I/O to average CPU burst
time.
19-05-2024 PIM, Udupi 37
CPU Scheduling
•The SJF algorithm is a special case of the general priority-scheduling algorithm.
•A priority is associated with each process, and the CPU is allocated to the process
with the highest priority.
•Equal-priority processes are scheduled in FCFS order.
•An SJF algorithm is simply a priority algorithm where the priority (P) is the
inverse of the (predicted) next CPU burst.
•The larger the CPU burst, the lower the priority, and vice versa.
•consider the following set of processes, assumed to have arrived at time 0, in the
order PI, P2, ..., P5, with the length of the CPU-burst time given in milliseconds:
19-05-2024 PIM, Udupi 38
•The SJF algorithm is a special case of the general priority-scheduling algorithm.
•A priority is associated with each process, and the CPU is allocated to the process
with the highest priority.
•Equal-priority processes are scheduled in FCFS order.
•An SJF algorithm is simply a priority algorithm where the priority (P) is the
inverse of the (predicted) next CPU burst.
•The larger the CPU burst, the lower the priority, and vice versa.
•consider the following set of processes, assumed to have arrived at time 0, in the
order PI, P2, ..., P5, with the length of the CPU-burst time given in milliseconds:
19-05-2024 PIM, Udupi 38
CPU Scheduling
•.
•Using priority scheduling, we would schedule these processes according to the
following Gantt chart:
•The average waiting time is = (6+0+16+18+1)/5 = 41/5 = 8.2 milliseconds.
19-05-2024 PIM, Udupi 39
ProcessBurst timePriority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
P2P5 P1 P3P4
•.
•Using priority scheduling, we would schedule these processes according to the
following Gantt chart:
•The average waiting time is = (6+0+16+18+1)/5 = 41/5 = 8.2 milliseconds.
19-05-2024 PIM, Udupi 39
ProcessBurst timePriority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
P2P5 P1 P3P4
CPU Scheduling
•Round Robin Scheduling.
•The round-robin (RR) scheduling algorithm is designed for timesharing systems.
•It is similar to FCFS scheduling, but preemption is added to switch between
processes.
•A small unit of time, called a time quantum (or time slice), is defined.
•A time quantum is generally from 10 to 100 milliseconds.
•The ready queue is treated as a circular queue.
•The CPU scheduler goes around the ready queue, allocating the CPU to each
process for a time interval of up to 1 time quantum.
19-05-2024 PIM, Udupi 40
•Round Robin Scheduling.
•The round-robin (RR) scheduling algorithm is designed for timesharing systems.
•It is similar to FCFS scheduling, but preemption is added to switch between
processes.
•A small unit of time, called a time quantum (or time slice), is defined.
•A time quantum is generally from 10 to 100 milliseconds.
•The ready queue is treated as a circular queue.
•The CPU scheduler goes around the ready queue, allocating the CPU to each
process for a time interval of up to 1 time quantum.
19-05-2024 PIM, Udupi 40
CPU Scheduling
•To implement RR scheduling, we keep the ready queue as a FIFO queue of
processes.
•New processes are added to the tail of the ready queue.
•The CPU scheduler picks the first process from the ready queue, sets a timer to
interrupt after 1 time quantum, and dispatches the process
•Consider the following table of arrival time and burst time for four processes P1,
P2, P3, and P4 and given Time Quantum = 2
19-05-2024 PIM, Udupi 41
•To implement RR scheduling, we keep the ready queue as a FIFO queue of
processes.
•New processes are added to the tail of the ready queue.
•The CPU scheduler picks the first process from the ready queue, sets a timer to
interrupt after 1 time quantum, and dispatches the process
•Consider the following table of arrival time and burst time for four processes P1,
P2, P3, and P4 and given Time Quantum = 2
19-05-2024 PIM, Udupi 41
CPU Scheduling
•At time = 0,
•The execution begins with process P1, which has burst time 5.
•Every process executes for 2 milliseconds (Time Quantum Period). P2 and P3 are
still in the waiting queue.
19-05-2024 PIM, Udupi 42
•At time = 0,
•The execution begins with process P1, which has burst time 5.
•Every process executes for 2 milliseconds (Time Quantum Period). P2 and P3 are
still in the waiting queue.
19-05-2024 PIM, Udupi 42
CPU Scheduling
•At time = 2,
•The processes P1 and P3 arrives in the ready queue and P2 starts executing for TQ
period
19-05-2024 PIM, Udupi 43
•At time = 2,
•The processes P1 and P3 arrives in the ready queue and P2 starts executing for TQ
period
19-05-2024 PIM, Udupi 43
CPU Scheduling
•At time = 4,
•The process P4 arrives in the ready queue, Then P3 executes for TQ period..
19-05-2024 PIM, Udupi 44
•At time = 4,
•The process P4 arrives in the ready queue, Then P3 executes for TQ period..
19-05-2024 PIM, Udupi 44
CPU Scheduling
•At time = 6,
•Process P3 completes its execution. P1 starts executing for TQ period as it is next
in the b.
19-05-2024 PIM, Udupi 45
•At time = 6,
•Process P3 completes its execution. P1 starts executing for TQ period as it is next
in the b.
19-05-2024 PIM, Udupi 45
CPU Scheduling
•At time = 8,
•Process P4 starts executing, it will not execute for Time Quantum period as it has
burst time = 1. Hence, it will execute for only 1ms.
19-05-2024 PIM, Udupi 46
•At time = 8,
•Process P4 starts executing, it will not execute for Time Quantum period as it has
burst time = 1. Hence, it will execute for only 1ms.
19-05-2024 PIM, Udupi 46
CPU Scheduling
•At time = 9,
•Process P4 completes its execution. P2 starts executing for TQ period as it is next
in the ready queue
19-05-2024 PIM, Udupi 47
•At time = 9,
•Process P4 completes its execution. P2 starts executing for TQ period as it is next
in the ready queue
19-05-2024 PIM, Udupi 47
CPU Scheduling
•At time = 11,
•P2 completes its execution. P1 starts executing, it will execute for 1ms only
19-05-2024 PIM, Udupi 48
•At time = 11,
•P2 completes its execution. P1 starts executing, it will execute for 1ms only
19-05-2024 PIM, Udupi 48
CPU Scheduling
•At time = 12,
•Process P1 completes its execution.
•Gantt chart will be as following below:
19-05-2024 PIM, Udupi 49
•At time = 12,
•Process P1 completes its execution.
•Gantt chart will be as following below:
19-05-2024 PIM, Udupi 49
CPU Scheduling
•Multilevel Queue Scheduling
•Another class of scheduling algorithms has been created for situations in which
processes are easily classified into different groups.
•For example, a common division is made between foreground (interactive)
processesand background (batch) processes.
•These two types of processes have different response-time requirements and so
may have different scheduling needs.
•In addition, foreground processes may have priority (externally defined) over
background processes.
•A multilevel queue scheduling algorithm partitions the ready queue into several
separate queues
19-05-2024 PIM, Udupi 50
•Multilevel Queue Scheduling
•Another class of scheduling algorithms has been created for situations in which
processes are easily classified into different groups.
•For example, a common division is made between foreground (interactive)
processesand background (batch) processes.
•These two types of processes have different response-time requirements and so
may have different scheduling needs.
•In addition, foreground processes may have priority (externally defined) over
background processes.
•A multilevel queue scheduling algorithm partitions the ready queue into several
separate queues
19-05-2024 PIM, Udupi 50
CPU Scheduling
•The processes are permanently assigned to one queue, generally based on some property
of the process, such as memory size, process priority, or process type.
•Each queue has its own scheduling algorithm.
•E.g.: Separate queues might be used for foreground and background processes.
•The foreground queue might be scheduled by an RR algorithm, while the background
queue is scheduled by an FCFS algorithm.
•In addition, there must be scheduling among the queues, which is commonly
implemented as fixed-priority preemptive scheduling.
•For example, the foreground queue may have absolute priority over the background
queue
19-05-2024 PIM, Udupi 51
•The processes are permanently assigned to one queue, generally based on some property
of the process, such as memory size, process priority, or process type.
•Each queue has its own scheduling algorithm.
•E.g.: Separate queues might be used for foreground and background processes.
•The foreground queue might be scheduled by an RR algorithm, while the background
queue is scheduled by an FCFS algorithm.
•In addition, there must be scheduling among the queues, which is commonly
implemented as fixed-priority preemptive scheduling.
•For example, the foreground queue may have absolute priority over the background
queue
19-05-2024 PIM, Udupi 51
CPU Scheduling
•Let's look at an example of a multilevel queue scheduling algorithm with five
queues, listed below in order of priority:
•System processes
•Interactive processes
•Interactive editing processes
•Batch processes
•Student processes
•Every queue would have an absolute priority over the low-priority queues.
•No process may execute until the high-priority queues are empty.
•In the above instance, no other process may execute until and unless the queues
for system, interactive, and editing processes are empty.
19-05-2024 PIM, Udupi 52
•Let's look at an example of a multilevel queue scheduling algorithm with five
queues, listed below in order of priority:
•System processes
•Interactive processes
•Interactive editing processes
•Batch processes
•Student processes
•Every queue would have an absolute priority over the low-priority queues.
•No process may execute until the high-priority queues are empty.
•In the above instance, no other process may execute until and unless the queues
for system, interactive, and editing processes are empty.
19-05-2024 PIM, Udupi 52
CPU Scheduling
•If an interactive editing process enters the ready queue while a batch process is
underway, the batch process will be preempted.
•Processes that are used in the above example:
•System Process-The OS has its process to execute, which is referred to as the
System Process.
•Interactive Process-It is a process in which the same type of interaction should
occur.
•Batch Process-Batch processing is an operating system feature that collects
programs and data into a batch before processing starts.
•Student Process-The system process is always given the highest priority, whereas
the student processes are always given the lowest.
19-05-2024 PIM, Udupi 53
•If an interactive editing process enters the ready queue while a batch process is
underway, the batch process will be preempted.
•Processes that are used in the above example:
•System Process-The OS has its process to execute, which is referred to as the
System Process.
•Interactive Process-It is a process in which the same type of interaction should
occur.
•Batch Process-Batch processing is an operating system feature that collects
programs and data into a batch before processing starts.
•Student Process-The system process is always given the highest priority, whereas
the student processes are always given the lowest.
19-05-2024 PIM, Udupi 53
CPU Scheduling
•Multilevel Feedback Queue Scheduling (MLFQ) CPU Scheduling:
•This is like Multilevel Queue(MLQ) Scheduling but in this process can move
between the queues thus, much more efficient than multilevel queue scheduling.
•Features of Multilevel Feedback Queue Scheduling (MLFQ) CPU Scheduling:
•Multiple queues: Similar to MLQ scheduling, MLFQ scheduling divides processes
into multiple queues based on their priority levels.
•However, unlike MLQ scheduling, processes can move between queues based on
their behaviour and needs.
19-05-2024 PIM, Udupi 54
•Multilevel Feedback Queue Scheduling (MLFQ) CPU Scheduling:
•This is like Multilevel Queue(MLQ) Scheduling but in this process can move
between the queues thus, much more efficient than multilevel queue scheduling.
•Features of Multilevel Feedback Queue Scheduling (MLFQ) CPU Scheduling:
•Multiple queues: Similar to MLQ scheduling, MLFQ scheduling divides processes
into multiple queues based on their priority levels.
•However, unlike MLQ scheduling, processes can move between queues based on
their behaviour and needs.
19-05-2024 PIM, Udupi 54
CPU Scheduling
•consider a multilevel feedback queue scheduler with three queues, numbered from
1 to 3.
•The scheduler first executes all processes in queue 1.
•Only when queue 1 is empty will it execute processes in queue 2
•Similarly, processes in queue 3will only be executed if queues 1and 2 are empty.
•A process that arrives for queue 2 will preempt a process in queue 3.
•A process in queue 2 will in turn be preempted by a process arriving for queue 1.
19-05-2024 PIM, Udupi 55
•consider a multilevel feedback queue scheduler with three queues, numbered from
1 to 3.
•The scheduler first executes all processes in queue 1.
•Only when queue 1 is empty will it execute processes in queue 2
•Similarly, processes in queue 3will only be executed if queues 1and 2 are empty.
•A process that arrives for queue 2 will preempt a process in queue 3.
•A process in queue 2 will in turn be preempted by a process arriving for queue 1.
19-05-2024 PIM, Udupi 55
CPU Scheduling
•A process entering the ready queue is put in queue 1.
•A process in queue 1 is given a time quantum of 8 milliseconds. If it does not
finish within this time, it is moved to the tail of queue 2.
•If queue 1 is empty, the process at the head of queue 2 is given a quantum of 16
milliseconds.
•If it does not complete, it is preempted and is put into queue 3.
•Processes in queue 3 are run on an FCFS basis but are run only when queues 1 and
2 are empty.
19-05-2024 PIM, Udupi 56
•A process entering the ready queue is put in queue 1.
•A process in queue 1 is given a time quantum of 8 milliseconds. If it does not
finish within this time, it is moved to the tail of queue 2.
•If queue 1 is empty, the process at the head of queue 2 is given a quantum of 16
milliseconds.
•If it does not complete, it is preempted and is put into queue 3.
•Processes in queue 3 are run on an FCFS basis but are run only when queues 1 and
2 are empty.
19-05-2024 PIM, Udupi 56
CPU Scheduling
•This scheduling algorithm gives highest priority to any process with a CPU burst
of 8 milliseconds or less.
•Such a process will quickly get the CPU, finish its CPU burst, and go off to its
next I/0 burst.
•Processes that need more than 8 but less than 24 milliseconds are also served but
with lower priority than shorter processes.
•Long processes automatically sink to queue 3 and are served in FCFS order with
any CPU cycles left over from queues 1and 2.
19-05-2024 PIM, Udupi 57
•This scheduling algorithm gives highest priority to any process with a CPU burst
of 8 milliseconds or less.
•Such a process will quickly get the CPU, finish its CPU burst, and go off to its
next I/0 burst.
•Processes that need more than 8 but less than 24 milliseconds are also served but
with lower priority than shorter processes.
•Long processes automatically sink to queue 3 and are served in FCFS order with
any CPU cycles left over from queues 1and 2.
19-05-2024 PIM, Udupi 57
CPU Scheduling
•Multiple Processors Scheduling
•Multiple processor scheduling or multiprocessor scheduling focuses on designing
the system's scheduling function, which consists of more than one processor.
•Multiple CPUs share the load in multiprocessor scheduling so that various
processes run simultaneously.
•In general, multiprocessor scheduling is complex as compared to single processor
scheduling.
•In the multiprocessor scheduling, there are many processors, and they are
identical, and we can run any process at any time
19-05-2024 PIM, Udupi 58
•Multiple Processors Scheduling
•Multiple processor scheduling or multiprocessor scheduling focuses on designing
the system's scheduling function, which consists of more than one processor.
•Multiple CPUs share the load in multiprocessor scheduling so that various
processes run simultaneously.
•In general, multiprocessor scheduling is complex as compared to single processor
scheduling.
•In the multiprocessor scheduling, there are many processors, and they are
identical, and we can run any process at any time
19-05-2024 PIM, Udupi 58
CPU Scheduling
•The multiple CPUs in the system are in close communication, which shares a
common bus, memory, and other peripheral devices.
•So we can say that the system is tightly coupled.
•These systems are usedwhen we want to process a bulk amount of data, and
these systems are mainly used in satellite, weather forecasting, etc.
•Multiprocessor systems may be heterogeneous(different kinds of CPUs) or
homogenous(the same CPU).
•There may be special scheduling constraints, such as devices connected via a
private bus to only one CPU
19-05-2024 PIM, Udupi 59
•The multiple CPUs in the system are in close communication, which shares a
common bus, memory, and other peripheral devices.
•So we can say that the system is tightly coupled.
•These systems are usedwhen we want to process a bulk amount of data, and
these systems are mainly used in satellite, weather forecasting, etc.
•Multiprocessor systems may be heterogeneous(different kinds of CPUs) or
homogenous(the same CPU).
•There may be special scheduling constraints, such as devices connected via a
private bus to only one CPU
19-05-2024 PIM, Udupi 59
CPU Scheduling
•Approaches to Multiple Processor Scheduling
•There are two approaches
•Symmetric Multiprocessing and Asymmetric Multiprocessing.
•Symmetric Multiprocessing:
•It is used where each processor is self-scheduling.
•All processes may be in a common ready queue, or each processor may have its
private queue for ready processes.
•The scheduling proceeds further by having the scheduler for each processor
examine the ready queue and select a process to execute.
19-05-2024 PIM, Udupi 60
•Approaches to Multiple Processor Scheduling
•There are two approaches
•Symmetric Multiprocessing and Asymmetric Multiprocessing.
•Symmetric Multiprocessing:
•It is used where each processor is self-scheduling.
•All processes may be in a common ready queue, or each processor may have its
private queue for ready processes.
•The scheduling proceeds further by having the scheduler for each processor
examine the ready queue and select a process to execute.
19-05-2024 PIM, Udupi 60
CPU Scheduling
•Asymmetric Multiprocessing:
•It is used when all the scheduling decisions and I/O processing are handled by a
single processor called the Master Server.
•The other processors execute only the user code.
•This is simple and reduces the need for data sharing
•Processor Affinity
•When a process runs on a specific processor, there are certain effects on the cache
memory.
•The data most recently accessed by the process gets stored on the cache for the
processor.
•So successive memory access by the process is satisfied in the cache memory.
19-05-2024 PIM, Udupi 61
•Asymmetric Multiprocessing:
•It is used when all the scheduling decisions and I/O processing are handled by a
single processor called the Master Server.
•The other processors execute only the user code.
•This is simple and reduces the need for data sharing
•Processor Affinity
•When a process runs on a specific processor, there are certain effects on the cache
memory.
•The data most recently accessed by the process gets stored on the cache for the
processor.
•So successive memory access by the process is satisfied in the cache memory.
19-05-2024 PIM, Udupi 61
CPU Scheduling
•Suppose the process migrates to another processor.
•In that case, the contents of the cache memory must be nullified for the first
processor, and the cache for the second processor must be repopulated.
•Because of the high cost of invalidating and repopulating caches, most SMP
systems try to avoid migrating processes from one processor to another and keep
a process running on the same processor.
•This is known as processor affinity.
•There are two types of processor affinity –Soft affinity and Hard affinity
19-05-2024 PIM, Udupi 62
•Suppose the process migrates to another processor.
•In that case, the contents of the cache memory must be nullified for the first
processor, and the cache for the second processor must be repopulated.
•Because of the high cost of invalidating and repopulating caches, most SMP
systems try to avoid migrating processes from one processor to another and keep
a process running on the same processor.
•This is known as processor affinity.
•There are two types of processor affinity –Soft affinity and Hard affinity
19-05-2024 PIM, Udupi 62
CPU Scheduling
•Soft Affinity:When an operating system has a policy of keeping a process
running on the same processor but not guaranteeing it will do so, this situation is
called soft affinity.
•Hard Affinity:Hard Affinity allows a process to specify a subset of processors on
which it may run.
•Load Balancing
•Load Balancing is the phenomenon that keeps the workload evenly distributed
across all processors in an SMP system.
•Load balancing is necessary on systems where each processor has its own private
queue of a process that is eligible to execute.
19-05-2024 PIM, Udupi 63
•Soft Affinity:When an operating system has a policy of keeping a process
running on the same processor but not guaranteeing it will do so, this situation is
called soft affinity.
•Hard Affinity:Hard Affinity allows a process to specify a subset of processors on
which it may run.
•Load Balancing
•Load Balancing is the phenomenon that keeps the workload evenly distributed
across all processors in an SMP system.
•Load balancing is necessary on systems where each processor has its own private
queue of a process that is eligible to execute.
19-05-2024 PIM, Udupi 63
CPU Scheduling
•On SMP, it is important to keep the workload balanced among all processors to
fully utilize the benefitsof having more than one processor
•Otherwise one or more processor will sit idle while other processors have high
workloads along with lists of processors awaiting the CPU.
•There are two general approaches to load balancing :
•Push Migration –In push migration a task routinely checks the load on each
processor and if it finds an imbalance then it evenly distributes load on each
processors by moving the processes from overloaded to idle or less busy
processors.
•Pull Migration –Pull Migration occurs when an idle processor pulls a waiting task
from a busy processor for its execution.
19-05-2024 PIM, Udupi 64
•On SMP, it is important to keep the workload balanced among all processors to
fully utilize the benefitsof having more than one processor
•Otherwise one or more processor will sit idle while other processors have high
workloads along with lists of processors awaiting the CPU.
•There are two general approaches to load balancing :
•Push Migration –In push migration a task routinely checks the load on each
processor and if it finds an imbalance then it evenly distributes load on each
processors by moving the processes from overloaded to idle or less busy
processors.
•Pull Migration –Pull Migration occurs when an idle processor pulls a waiting task
from a busy processor for its execution.
19-05-2024 PIM, Udupi 64
CPU Scheduling
•Interestingly, load balancing often counters the benefits of processor affinity.
•That is, the benefit of keeping a process running on the same processor is that the
process can take advantage of its data being in that processor's cache memory.
•Either pulling or pushing a process from one processor to another invalidates this
benefit.
•However there is no absolute rule concerning what policy is best.
•Thus, in some systems, an idle processor always pulls a process from a non-idle
processor; and in other systems, processes are moved only if the imbalance
exceeds a certain threshold.
19-05-2024 PIM, Udupi 65
•Interestingly, load balancing often counters the benefits of processor affinity.
•That is, the benefit of keeping a process running on the same processor is that the
process can take advantage of its data being in that processor's cache memory.
•Either pulling or pushing a process from one processor to another invalidates this
benefit.
•However there is no absolute rule concerning what policy is best.
•Thus, in some systems, an idle processor always pulls a process from a non-idle
processor; and in other systems, processes are moved only if the imbalance
exceeds a certain threshold.
19-05-2024 PIM, Udupi 65
CPU Scheduling
•Multi-core Processors
•Multi-core processors, -multiple processor cores placed on the same IC.
•Each core has a register setto maintain its architectural state and thus appears to
the operating system as a separate physical processor.
•SMP systems that use multi-core processors are faster and consume less power
than systems in which each processor has its own physical chip.
•However, multi-core processors may complicate the scheduling problems.
•When the processor accesses memory, it spends a significant amount of time
waiting for the data to become available.
•This situation is called a Memory stall.
19-05-2024 PIM, Udupi 66
•Multi-core Processors
•Multi-core processors, -multiple processor cores placed on the same IC.
•Each core has a register setto maintain its architectural state and thus appears to
the operating system as a separate physical processor.
•SMP systems that use multi-core processors are faster and consume less power
than systems in which each processor has its own physical chip.
•However, multi-core processors may complicate the scheduling problems.
•When the processor accesses memory, it spends a significant amount of time
waiting for the data to become available.
•This situation is called a Memory stall.
19-05-2024 PIM, Udupi 66
CPU Scheduling
•It occurs for various reasons, such as cache miss, which is accessing the data that
is not in the cache memory.
•In such cases, the processor can spend upto50% of its time waiting for data to
become available from memory.
•To solve this problem, recent hardware designs have implemented multithreaded
processor cores in which two or more hardware threads are assigned to each core.
•Therefore if one thread stallswhile waiting for the memory, the core can switch to
another thread.
•There are two ways to multithread a processor:
•Coarse-Grained Multithreading
•Fine-Grained Multithreading:
19-05-2024 PIM, Udupi 67
•It occurs for various reasons, such as cache miss, which is accessing the data that
is not in the cache memory.
•In such cases, the processor can spend upto50% of its time waiting for data to
become available from memory.
•To solve this problem, recent hardware designs have implemented multithreaded
processor cores in which two or more hardware threads are assigned to each core.
•Therefore if one thread stallswhile waiting for the memory, the core can switch to
another thread.
•There are two ways to multithread a processor:
•Coarse-Grained Multithreading
•Fine-Grained Multithreading:
19-05-2024 PIM, Udupi 67
CPU Scheduling
•Coarse-Grained Multithreading:
•In coarse-grained multithreading, a thread executes on a processor until a long latency
event such as a memory stall occurs.
•Because of the delay caused by the long latency event, the processor must switch to
another thread to begin execution.
•The cost of switching between threads is high as the instruction pipeline must be
terminated before the other thread can begin execution on the processor core.
•Once this new thread begins execution, it begins filling the pipeline with its instructions.
•Fine-Grained Multithreading:This multithreading switches between threads at a much
finer level, mainly at the boundary of an instruction cycle.
•The architectural design of fine-grained systems includes logic for thread switching, and
as a result, the cost of switching between threads is small.
19-05-2024 PIM, Udupi 68
•Coarse-Grained Multithreading:
•In coarse-grained multithreading, a thread executes on a processor until a long latency
event such as a memory stall occurs.
•Because of the delay caused by the long latency event, the processor must switch to
another thread to begin execution.
•The cost of switching between threads is high as the instruction pipeline must be
terminated before the other thread can begin execution on the processor core.
•Once this new thread begins execution, it begins filling the pipeline with its instructions.
•Fine-Grained Multithreading:This multithreading switches between threads at a much
finer level, mainly at the boundary of an instruction cycle.
•The architectural design of fine-grained systems includes logic for thread switching, and
as a result, the cost of switching between threads is small.
19-05-2024 PIM, Udupi 68
CPU Scheduling
•REAL-TIME SCHEDULING:
•Real-time computing is becoming an increasingly important discipline.
•The OS, and in particular the scheduler, is the most important component of a
real-time system.
•Examples control of laboratory experiments, process control in industrial plants,
robotics, air traffic control, telecommunications, and military command and
control systems.
•Next-generation systems will include the autonomous land rover, controllers of
robots with elastic joints, systems found in intelligent manufacturing, the space
station, and undersea exploration
19-05-2024 PIM, Udupi 69
•REAL-TIME SCHEDULING:
•Real-time computing is becoming an increasingly important discipline.
•The OS, and in particular the scheduler, is the most important component of a
real-time system.
•Examples control of laboratory experiments, process control in industrial plants,
robotics, air traffic control, telecommunications, and military command and
control systems.
•Next-generation systems will include the autonomous land rover, controllers of
robots with elastic joints, systems found in intelligent manufacturing, the space
station, and undersea exploration
19-05-2024 PIM, Udupi 69
CPU Scheduling
•REAL-TIME SCHEDULING:
•Real-time computing is becoming an increasingly important discipline.
•The OS, and in particular the scheduler, is the most important component of a
real-time system.
•Examples control of laboratory experiments, process control in industrial plants,
robotics, air traffic control, telecommunications, and military command and
control systems.
•Next-generation systems will include the autonomous land rover, controllers of
robots with elastic joints, systems found in intelligent manufacturing, the space
station, and undersea exploration
19-05-2024 PIM, Udupi 70
•REAL-TIME SCHEDULING:
•Real-time computing is becoming an increasingly important discipline.
•The OS, and in particular the scheduler, is the most important component of a
real-time system.
•Examples control of laboratory experiments, process control in industrial plants,
robotics, air traffic control, telecommunications, and military command and
control systems.
•Next-generation systems will include the autonomous land rover, controllers of
robots with elastic joints, systems found in intelligent manufacturing, the space
station, and undersea exploration
19-05-2024 PIM, Udupi 70
CPU Scheduling
•In real-time computing system, the correctness of the system depends not only on
the logical result of the computation but also on the time at which the results are
produced.
•Real-time systems carry-out -real-time tasks.
•These tasks need to be performed immediately with a certain degree of urgency.
•In particular, these tasks are related to control of certain events (or) reacting to
them.
•Real-time tasks can be classified as hard real-time tasks and soft real-time tasks.
19-05-2024 PIM, Udupi 71
•In real-time computing system, the correctness of the system depends not only on
the logical result of the computation but also on the time at which the results are
produced.
•Real-time systems carry-out -real-time tasks.
•These tasks need to be performed immediately with a certain degree of urgency.
•In particular, these tasks are related to control of certain events (or) reacting to
them.
•Real-time tasks can be classified as hard real-time tasks and soft real-time tasks.
19-05-2024 PIM, Udupi 71
CPU Scheduling
•A hard real-time taskmust be performed at a specified time which could
otherwise lead to huge losses.
•In soft real-time tasks, a specified deadline can be missed. This is because the
task can be rescheduled (or) can be completed after the specified time,
•Another characteristic of real-time tasks is whether they are
•periodicor aperiodic.
•An aperiodic taskhas a deadline by which it must finish or start, or it may have a
constraint on both start and finish time.
•In the case of a periodic task, the requirement may be stated as “once per period
T” or “exactly T units apart.”
19-05-2024 PIM, Udupi 72
•A hard real-time taskmust be performed at a specified time which could
otherwise lead to huge losses.
•In soft real-time tasks, a specified deadline can be missed. This is because the
task can be rescheduled (or) can be completed after the specified time,
•Another characteristic of real-time tasks is whether they are
•periodicor aperiodic.
•An aperiodic taskhas a deadline by which it must finish or start, or it may have a
constraint on both start and finish time.
•In the case of a periodic task, the requirement may be stated as “once per period
T” or “exactly T units apart.”
19-05-2024 PIM, Udupi 72
CPU Scheduling
•In real-time systems, the scheduleris the most important component which is
typically a short-term task scheduler.
•The focus of this scheduler is to reduce the response timeassociated with each of
the associated processes instead of handling the deadline.
•If a preemptive scheduler is used, the real-time task needs to wait until its
corresponding tasks time slice completes.
•In the case of a non-preemptive scheduler, even if the highest priority is allocated
to the task, it needs to wait until the completion of the current task.
•This task can be slow or of the lower priority and can lead to a longer wait.
19-05-2024 PIM, Udupi 73
•In real-time systems, the scheduleris the most important component which is
typically a short-term task scheduler.
•The focus of this scheduler is to reduce the response timeassociated with each of
the associated processes instead of handling the deadline.
•If a preemptive scheduler is used, the real-time task needs to wait until its
corresponding tasks time slice completes.
•In the case of a non-preemptive scheduler, even if the highest priority is allocated
to the task, it needs to wait until the completion of the current task.
•This task can be slow or of the lower priority and can lead to a longer wait.
19-05-2024 PIM, Udupi 73
CPU Scheduling
•A better approach is to design by combining both preemptive and non-preemptive
scheduling.
•This can be done by introducing time-based interrupts in priority based systems
which means the currently running process is interrupted on a time-based interval
and if a higher priority process is present in a ready queue, it is executed by
preempting the current process.
•Based on schedulability, implementation (static or dynamic), and the result (self or
dependent) of analysis, the scheduling algorithm are classified as follows.
19-05-2024 PIM, Udupi 74
•A better approach is to design by combining both preemptive and non-preemptive
scheduling.
•This can be done by introducing time-based interrupts in priority based systems
which means the currently running process is interrupted on a time-based interval
and if a higher priority process is present in a ready queue, it is executed by
preempting the current process.
•Based on schedulability, implementation (static or dynamic), and the result (self or
dependent) of analysis, the scheduling algorithm are classified as follows.
19-05-2024 PIM, Udupi 74
CPU Scheduling
•Static table-driven approaches:
•These algorithms usually perform a static analysis associated with scheduling and
capture the schedules that are advantageous.
•This helps in providing a schedule that can point out a task with which the execution
must be started at run time.
•These are applicable to tasks that are periodic.
•Input to the analysis consists of the periodic arrival time, execution time, periodic ending
deadline, and relative priority of each task.
•The scheduler attempts to develop a schedule that enables it to meet the requirements of
all periodic tasks.
•This is a predictable approach but one that is inflexible, because any change to any task
requirements requires that the schedule be redone.
19-05-2024 PIM, Udupi 75
•Static table-driven approaches:
•These algorithms usually perform a static analysis associated with scheduling and
capture the schedules that are advantageous.
•This helps in providing a schedule that can point out a task with which the execution
must be started at run time.
•These are applicable to tasks that are periodic.
•Input to the analysis consists of the periodic arrival time, execution time, periodic ending
deadline, and relative priority of each task.
•The scheduler attempts to develop a schedule that enables it to meet the requirements of
all periodic tasks.
•This is a predictable approach but one that is inflexible, because any change to any task
requirements requires that the schedule be redone.
19-05-2024 PIM, Udupi 75
CPU Scheduling
•Static priority-driven preemptive approaches:
•Similar to the first approach, these also uses static analysis of scheduling.
•The differenceis that instead of selecting a particular schedule, it provides a useful
way of assigning priorities among various tasks in preemptive scheduling.
•This makes use of the priority-driven preemptive scheduling mechanism common
to most non-real-time multiprogramming systems.
•In a non-real-time system, a variety of factors might be used to determine priority.
•For example, in a time-sharing system, the priority of a process changes
depending on whether it is processor bound or I/O bound.
•In a real-time system, priority assignment is related to the time constraints
associated with each task.
19-05-2024 PIM, Udupi 76
•Static priority-driven preemptive approaches:
•Similar to the first approach, these also uses static analysis of scheduling.
•The differenceis that instead of selecting a particular schedule, it provides a useful
way of assigning priorities among various tasks in preemptive scheduling.
•This makes use of the priority-driven preemptive scheduling mechanism common
to most non-real-time multiprogramming systems.
•In a non-real-time system, a variety of factors might be used to determine priority.
•For example, in a time-sharing system, the priority of a process changes
depending on whether it is processor bound or I/O bound.
•In a real-time system, priority assignment is related to the time constraints
associated with each task.
19-05-2024 PIM, Udupi 76
CPU Scheduling
•Dynamic planning-based approaches:
•Feasibility is determined at run time (dynamically) rather than offline prior to the start of
execution (statically).
•An arriving task is accepted for execution only if it is feasible to meet its time
constraints.
•One of the results of the feasibility analysis is a schedule or plan that is used to decide
when to dispatch this task.
•With this approach, after a task arrives, but before its execution begins, an attempt is
made to create a schedule that contains the previously scheduled tasks as well as the new
arrival.
•If the new arrival can be scheduled in such a way that its deadlines are satisfied and that
no currently scheduled task misses a deadline, then the schedule is revised to
accommodate the new task
19-05-2024 PIM, Udupi 77
•Dynamic planning-based approaches:
•Feasibility is determined at run time (dynamically) rather than offline prior to the start of
execution (statically).
•An arriving task is accepted for execution only if it is feasible to meet its time
constraints.
•One of the results of the feasibility analysis is a schedule or plan that is used to decide
when to dispatch this task.
•With this approach, after a task arrives, but before its execution begins, an attempt is
made to create a schedule that contains the previously scheduled tasks as well as the new
arrival.
•If the new arrival can be scheduled in such a way that its deadlines are satisfied and that
no currently scheduled task misses a deadline, then the schedule is revised to
accommodate the new task
19-05-2024 PIM, Udupi 77
CPU Scheduling
•Dynamic best effort approaches:
•No feasibility analysis is performed.
•The system tries to meet all deadlines and aborts any started process whose
deadline is missed.
•When a task arrives, the system assigns a priority based on the characteristics of
the task.
•Typically, the tasks are aperiodic and so no static scheduling analysis is possible.
•With this type of scheduling, until a deadline arrives or until the task completes,
we do not know whether a timing constraint will be met.
•This is the major disadvantage of this form of scheduling.
•Its advantage is that it is easy to implement
19-05-2024 PIM, Udupi 78
•Dynamic best effort approaches:
•No feasibility analysis is performed.
•The system tries to meet all deadlines and aborts any started process whose
deadline is missed.
•When a task arrives, the system assigns a priority based on the characteristics of
the task.
•Typically, the tasks are aperiodic and so no static scheduling analysis is possible.
•With this type of scheduling, until a deadline arrives or until the task completes,
we do not know whether a timing constraint will be met.
•This is the major disadvantage of this form of scheduling.
•Its advantage is that it is easy to implement
19-05-2024 PIM, Udupi 78
CPU Scheduling
•Examples of Real time Scheduling:
•Deadline Scheduling
•Rate Monotonic Scheduling
•Linux Scheduling
•Windows Scheduling ( Windows Vista)
•Assignment 1: Above three topics
•Submission by 18 May 2024
19-05-2024 PIM, Udupi 79
•Examples of Real time Scheduling:
•Deadline Scheduling
•Rate Monotonic Scheduling
•Linux Scheduling
•Windows Scheduling ( Windows Vista)
•Assignment 1: Above three topics
•Submission by 18 May 2024
19-05-2024 PIM, Udupi 79
Virtual Memory
•Virtual Memory:
•Hardware and Control Structures,
•Operating System Software,
•UNIX and Solaris Memory Management,
•Linux Memory Management,
•Windows Vista Memory Management.
19-05-2024 PIM, Udupi 80
•Virtual Memory:
•Hardware and Control Structures,
•Operating System Software,
•UNIX and Solaris Memory Management,
•Linux Memory Management,
•Windows Vista Memory Management.
19-05-2024 PIM, Udupi 80
Virtual Memory
•Virtual memory
•This is a technique that allows the execution of processes that may not be
completely in memory.
•One advantage of this scheme is that programs can be larger than physical
memory.
•Further, virtual memory summaries main memory into an extremely large,
uniform array of storage, separating logical memory from physical memory.
•This frees programmers from the concerns of memory-storage limitations.
•Virtual memory also allows processes to easily share files and address spaces, and
it provides an efficient mechanism for process creation.
19-05-2024 PIM, Udupi 81
•Virtual memory
•This is a technique that allows the execution of processes that may not be
completely in memory.
•One advantage of this scheme is that programs can be larger than physical
memory.
•Further, virtual memory summaries main memory into an extremely large,
uniform array of storage, separating logical memory from physical memory.
•This frees programmers from the concerns of memory-storage limitations.
•Virtual memory also allows processes to easily share files and address spaces, and
it provides an efficient mechanism for process creation.
19-05-2024 PIM, Udupi 81
Virtual Memory
•Virtual Memory Terminology
•Virtual memory
•A storage allocation scheme in which secondary memory can be addressed as
though it were part of main memory.
•The addresses a program may use to reference memory are distinguished from the
addresses the memory system uses to identify physical storage sites, and program-
generated addresses are translated automatically to the corresponding machine
addresses.
•The size of virtual storage is limited by the addressing scheme of the computer
system and by the amount of secondary memory available
19-05-2024 PIM, Udupi 82
•Virtual Memory Terminology
•Virtual memory
•A storage allocation scheme in which secondary memory can be addressed as
though it were part of main memory.
•The addresses a program may use to reference memory are distinguished from the
addresses the memory system uses to identify physical storage sites, and program-
generated addresses are translated automatically to the corresponding machine
addresses.
•The size of virtual storage is limited by the addressing scheme of the computer
system and by the amount of secondary memory available
19-05-2024 PIM, Udupi 82
Virtual Memory
•Virtual address
•The address assigned to a location in virtual memory to allow that location to be
accessed as though it were part of main memory
•Virtual address space
•The virtual storage assigned to a process.
•Address space
•The range of memory addresses available to a process.
•Real address
•The address of a storage location in main memory
19-05-2024 PIM, Udupi 83
•Virtual address
•The address assigned to a location in virtual memory to allow that location to be
accessed as though it were part of main memory
•Virtual address space
•The virtual storage assigned to a process.
•Address space
•The range of memory addresses available to a process.
•Real address
•The address of a storage location in main memory
19-05-2024 PIM, Udupi 83
Virtual Memory
•The concepts of simple paging and simple segmentation, on the one hand, with
fixed and dynamic partitioning, on the other, there was a breakthrough in memory
management.
•Two characteristics of paging and segmentation are the keys to this breakthrough:
•1. All memory references within a process are logical addresses that are
dynamically translated into physical addresses at run time.
•This means that a process may be swapped in and out of main memory such that it
occupies different regions of main memory at different times during the course of
execution.
19-05-2024 PIM, Udupi 84
•The concepts of simple paging and simple segmentation, on the one hand, with
fixed and dynamic partitioning, on the other, there was a breakthrough in memory
management.
•Two characteristics of paging and segmentation are the keys to this breakthrough:
•1. All memory references within a process are logical addresses that are
dynamically translated into physical addresses at run time.
•This means that a process may be swapped in and out of main memory such that it
occupies different regions of main memory at different times during the course of
execution.
19-05-2024 PIM, Udupi 84
Virtual Memory
•2. A process may be broken up into a number of pieces (pages or segments) and
these pieces need not be contiguously located in main memory during execution.
•The combination of dynamic run-time address translation and the use of a page or
segment table permits this to happen.
•If these two characteristics are present, then all the pages or all of the segments of
a process need not be in main memory during execution.
•If the piece (segment or page) that holds the next instruction to be fetched and the
piece that holds the next data location to be accessed are in main memory, then at
least for a time execution may proceed
•
19-05-2024 PIM, Udupi 85
•2. A process may be broken up into a number of pieces (pages or segments) and
these pieces need not be contiguously located in main memory during execution.
•The combination of dynamic run-time address translation and the use of a page or
segment table permits this to happen.
•If these two characteristics are present, then all the pages or all of the segments of
a process need not be in main memory during execution.
•If the piece (segment or page) that holds the next instruction to be fetched and the
piece that holds the next data location to be accessed are in main memory, then at
least for a time execution may proceed
•
19-05-2024 PIM, Udupi 85
Virtual Memory
•Let us see how this is accomplished.
•We will use the term pieceto refer to either page or segment, depending on
whether paging or segmentation is employed.
•Suppose that a new process is brought into memory.
•The OS begins by bringing in only one or a few pieces, to include the initial
program piece and the initial data piece to which those instructions refer.
•The portion of a process that is actually in main memory at any time is called the
resident setof the process
•As the process executes, things proceed smoothly as long as all memory
references are to locations that are in the resident set.
19-05-2024 PIM, Udupi 86
•Let us see how this is accomplished.
•We will use the term pieceto refer to either page or segment, depending on
whether paging or segmentation is employed.
•Suppose that a new process is brought into memory.
•The OS begins by bringing in only one or a few pieces, to include the initial
program piece and the initial data piece to which those instructions refer.
•The portion of a process that is actually in main memory at any time is called the
resident setof the process
•As the process executes, things proceed smoothly as long as all memory
references are to locations that are in the resident set.
19-05-2024 PIM, Udupi 86
Virtual Memory
•If the processor encounters a logical address that is not in main memory, it
generates an interruptindicating a memory access fault.
•The OS puts this interrupted process in a blocking state.
•For the execution of this process to proceed later, the OS must bring into main
memory the piece of the process that contains the logical address that caused the
access fault.
•For this, the OS issues a disk I/O read request.
•After the I/O request has been issued, the OS can dispatch another process to run
while the disk I/O is performed.
•Once the desired piece has been brought into main memory, an I/O interrupt is
issued, giving control back to the OS, which places the affected process back into
a Ready state
19-05-2024 PIM, Udupi 87
•If the processor encounters a logical address that is not in main memory, it
generates an interruptindicating a memory access fault.
•The OS puts this interrupted process in a blocking state.
•For the execution of this process to proceed later, the OS must bring into main
memory the piece of the process that contains the logical address that caused the
access fault.
•For this, the OS issues a disk I/O read request.
•After the I/O request has been issued, the OS can dispatch another process to run
while the disk I/O is performed.
•Once the desired piece has been brought into main memory, an I/O interrupt is
issued, giving control back to the OS, which places the affected process back into
a Ready state
19-05-2024 PIM, Udupi 87
Virtual Memory
•What are the implications of our new strategy?
•There are two implications, and both lead to improved system utilization
•More processes may be maintained in main memory.
•Since we are going to load only some of the pieces of any particular process, there
is room for more processes.
•This leads to more efficient utilization of the processor because it is more likely
that at least one of the more processes will be in a Ready state at any particular
time
19-05-2024 PIM, Udupi 88
•What are the implications of our new strategy?
•There are two implications, and both lead to improved system utilization
•More processes may be maintained in main memory.
•Since we are going to load only some of the pieces of any particular process, there
is room for more processes.
•This leads to more efficient utilization of the processor because it is more likely
that at least one of the more processes will be in a Ready state at any particular
time
19-05-2024 PIM, Udupi 88
Virtual Memory
•A process may be larger than all of main memory.
•One of the most fundamental restrictions in programming is lifted.
•A programmer must be acutely aware of how much memory is available.
•If the program being written is too large, the programmer must devise ways to
structure the program into pieces that can be loaded separately in some sort of
overlay strategy.
•With virtual memory based on paging or segmentation, that job is left to the OS
and the hardware.
•As far as the programmer is concerned, he or she is dealing with a huge memory,
the size associated with disk storage.
•The OS automatically loads pieces of a process into main memory as required.
19-05-2024 PIM, Udupi 89
•A process may be larger than all of main memory.
•One of the most fundamental restrictions in programming is lifted.
•A programmer must be acutely aware of how much memory is available.
•If the program being written is too large, the programmer must devise ways to
structure the program into pieces that can be loaded separately in some sort of
overlay strategy.
•With virtual memory based on paging or segmentation, that job is left to the OS
and the hardware.
•As far as the programmer is concerned, he or she is dealing with a huge memory,
the size associated with disk storage.
•The OS automatically loads pieces of a process into main memory as required.
19-05-2024 PIM, Udupi 89
Virtual Memory
•A process may be larger than all of main memory.
•One of the most fundamental restrictions in programming is lifted.
•A programmer must be acutely aware of how much memory is available.
•If the program being written is too large, the programmer must devise ways to
structure the program into pieces that can be loaded separately in some sort of
overlay strategy.
•With virtual memory based on paging or segmentation, that job is left to the OS
and the hardware.
•As far as the programmer is concerned, he or she is dealing with a huge memory,
the size associated with disk storage.
•The OS automatically loads pieces of a process into main memory as required.
19-05-2024 PIM, Udupi 90
•A process may be larger than all of main memory.
•One of the most fundamental restrictions in programming is lifted.
•A programmer must be acutely aware of how much memory is available.
•If the program being written is too large, the programmer must devise ways to
structure the program into pieces that can be loaded separately in some sort of
overlay strategy.
•With virtual memory based on paging or segmentation, that job is left to the OS
and the hardware.
•As far as the programmer is concerned, he or she is dealing with a huge memory,
the size associated with disk storage.
•The OS automatically loads pieces of a process into main memory as required.
19-05-2024 PIM, Udupi 90
Virtual Memory
•Because a process executes only in main memory, that memory is referred to as
real memory.
•But a programmer or user sees a much larger memory—which is allocated on
disk.
•This latter is referred to as virtual memory.
•Virtual memory allows for very effective multiprogramming and relieves the user
of constraints of main memory.
•Characteristics of paging and segmentation, with and without the use of virtual
memory
•Page no –343 (Operating Systems Internals and Design Principles, Seventh
Edition –William Stallings)
19-05-2024 PIM, Udupi 91
•Because a process executes only in main memory, that memory is referred to as
real memory.
•But a programmer or user sees a much larger memory—which is allocated on
disk.
•This latter is referred to as virtual memory.
•Virtual memory allows for very effective multiprogramming and relieves the user
of constraints of main memory.
•Characteristics of paging and segmentation, with and without the use of virtual
memory
•Page no –343 (Operating Systems Internals and Design Principles, Seventh
Edition –William Stallings)
19-05-2024 PIM, Udupi 91
Virtual Memory
•Locality and Virtual Memory
•Consider a process, consisting of a long program plus a number of arrays of data.
•Over any short period of time, execution may be confined to a small section of the
program (e.g., a subroutine) and access to only one or two arrays of data.
•Then it would clearly be wasteful to load in many pieces for that process when
only a few pieces will be used before the program is suspended and swapped out.
•We can make better use of memory by loading in just a few pieces.
•Then, if the program branches to an instruction or references a data item on a
piece not in main memory, a fault is triggered.
•This tells the OS to bring in the desired piece
19-05-2024 PIM, Udupi 92
•Locality and Virtual Memory
•Consider a process, consisting of a long program plus a number of arrays of data.
•Over any short period of time, execution may be confined to a small section of the
program (e.g., a subroutine) and access to only one or two arrays of data.
•Then it would clearly be wasteful to load in many pieces for that process when
only a few pieces will be used before the program is suspended and swapped out.
•We can make better use of memory by loading in just a few pieces.
•Then, if the program branches to an instruction or references a data item on a
piece not in main memory, a fault is triggered.
•This tells the OS to bring in the desired piece
19-05-2024 PIM, Udupi 92
Virtual Memory
•Thus, at any one time, only a few pieces of any given process are in memory, and
therefore more processes can be maintained in memory.
•Furthermore, time is saved because unused pieces are not swapped in and out of
memory.
•But the OS must be clever to manage this scheme.
•Practically main memory will be occupied with process pieces, so that the
processor and OS have direct access to as many processes as possible.
•Thus, when the OS brings one piece in, it must throw another out. If it throws out
a piece just before it is used, then it will have to get that piece again almost
immediately.
•Too much of this leads to a condition known as thrashing
19-05-2024 PIM, Udupi 93
•Thus, at any one time, only a few pieces of any given process are in memory, and
therefore more processes can be maintained in memory.
•Furthermore, time is saved because unused pieces are not swapped in and out of
memory.
•But the OS must be clever to manage this scheme.
•Practically main memory will be occupied with process pieces, so that the
processor and OS have direct access to as many processes as possible.
•Thus, when the OS brings one piece in, it must throw another out. If it throws out
a piece just before it is used, then it will have to get that piece again almost
immediately.
•Too much of this leads to a condition known as thrashing
19-05-2024 PIM, Udupi 93
Virtual Memory
•The system spends most of its time swapping pieces rather than executing
instructions.
•The avoid thrashing variety of complex but effective algorithms are developed.
•In essence, the OS tries to guess, based on recent history, which pieces are least
likely to be used in the near future.
•This reasoning is based on the principle of locality
•Hence, the assumption that only a few pieces of a process will be needed over a
short period of time is valid.
•Also, it should be possible to make intelligent guesses about which pieces of a
process will be needed in the near future, which avoids thrashing.
19-05-2024 PIM, Udupi 94
•The system spends most of its time swapping pieces rather than executing
instructions.
•The avoid thrashing variety of complex but effective algorithms are developed.
•In essence, the OS tries to guess, based on recent history, which pieces are least
likely to be used in the near future.
•This reasoning is based on the principle of locality
•Hence, the assumption that only a few pieces of a process will be needed over a
short period of time is valid.
•Also, it should be possible to make intelligent guesses about which pieces of a
process will be needed in the near future, which avoids thrashing.
19-05-2024 PIM, Udupi 94
Virtual Memory
•the principle of locality suggests that a virtual memory scheme may work.
•For virtual memory to be practical and effective, two ingredients are needed.
•First, there must be hardware support for the paging and/or segmentation scheme
to be employed.
•Second, the OS must include software for managing the movement of pages
and/or segments between secondary memory and main memory.
19-05-2024 PIM, Udupi 95
•the principle of locality suggests that a virtual memory scheme may work.
•For virtual memory to be practical and effective, two ingredients are needed.
•First, there must be hardware support for the paging and/or segmentation scheme
to be employed.
•Second, the OS must include software for managing the movement of pages
and/or segments between secondary memory and main memory.
19-05-2024 PIM, Udupi 95
Virtual Memory
•Paging
•The term virtual memory is usually associated with systems that employ paging,
•Virtual memory based on segmentation is also used.
•In simple paging, each process has its own page table, and when all of its pages
are loaded into main memory, the page table for a process is created and loaded
into main memory.
•Each page table entry (PTE)contains the frame number of the corresponding
page in main memory.
•A page table is also needed for a virtual memory scheme based on paging which is
unique with each process
19-05-2024 PIM, Udupi 96
•Paging
•The term virtual memory is usually associated with systems that employ paging,
•Virtual memory based on segmentation is also used.
•In simple paging, each process has its own page table, and when all of its pages
are loaded into main memory, the page table for a process is created and loaded
into main memory.
•Each page table entry (PTE)contains the frame number of the corresponding
page in main memory.
•A page table is also needed for a virtual memory scheme based on paging which is
unique with each process
19-05-2024 PIM, Udupi 96
Virtual Memory
•In this case, the page table entries become more complex.
•Since only some of the pages of a process may be in main memory, a bit is
needed in each page table entry to indicate whether the corresponding page is
present (P) in main memory or not.
•The page table entry includes a modify (M) bit, indicating whether the contents of
the corresponding page have been altered since the page was last loaded into main
memory.
19-05-2024 PIM, Udupi 97
•In this case, the page table entries become more complex.
•Since only some of the pages of a process may be in main memory, a bit is
needed in each page table entry to indicate whether the corresponding page is
present (P) in main memory or not.
•The page table entry includes a modify (M) bit, indicating whether the contents of
the corresponding page have been altered since the page was last loaded into main
memory.
19-05-2024 PIM, Udupi 97
Virtual Memory
•If there has been no change, then it is not necessary to write the page out when it
comes time to replace the page in the frame that it currently occupies.
•Other control bits may also be present.
•E.g.: If protection or sharing is managed at the page level, then bits for that
purpose will be required.
•PAGE TABLE STRUCTURE
•The basic mechanism for reading a word from memory involves the translation of
a virtual, or logical address, consisting of page number and offset, into a physical
address, consisting of frame number and offset, using a page table.
19-05-2024 PIM, Udupi 98
•If there has been no change, then it is not necessary to write the page out when it
comes time to replace the page in the frame that it currently occupies.
•Other control bits may also be present.
•E.g.: If protection or sharing is managed at the page level, then bits for that
purpose will be required.
•PAGE TABLE STRUCTURE
•The basic mechanism for reading a word from memory involves the translation of
a virtual, or logical address, consisting of page number and offset, into a physical
address, consisting of frame number and offset, using a page table.
19-05-2024 PIM, Udupi 98
Virtual Memory
•But the page table is of variable length, depending on the size of the process, it
cannot held in registers.
•Instead, it must be in main memory to be accessed.
•Following figure suggests a hardware implementation
19-05-2024 PIM, Udupi 99
•But the page table is of variable length, depending on the size of the process, it
cannot held in registers.
•Instead, it must be in main memory to be accessed.
•Following figure suggests a hardware implementation
19-05-2024 PIM, Udupi 99
Virtual Memory
•.
19-05-2024 PIM, Udupi 100
•.
19-05-2024 PIM, Udupi 100
Virtual Memory
•When a particular process is running, a register holds the starting address of the
page table for that process.
•The page number of a virtual address is used to index that table and look up the
corresponding frame number.
•This is combined with the offset portion of the virtual address to produce the
desired real address.
•Typically the amount of memory required for the page tables are high.
•To overcome this problem, most virtual memory schemes store page tables in
virtual memory rather than real memory.
•When a process is running, at least a part of its page table must be in main
memory, including the page table entry of the currently executing page
19-05-2024 PIM, Udupi 101
•When a particular process is running, a register holds the starting address of the
page table for that process.
•The page number of a virtual address is used to index that table and look up the
corresponding frame number.
•This is combined with the offset portion of the virtual address to produce the
desired real address.
•Typically the amount of memory required for the page tables are high.
•To overcome this problem, most virtual memory schemes store page tables in
virtual memory rather than real memory.
•When a process is running, at least a part of its page table must be in main
memory, including the page table entry of the currently executing page
19-05-2024 PIM, Udupi 101
Virtual Memory
•Some processors use a two-level scheme to organize large page tables.
•In this scheme, there is a page directory, in which each entry, points to a page
table.
•Thus, if the length of the page directory is X , and if the maximum length of a
page table is Y , then a process can consist of up to X ×Y pages.
•Example: refer text book –page 348
19-05-2024 PIM, Udupi 102
•Some processors use a two-level scheme to organize large page tables.
•In this scheme, there is a page directory, in which each entry, points to a page
table.
•Thus, if the length of the page directory is X , and if the maximum length of a
page table is Y , then a process can consist of up to X ×Y pages.
•Example: refer text book –page 348
19-05-2024 PIM, Udupi 102
Virtual Memory
•INVERTED PAGE TABLE:
•A drawback of the traditional page tables seen so far is that their size is
proportional to that of the virtual address space
•As virtual address space increases, page table size also increases
•If the address space consists of 2
32
bytes, with 4096 bytes per page, then over 1
million page table entries are needed which may need at least 4 megabytes.
•On large systems, this size is probably doable.
•But with 64-bit computers, the situation changes drastically.
•If the address space is now 2
64
bytes, with 4-KB pages, we need a page table with
2
52
entries.
•If each entry is 8 bytes, the table is over 30 million gigabytes –Practically not
possible
19-05-2024 PIM, Udupi 103
•INVERTED PAGE TABLE:
•A drawback of the traditional page tables seen so far is that their size is
proportional to that of the virtual address space
•As virtual address space increases, page table size also increases
•If the address space consists of 2
32
bytes, with 4096 bytes per page, then over 1
million page table entries are needed which may need at least 4 megabytes.
•On large systems, this size is probably doable.
•But with 64-bit computers, the situation changes drastically.
•If the address space is now 2
64
bytes, with 4-KB pages, we need a page table with
2
52
entries.
•If each entry is 8 bytes, the table is over 30 million gigabytes –Practically not
possible
19-05-2024 PIM, Udupi 103
Virtual Memory
•An alternative approach “inverted page table structure” is proposed
•In this approach, the page number portion of a virtual address is mapped into a
hash value using a simple hashing function.
•The hash value is a pointer to the inverted page table, which contains the page
table entries.
•There is one entry in the inverted page table for each real memory page frame
rather than one per virtual page.
•Thus, a fixed proportion of real memory is required for the tables regardless of the
number of processes or virtual pages supported.
•As more than one virtual address may map into the same hash table entry, a
chaining technique is used for managing the overflow
19-05-2024 PIM, Udupi 104
•An alternative approach “inverted page table structure” is proposed
•In this approach, the page number portion of a virtual address is mapped into a
hash value using a simple hashing function.
•The hash value is a pointer to the inverted page table, which contains the page
table entries.
•There is one entry in the inverted page table for each real memory page frame
rather than one per virtual page.
•Thus, a fixed proportion of real memory is required for the tables regardless of the
number of processes or virtual pages supported.
•As more than one virtual address may map into the same hash table entry, a
chaining technique is used for managing the overflow
19-05-2024 PIM, Udupi 104
Virtual Memory
•The page table’s structure is called inverted because it indexes page table entries by
frame number rather than by virtual page number.
•Each entry in the page table includes the following:
•Page number:This is the page number portion of the virtual address.
•Process identifier:The process that owns this page. The combination of page number
and process identifier identify a page within the virtual address space of a particular
process.
•Control bits:This field includes flags, such as valid, referenced, and modified; and
protection and locking information.
•Chain pointer:This field is null (perhaps indicated by a separate bit) if there are no
chained entries for this entry. Otherwise, the field contains the index value (number
between 0 and 2
m–1
) of the next entry in the chain.
19-05-2024 PIM, Udupi 105
•The page table’s structure is called inverted because it indexes page table entries by
frame number rather than by virtual page number.
•Each entry in the page table includes the following:
•Page number:This is the page number portion of the virtual address.
•Process identifier:The process that owns this page. The combination of page number
and process identifier identify a page within the virtual address space of a particular
process.
•Control bits:This field includes flags, such as valid, referenced, and modified; and
protection and locking information.
•Chain pointer:This field is null (perhaps indicated by a separate bit) if there are no
chained entries for this entry. Otherwise, the field contains the index value (number
between 0 and 2
m–1
) of the next entry in the chain.
19-05-2024 PIM, Udupi 105
Virtual Memory
•Figure below shows a typical implementation of the inverted page table approach
19-05-2024 PIM, Udupi 106
•Figure below shows a typical implementation of the inverted page table approach
19-05-2024 PIM, Udupi 106
Virtual Memory
•In this example, the virtual address includes an n -bit page number, with n > m .
•The hash function maps the n -bit page number into an m -bit quantity, which is
used to index into the inverted page table
•TRANSLATION LOOKASIDE BUFFER
•Every virtual memory reference can cause two physical memory accesses:
•One to fetch the appropriate page table entry and one to fetch the desired data.
•Thus, a straightforward virtual memory scheme doubles the memory access time.
•To overcome this problem, most virtual memory schemes use a special high-speed
cache for page table entries, called a Translation LookasideBuffer (TLB)
19-05-2024 PIM, Udupi 107
•In this example, the virtual address includes an n -bit page number, with n > m .
•The hash function maps the n -bit page number into an m -bit quantity, which is
used to index into the inverted page table
•TRANSLATION LOOKASIDE BUFFER
•Every virtual memory reference can cause two physical memory accesses:
•One to fetch the appropriate page table entry and one to fetch the desired data.
•Thus, a straightforward virtual memory scheme doubles the memory access time.
•To overcome this problem, most virtual memory schemes use a special high-speed
cache for page table entries, called a Translation LookasideBuffer (TLB)
19-05-2024 PIM, Udupi 107
Virtual Memory
•This cache functions in the same way as a memory cache and contains those page
table entries that have been most recently used.
•The resulting paging hardware is illustrated in Figure
19-05-2024 PIM, Udupi 108
•This cache functions in the same way as a memory cache and contains those page
table entries that have been most recently used.
•The resulting paging hardware is illustrated in Figure
19-05-2024 PIM, Udupi 108
Virtual Memory
19-05-2024 PIM, Udupi 109
19-05-2024 PIM, Udupi 109
Virtual Memory
•Given a virtual address, the processor will first examine the TLB.
•If the desired page table entry is present(TLB hit), then the frame number is
retrieved and the real address is formed.
•If the desired page table entry is not found (TLB miss), then the processor uses the
page number to index the process page table and examine the corresponding
page table entry.
•If the “present bit” is set, then the page is in main memory, and the processor can
retrieve the frame number from the page table entry to form the real address.
•The processor also updates the TLB to include this new page table entry.
19-05-2024 PIM, Udupi 110
•Given a virtual address, the processor will first examine the TLB.
•If the desired page table entry is present(TLB hit), then the frame number is
retrieved and the real address is formed.
•If the desired page table entry is not found (TLB miss), then the processor uses the
page number to index the process page table and examine the corresponding
page table entry.
•If the “present bit” is set, then the page is in main memory, and the processor can
retrieve the frame number from the page table entry to form the real address.
•The processor also updates the TLB to include this new page table entry.
19-05-2024 PIM, Udupi 110
Virtual Memory
•Finally, if the present bit is not set, then the desired page is not in main memory
and a memory access fault, called a page fault, is issued.
•At this point, the OS is invoked which loads the needed page and updates the page
table
•Following figure 8.8 shows a flowchart that shows the use of the TLB
19-05-2024 PIM, Udupi 111
•Finally, if the present bit is not set, then the desired page is not in main memory
and a memory access fault, called a page fault, is issued.
•At this point, the OS is invoked which loads the needed page and updates the page
table
•Following figure 8.8 shows a flowchart that shows the use of the TLB
19-05-2024 PIM, Udupi 111
Virtual Memory
19-05-2024 PIM, Udupi 112
19-05-2024 PIM, Udupi 112
Virtual Memory
•The flowchart shows that if the desired page is not in main memory, a page fault
interrupt causes the page fault handling routine to be invoked.
•To keep the flowchart simple, the fact that the OS may dispatch another process
while disk I/O is underway is not shown.
•By the principle of locality, most virtual memory references will be to locations in
recently used pages.
•Therefore, most references will involve page table entries in the cache.
•Studies of the VAX TLB have shown that this scheme can significantly improve
performance
19-05-2024 PIM, Udupi 113
•The flowchart shows that if the desired page is not in main memory, a page fault
interrupt causes the page fault handling routine to be invoked.
•To keep the flowchart simple, the fact that the OS may dispatch another process
while disk I/O is underway is not shown.
•By the principle of locality, most virtual memory references will be to locations in
recently used pages.
•Therefore, most references will involve page table entries in the cache.
•Studies of the VAX TLB have shown that this scheme can significantly improve
performance
19-05-2024 PIM, Udupi 113
Tags
Categories
GeneralDownload
Download Slideshow Get the original presentation fileQuick Actions
Statistics
- Views 6
- Slides 113
- Age 484 days
Related Slideshows
22
Pray For The Peace Of Jerusalem and You Will Prosper
RodolfoMoralesMarcuc
30 views
26
Don_t_Waste_Your_Life_God.....powerpoint
chalobrido8
32 views
31
VILLASUR_FACTORS_TO_CONSIDER_IN_PLATING_SALAD_10-13.pdf
JaiJai148317
30 views
14
Fertility awareness methods for women in the society
Isaiah47
29 views
35
Chapter 5 Arithmetic Functions Computer Organisation and Architecture
RitikSharma297999
26 views
5
syakira bhasa inggris (1) (1).pptx.......
ourcommunity56
28 views