|
|
|
Modern Operating Systems by Herbert Bos and Andrew S. Tanenb...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf
Showing 596-597 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 596
SEC. 8.2
MULTICOMPUTERS
565
G
H
I
A
E
F
B
C
D
Node 1
Node 2
3
2
3
5
5
8
1
2
4
4
2
3
6
2
1
4
Node 3
G
H
I
A
E
F
B
C
D
Node 1
Node 2
3
2
3
5
5
8
1
2
4
4
2
3
6
2
1
4
Node 3
Traffic
between
D and I
Process
Figure 8-24.
Two ways of allocating nine processes to three nodes.
A Sender-Initiated Distributed Heuristic Algorithm
Now let us look at some distributed algorithms. One algorithm says that when
a process is created, it runs on the node that created it unless that node is overload-
ed. The metric for overloaded might involve too many processes, too big a total
working set, or some other metric.
If it is overloaded, the node selects another
node at random and asks it what its load is (using the same metric).
If the probed
node’s load is below some threshold value, the new process is sent there (Eager et
al., 1986).
If not, another machine is chosen for probing. Probing does not go on
forever. If no suitable host is found within
N
probes, the algorithm terminates and
the process runs on the originating machine. The idea is for heavily loaded nodes
to try to get rid of excess work, as shown in Fig. 8-25(a), which depicts send-
er-initiated load balancing.
I’m full
Here, have a process
Take some work
I’m overloaded
Help !
(a)
(b)
I have nothing to do
Yawn
I’m bored
I’m free tonight
Need help ?
Figure 8-25.
(a) An overloaded node looking for a lightly loaded node to hand
off processes to.
(b) An empty node looking for work to do.
Page 597
566
MULTIPLE PROCESSOR SYSTEMS
CHAP. 8
Eager et al. constructed an analytical queueing model of this algorithm. Using
this model, it was established that the algorithm behaves well and is stable under a
wide range of parameters, including various threshold values, transfer costs, and
probe limits.
Nevertheless, it should be observed that under conditions of heavy load, all
machines will constantly send probes to other machines in a futile attempt to find
one that is willing to accept more work. Few processes will be off-loaded, but con-
siderable overhead may be incurred in the attempt to do so.
A Receiver-Initiated Distributed Heuristic Algorithm
A complementary algorithm to the one discussed above, which is initiated by
an overloaded sender, is one initiated by an underloaded receiver, as shown in
Fig. 8-25(b).
With this algorithm, whenever a process finishes, the system checks
to see if it has enough work. If not, it picks some machine at random and asks it
for work. If that machine has nothing to offer, a second, and then a third machine
is asked. If no work is found with
N
probes, the node temporarily stops asking,
does any work it has queued up, and tries again when the next process finishes. If
no work is available, the machine goes idle.
After some fixed time interval, it
begins probing again.
An advantage of this algorithm is that it does not put extra load on the system
at critical times. The sender-initiated algorithm makes large numbers of probes
precisely when the system can least tolerate it—when it is heavily loaded. With the
receiver-initiated algorithm, when the system is heavily loaded, the chance of a
machine having insufficient work is small. However, when this does happen, it will
be easy to find work to take over. Of course, when there is little work to do, the re-
ceiver-initiated algorithm creates considerable probe traffic as all the unemployed
machines desperately hunt for work. However, it is far better to have the overhead
go up when the system is underloaded than when it is overloaded.
It is also possible to combine both of these algorithms and have machines try
to get rid of work when they have too much, and try to acquire work when they do
not have enough. Furthermore, machines can perhaps improve on random polling
by keeping a history of past probes to determine if any machines are chronically
underloaded or overloaded. One of these can be tried first, depending on whether
the initiator is trying to get rid of work or acquire it.
8.3 DISTRIBUTED SYSTEMS
Having now
completed our study of multicores, multiprocessors, and
multicomputers we are now ready to turn to the last type of multiple processor sys-
tem, the
distributed system
.
These systems are similar to multicomputers in that
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
