Processes and Threads
Chapter 2
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
The Process Model (1)
Figure 2-1. (a) Multiprogramming of four programs.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
The Process Model (2)
Figure 2-1. (b) Conceptual model of
four independent, sequential processes.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
The Process Model (3)
Figure 2-1. (c) Only one program is active at once.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Process Creation
Four principal events that cause processes to be
created:
[Link] initialization.
[Link] of a process creation system call by
a running process.
3.A user request to create a new process.
[Link] of a batch job.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Process Termination
Typical conditions which terminate a process:
[Link] exit (voluntary).
[Link] exit (voluntary).
[Link] error (involuntary).
[Link] by another process (involuntary).
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Process States (1)
Three states a process may be in:
[Link] (actually using the CPU at that
instant).
[Link] (runnable; temporarily stopped to let
another process run).
[Link] (unable to run until some external
event happens).
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Process States (2)
Figure 2-2. A process can be in running, blocked, or ready
state. Transitions between these states are as shown.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Process States (3)
Figure 2-3. The lowest layer of a process-structured operating
system handles interrupts and scheduling. Above that layer are
sequential processes.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Implementation of Processes (1)
Figure 2-4. Some of the fields of a typical process table entry.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Implementation of Processes (2)
Figure 2-5. Skeleton of what the lowest level of the operating
system does when an interrupt occurs.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Modeling Multiprogramming
Figure 2-6. CPU utilization as a function of the number of
processes in memory.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Thread Usage (1)
Figure 2-7. A word processor with three threads.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Thread Usage (2)
Figure 2-8. A multithreaded Web server.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Thread Usage (3)
Figure 2-9. A rough outline of the code for Fig. 2-8.
(a) Dispatcher thread. (b) Worker thread.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Thread Usage (4)
Figure 2-10. Three ways to construct a server.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
The Classical Thread Model (1)
Figure 2-11. (a) Three processes each with one thread.
(b) One process with three threads.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
The Classical Thread Model (2)
Figure 2-12. The first column lists some items shared by all
threads in a process. The second one lists some items private
to each thread.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
The Classical Thread Model (3)
Figure 2-13. Each thread has its own stack.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
POSIX Threads (1)
Figure 2-14. Some of the Pthreads function calls.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
POSIX Threads (2)
Figure 2-15. An example program using threads.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
POSIX Threads (3)
Figure 2-15. An example program using threads.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Implementing Threads
in User Space
(a) (b)
Figure 2-16. (a) A user-level threads package.
(b) A threads package managed by the kernel.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Hybrid Implementations
Figure 2-17. Multiplexing user-level threads
onto kernel-level threads.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Pop-Up Threads
Figure 2-18. Creation of a new thread when a message arrives.
(a) Before the message arrives. (b) After the message arrives.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Making Single-Threaded Code
Multithreaded (1)
Figure 2-19. Conflicts between threads over the
use of a global variable.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Making Single-Threaded Code
Multithreaded (2)
Figure 2-20. Threads can have private global variables.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Race Conditions
Figure 2-21. Two processes want to access
shared memory at the same time.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Critical Regions (1)
Requirements to avoid race conditions:
[Link] two processes may be simultaneously inside their
critical regions.
[Link] assumptions may be made about speeds or the
number of CPUs.
[Link] process running outside its critical region may
block other processes.
[Link] process should have to wait forever to enter its
critical region.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Critical Regions (2)
Figure 2-22. Mutual exclusion using critical regions.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Mutual Exclusion with Busy Waiting:
Strict Alternation
Figure 2-23. A proposed solution to the critical region
problem. (a) Process 0. (b) Process 1. In both cases, be sure
to note the semicolons terminating the while statements.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Mutual Exclusion with Busy Waiting:
Peterson’s Solution
Figure 2-24. Peterson’s solution for achieving mutual exclusion.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Mutual Exclusion with Busy Waiting:
The TSL Instruction (1)
Figure 2-25. Entering and leaving a critical region
using the TSL instruction.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Mutual Exclusion with Busy Waiting:
The TSL Instruction (2)
Figure 2-26. Entering and leaving a critical region
using the XCHG instruction
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Sleep and Wakeup
The Producer-Consumer Problem (1)
Figure 2-27. The producer-consumer problem
with a fatal race condition.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Sleep and Wakeup
The Producer-Consumer Problem (2)
Figure 2-27. The producer-consumer problem
with a fatal race condition.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Semaphores (1)
Figure 2-28. The producer-consumer problem
using semaphores.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Semaphores (2)
Figure 2-28. The producer-consumer problem
using semaphores.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Mutexes
Figure 2-29. Implementation of mutex_lock
and mutex_unlock.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Mutexes in Pthreads (1)
Figure 2-30. Some of the Pthreads calls relating to mutexes.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Mutexes in Pthreads (2)
Figure 2-31. Some of the Pthreads calls relating
to condition variables.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Mutexes in Pthreads (3)
Figure 2-32. Using threads to solve the
producer-consumer problem.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Mutexes in Pthreads (4)
Figure 2-32. Using threads to solve the
producer-consumer problem.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Mutexes in Pthreads (5)
Figure 2-32. Using threads to solve the
producer-consumer problem.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Monitors (1)
Figure 2-33. A monitor.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Monitors (2)
Figure 2-34. An outline of the producer-consumer problem with
monitors. Only one monitor procedure at a time is active. The buffer
has N slots.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Monitors (3)
Figure 2-34. An outline of the producer-consumer problem with
monitors. Only one monitor procedure at a time is active. The buffer
has N slots.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Monitors (4)
Figure 2-35. A solution to the producer-consumer
problem in Java.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Monitors (5)
Figure 2-35. A solution to the producer-consumer
problem in Java.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Monitors (6)
Figure 2-35. A solution to the producer-consumer
problem in Java.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
The Producer-Consumer Problem
with Message Passing (1)
Figure 2-36. The producer-consumer
problem with N messages.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
The Producer-Consumer Problem
with Message Passing (2)
Figure 2-36. The producer-consumer
problem with N messages.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Barriers
Figure 2-37. Use of a barrier. (a) Processes approaching a barrier. (b) All
processes but one blocked at the barrier. (c) When the last process
arrives at the barrier, all of them are let through.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Avoiding Locks: Read-Copy-Update (1)
Figure 2-38. Read-Copy-Update: inserting a node in the tree
and then removing a branch—all without locks
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Avoiding Locks: Read-Copy-Update (2)
Figure 2-38. Read-Copy-Update: inserting a node in the tree
and then removing a branch—all without locks
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Introduction to Scheduling
Process Behavior
Figure 2-39. Bursts of CPU usage alternate with periods of waiting
for I/O. (a) A CPU-bound process. (b) An I/O-bound process.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Categories of Scheduling
Algorithms
1. Batch.
2. Interactive.
3. Real time.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Scheduling Algorithm Goals
Figure 2-40. Some goals of the scheduling algorithm under
different circumstances.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Scheduling in Batch Systems
• First-Come First-Served
• Shortest Job First
• Shortest Remaining Time Next
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Shortest Job First
Figure 2-41. An example of shortest job first scheduling.
(a) Running four jobs in the original order.
(b) Running them in shortest job first order.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Scheduling in Interactive Systems
• Round-Robin Scheduling
• Priority Scheduling
• Multiple Queues
• Shortest Process Next
• Guaranteed Scheduling
• Lottery Scheduling
• Fair-Share Scheduling
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Round-Robin Scheduling
Figure 2-42. Round-robin scheduling. (a) The list of
runnable processes. (b) The list of runnable
processes after B uses up its quantum.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Priority Scheduling
Figure 2-43. A scheduling algorithm with four priority classes.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Scheduling in Real-Time Systems
• Time plays an essential role
• Categories
– Hard real time
– Soft real time
– Periodic or aperiodic
• Schedulable satisfies
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Thread Scheduling (1)
Figure 2-44. (a) Possible scheduling of user-level threads with a 50-
msec process quantum and threads that run 5 msec per CPU burst.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Thread Scheduling (2)
Figure 2-44. (b) Possible scheduling of kernel-level threads
with the same characteristics as (a).
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
The Dining Philosophers Problem (1)
Figure 2-45. Lunch time in the Philosophy Department.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
The Dining Philosophers Problem (2)
Figure 2-46. A nonsolution to the dining philosophers problem.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
The Dining Philosophers Problem (3)
Figure 2-47. A solution to the dining philosophers problem.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
The Dining Philosophers Problem (4)
Figure 2-47. A solution to the dining philosophers problem.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
The Dining Philosophers Problem (5)
Figure 2-47. A solution to the dining philosophers problem.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
The Readers and Writers Problem (1)
Figure 2-48. A solution to the readers and writers problem.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
The Readers and Writers Problem (2)
Figure 2-48. A solution to the readers and writers problem.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
End
Chapter 2
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.