|
|
|
Modern Operating Systems by Herbert Bos and Andrew S. Tanenb...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf
Showing 197-198 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 197
166
PROCESSES AND THREADS
CHAP. 2
2.4.6 Thread Scheduling
When several processes each have multiple threads, we have two levels of par-
allelism present: processes and threads. Scheduling in such systems differs sub-
stantially depending on whether user-level threads or kernel-level threads (or both)
are supported.
Let us consider user-level threads first. Since the kernel is not aware of the ex-
istence of threads, it operates as it always does, picking a process, say,
A
, and giv-
ing
A
control for its quantum. The thread scheduler inside
A
decides which thread
to run, say
A1
.
Since there are no clock interrupts to multiprogram threads, this
thread may continue running as long as it wants to.
If it uses up the process’ entire
quantum, the kernel will select another process to run.
When the process
A
finally runs again, thread
A1
will resume running.
It will
continue to consume all of
A
’s time until it is finished. However, its antisocial be-
havior will not affect other processes.
They will get whatever the scheduler con-
siders their appropriate share, no matter what is going on inside process
A
.
Now consider the case that
A
’s threads have relatively little work to do per
CPU burst, for example, 5 msec of work within a 50-msec quantum. Consequently,
each one runs for a little while, then yields the CPU back to the thread scheduler.
This might lead to the sequence
A1
,
A2
,
A3
,
A1
,
A2
,
A3
,
A1
,
A2
,
A3
,
A1
, before the
kernel switches to process
B
.
This situation is illustrated in Fig. 2-44(a).
Process A
Process B
Process B
Process A
1. Kernel picks a process
1. Kernel picks a thread
Possible:
A1, A2, A3, A1, A2, A3
Also possible:
A1, B1, A2, B2, A3, B3
Possible:
A1, A2, A3, A1, A2, A3
Not possible:
A1, B1, A2, B2, A3, B3
(a)
(b)
Order in which
threads run
2. Run-time
system
picks a
thread
1
2
3
1
3
2
Figure 2-44.
(a) Possible scheduling of user-level threads with a 50-msec proc-
ess quantum and threads that run 5 msec per CPU burst. (b) Possible scheduling
of kernel-level threads with the same characteristics as (a).
The scheduling algorithm used by the run-time system can be any of the ones
described above.
In practice, round-robin scheduling and priority scheduling are
most common. The only constraint is the absence of a clock to interrupt a thread
that has run too long.
Since threads cooperate, this is usually not an issue.
Page 198
SEC. 2.4
SCHEDULING
167
Now consider the situation with kernel-level threads. Here the kernel picks a
particular thread to run.
It does not have to take into account which process the
thread belongs to, but it can if it wants to. The thread is given a quantum and is for-
cibly suspended if it exceeds the quantum. With a 50-msec quantum but threads
that block after 5 msec, the thread order for some period of 30 msec might be
A1
,
B1
,
A2
,
B2
,
A3
,
B3
, something not possible with these parameters and user-level
threads. This situation is partially depicted in Fig. 2-44(b).
A major difference between user-level threads and kernel-level threads is the
performance. Doing a thread switch with user-level threads takes a handful of ma-
chine instructions. With kernel-level threads it requires a full context switch,
changing the memory map and invalidating the cache, which is several orders of
magnitude slower.
On the other hand, with kernel-level threads, having a thread
block on I/O does not suspend the entire process as it does with user-level threads.
Since the kernel knows that switching from a thread in process
A
to a thread in
process
B
is more expensive than running a second thread in process
A
(due to hav-
ing to change the memory map and having the memory cache spoiled), it can take
this information into account when making a decision. For example, given two
threads that are otherwise equally important, with one of them belonging to the
same process as a thread that just blocked and one belonging to a different process,
preference could be given to the former.
Another important factor is that user-level threads can employ an applica-
tion-specific thread scheduler. Consider, for example, the Web server of Fig. 2-8.
Suppose that a worker thread has just blocked and the dispatcher thread and two
worker threads are ready. Who should run next? The run-time system, knowing
what all the threads do, can easily pick the dispatcher to run next, so that it can
start another worker running. This strategy maximizes the amount of parallelism in
an environment where workers frequently block on disk I/O.
With kernel-level
threads, the kernel would never know what each thread did (although they could be
assigned different priorities).
In general, however, application-specific thread
schedulers can tune an application better than the kernel can.
2.5 CLASSICAL IPC PROBLEMS
The operating systems literature is full of interesting problems that have been
widely discussed and analyzed using a variety of synchronization methods.
In the
following sections we will examine three of the better-known problems.
2.5.1 The Dining Philosophers Problem
In 1965, Dijkstra posed and then solved a synchronization problem he called
the
dining philosophers problem
.
Since that time, everyone inventing yet another
synchronization primitive has felt obligated to demonstrate how wonderful the new
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
