|
|
|
Modern Operating Systems by Herbert Bos and Andrew S. Tanenb...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf
Showing 194 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 194
SEC. 2.4
SCHEDULING
163
Lottery Scheduling
While making promises to the users and then living up to them is a fine idea, it
is difficult to implement. However, another algorithm can be used to give similarly
predictable results with a much simpler implementation.
It is called
lottery
scheduling
(Waldspurger and Weihl, 1994).
The basic idea is to give processes lottery tickets for various system resources,
such as CPU time. Whenever a scheduling decision has to be made, a lottery ticket
is chosen at random, and the process holding that ticket gets the resource. When
applied to CPU scheduling, the system might hold a lottery 50 times a second, with
each winner getting 20 msec of CPU time as a prize.
To paraphrase George Orwell: ‘‘All processes are equal, but some processes
are more equal.’’ More important processes can be givenextra tickets, to increase
their odds of winning.
If there are 100 tickets outstanding, and one process holds
20 of them, it will have a 20% chance of winning each lottery.
In the long run, it
will get about 20% of the CPU.
In contrast to a priority scheduler, where it is very
hard to state what having a priority of 40 actually means, here the rule is clear: a
process holding a fraction
f
of the tickets will get about a fraction
f
of the resource
in question.
Lottery scheduling has several interesting properties. For example, if a new
process shows up and is granted some tickets, at the very next lottery it will have a
chance of winning in proportion to the number of tickets it holds.
In other words,
lottery scheduling is highly responsive.
Cooperating processes may exchange tickets if they wish. For example, when a
client process sends a message to a server process and then blocks, it may give all
of its tickets to the server, to increase the chance of the server running next. When
the server is finished, it returns the tickets so that the client can run again. In fact,
in the absence of clients, servers need no tickets at all.
Lottery scheduling can be used to solve problems that are difficult to handle
with other methods. One example is a video server in which several processes are
feeding video streams to their clients, but at different frame rates. Suppose that the
processes need frames at 10, 20, and 25 frames/sec.
By allocating these processes
10, 20, and 25 tickets, respectively, they will automatically divide the CPU in
approximately the correct proportion, that is, 10 : 20 : 25.
Fair-Share Scheduling
So far we have assumed that each process is scheduled on its own, without
regard to who its owner is.
As a result, if user 1 starts up nine processes and user 2
starts up one process, with round robin or equal priorities, user 1 will get 90% of
the CPU and user 2 only 10% of it.
To prevent this situation, some systems take into account which user owns a
process before scheduling it.
In this model, each user is allocated some fraction of
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
