Modern Operating Systems by Herbert Bos ...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf-M ODERN O PERATING S YSTEMS
Showing 564-565 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 564
SEC. 8.1
idle while another is overloaded. Similarly, pages can be allocated among all the
processes dynamically and there is only one buffer cache, so inconsistencies never
The problem with this model is that with many CPUs, the master will become
a bottleneck. After all, it must handle all system calls from all CPUs.
If, say, 10%
of all time is spent handling system calls, then 10 CPUs will pretty much saturate
the master, and with 20 CPUs it will be completely overloaded. Thus this model is
simple and workable for small multiprocessors, but for large ones it fails.
Symmetric Multiprocessors
Our third model, the
Symmetric MultiProcessor
), eliminates this
asymmetry. There is one copy of the operating system in memory, but any CPU
can run it.
When a system call is made, the CPU on which the system call was
made traps to the kernel and processes the system call. The SMP model is illustrat-
ed in Fig. 8-9.
users and
shared OS
users and
shared OS
users and
shared OS
users and
shared OS
Figure 8-9.
The SMP multiprocessor model.
This model balances processes and memory dynamically, since there is only
one set of operating system tables.
It also eliminates the master CPU bottleneck,
since there is no master, but it introduces its own problems.
In particular, if two or
more CPUs are running operating system code at the same time, disaster may well
result. Imagine two CPUs simultaneously picking the same process to run or
claiming the same free memory page. The simplest way around these problems is
to associate a mutex (i.e., lock) with the operating system, making the whole sys-
tem one big critical region. When a CPU wants to run operating system code, it
must first acquire the mutex. If the mutex is locked, it just waits. In this way, any
CPU can run the operating system, but only one at a time.
This approach is some-
things called a
big kernel lock
This model works, but is almost as bad as the master-slave model. Again, sup-
pose that 10% of all run time is spent inside the operating system.
With 20 CPUs,
there will be long queues of CPUs waiting to get in. Fortunately, it is easy to im-
Many parts of the operating system are independent of one another. For

Page 565
example, there is no problem with one CPU running the scheduler while another
CPU is handling a file-system call and a third one is processing a page fault.
This observation leads to splitting the operating system up into multiple inde-
pendent critical regions that do not interact with one another. Each critical region is
protected by its own mutex, so only one CPU at a time can execute it.
In this way,
far more parallelism can be achieved. However, it may well happen that some ta-
bles, such as the process table, are used by multiple critical regions. For example,
the process table is needed for scheduling, but also for the
system call and also
for signal handling. Each table that may be used by multiple critical regions needs
its own mutex. In this way, each critical region can be executed by only one CPU
at a time and each critical table can be accessed by only one CPU at a time.
Most modern multiprocessors use this arrangement. The hard part about writ-
ing the operating system for such a machine is not that the actual code is so dif-
ferent from a regular operating system.
It is not.
The hard part is splitting it into
critical regions that can be executed concurrently by different CPUs without inter-
fering with one another, not even in subtle, indirect ways. In addition, every table
used by two or more critical regions must be separately protected by a mutex and
all code using the table must use the mutex correctly.
Furthermore, great care must be taken to avoid deadlocks.
If two critical re-
gions both need table
and table
, and one of them claims
first and the other
first, sooner or later a deadlock will occur and nobody will know why.
theory, all the tables could be assigned integer values and all the critical regions
could be required to acquire tables in increasing order. This strategy avoids dead-
locks, but it requires the programmer to think very carefully about which tables
each critical region needs and to make the requests in the right order.
As the code evolves over time, a critical region may need a new table it did not
previously need.
If the programmer is new and does not understand the full logic
of the system, then the temptation will be to just grab the mutex on the table at the
point it is needed and release it when it is no longer needed. However reasonable
this may appear, it may lead to deadlocks, which the user will perceive as the sys-
tem freezing. Getting it right is not easy and keeping it right over a period of years
in the face of changing programmers is very difficult.
8.1.3 Multiprocessor Synchronization
The CPUs in a multiprocessor frequently need to synchronize.
We just saw the
case in which kernel critical regions and tables have to be protected by mutexes.
Let us now take a close look at how this synchronization actually works in a multi-
It is far from trivial, as we will soon see.
To start with, proper synchronization primitives are really needed.
If a process
on a uniprocessor machine (just one CPU) makes a system call that requires ac-
cessing some critical kernel table, the kernel code can just disable interrupts before

Ace your assessments! Get Better Grades
Browse thousands of Study Materials & Solutions from your Favorite Schools
Concordia University
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

Students also viewed documents