|
|
|
Modern Operating Systems by Herbert Bos and Andrew S. Tanenb...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf
Showing 193 out of 1137
Modern Operating Systems by Herbert Bos and Andrew...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf-M ODERN O PERATING S YSTEMS
Modern Operating Systems by Herbert...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf-M ODERN O PERATING S YSTEMS
Page 193
162
PROCESSES AND THREADS
CHAP. 2
Shortest Process Next
Because shortest job first always produces the minimum average response time
for batch systems, it would be nice if it could be used for interactive processes as
well. To a certain extent, it can be.
Interactive processes generally follow the pat-
tern of wait for command, execute command, wait for command, execute com-
mand, etc.
If we regard the execution of each command as a separate ‘‘job,’’ then
we can minimize overall response time by running the shortest one first. The prob-
lem is figuring out which of the currently runnable processes is the shortest one.
One approach is to make estimates based on past behavior and run the process
with the shortest estimated running time. Suppose that the estimated time per com-
mand for some process is
T
0
.
Now suppose its next run is measured to be
T
1
. We
could update our estimate by taking a weighted sum of these two numbers, that is,
aT
0
+
(1
−
a
)
T
1
.
Through the choice of
a
we can decide to have the estimation
process forget old runs quickly, or remember them for a long time. With
a
=
1/2,
we get successive estimates of
T
0
,
T
0
/2
+
T
1
/2,
T
0
/4
+
T
1
/4
+
T
2
/2,
T
0
/8
+
T
1
/8
+
T
2
/4
+
T
3
/2
After three new runs, the weight of
T
0
in the new estimate has dropped to 1/8.
The technique of estimating the next value in a series by taking the weighted
average of the current measured value and the previous estimate is sometimes cal-
led
aging
.
It is applicable to many situations where a prediction must be made
based on previous values. Aging is especially easy to implement when
a
=
1/2. All
that is needed is to add the new value to the current estimate and divide the sum by
2 (by shifting it right 1 bit).
Guaranteed Scheduling
A completely different approach to scheduling is to make real promises to the
users about performance and then live up to those promises. One promise that is
realistic to make and easy to live up to is this: If
n
users are logged in while you are
working, you will receive about 1/
n
of the CPU power. Similarly, on a single-user
system with
n
processes running, all things being equal, each one should get 1/
n
of
the CPU cycles. That seems fair enough.
To make good on this promise, the system must keep track of how much CPU
each process has had since its creation.
It then computes the amount of CPU each
one is entitled to, namely the time since creation divided by
n
.
Since the amount of
CPU time each process has actually had is also known, it is fairly straightforward
to compute the ratio of actual CPU time consumed to CPU time entitled.
A ratio
of 0.5 means that a process has only had half of what it should have had, and a
ratio of 2.0 means that a process has had twice as much as it was entitled to. The
algorithm is then to run the process with the lowest ratio until its ratio has moved
above that of its closest competitor.
Then that one is chosen to run next.
Ace your assessments! Get Better Grades
Browse thousands of Study Materials & Solutions from your Favorite Schools
Concordia University
Concordia_University
School:
Operating_Systems
Course:
Great resource for chem class. Had all the past labs and assignments
Leland P.
Santa Clara University
Introducing Study Plan
Using AI Tools to Help you understand and remember your course concepts better and faster than any other resource.
Find the best videos to learn every concept in that course from Youtube and Tiktok without searching.
Save All Relavent Videos & Materials and access anytime and anywhere
Prepare Smart and Guarantee better grades
Know more
Students also viewed documents
lab 18.docx
lab_18.docx
Course
Course
3
Module5QuizSTA2023.d...
Module5QuizSTA2023.docx.docx
Course
Course
10
Week 7 Test Math302....
Week_7_Test_Math302.docx.docx
Course
Course
30
Chapter 1 Assigment ...
Chapter_1_Assigment_Questions.docx.docx
Course
Course
5
Week 4 tests.docx.do...
Week_4_tests.docx.docx
Course
Course
23
Week 6 tests.docx.do...
Week_6_tests.docx.docx
Course
Course
106
