Processes and Threads
Chapter 2
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
The Process Model (1)
Figure 2-1. (a) Multiprogramming of four programs.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
The Process Model (2)
Figure 2-1. (b) Conceptual model of
four independent, sequential processes.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
The Process Model (3)
Figure 2-1. (c) Only one program is active at once.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Process Creation
Four principal events that cause processes to be
created:
1. System initialization.
2. Execution of a process creation system call by
a running process.
3. A user request to create a new process.
4. Initiation of a batch job.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Process Termination
Typical conditions which terminate a process:
1. Normal exit (voluntary).
2. Error exit (voluntary).
3. Fatal error (involuntary).
4. Killed by another process (involuntary).
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Process States (1)
Three states a process may be in:
1. Running (actually using the CPU at that
instant).
2. Ready (runnable; temporarily stopped to let
another process run).
3. Blocked (unable to run until some external
event happens).
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. 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 & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. 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 & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Implementation of Processes (1)
Figure 2-4. Some of the fields of a typical process table entry.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. 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 & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Modeling Multiprogramming
Figure 2-6. CPU utilization as a function of the number of
processes in memory.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Thread Usage (1)
Figure 2-7. A word processor with three threads.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Thread Usage (2)
Figure 2-8. A multithreaded Web server.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. 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 & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Thread Usage (4)
Figure 2-10. Three ways to construct a server.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. 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 & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. 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 & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
The Classical Thread Model (3)
Figure 2-13. Each thread has its own stack.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
POSIX Threads (1)
Figure 2-14. Some of the Pthreads function calls.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
POSIX Threads (2)
Figure 2-15. An example program using threads.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
POSIX Threads (3)
Figure 2-15. An example program using threads.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. 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 & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Hybrid Implementations
Figure 2-17. Multiplexing user-level threads
onto kernel-level threads.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. 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 & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Making Single-Threaded Code
Multithreaded (1)
Figure 2-19. Conflicts between threads over the
use of a global variable.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Making Single-Threaded Code
Multithreaded (2)
Figure 2-20. Threads can have private global variables.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Race Conditions
Figure 2-21. Two processes want to access
shared memory at the same time.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Critical Regions (1)
Requirements to avoid race conditions:
1. No two processes may be simultaneously inside
their critical regions.
2. No assumptions may be made about speeds or the
number of CPUs.
3. No process running outside its critical region may
block other processes.
4. No process should have to wait forever to enter its
critical region.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Critical Regions (2)
Figure 2-22. Mutual exclusion using critical regions.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. 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 & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Mutual Exclusion with Busy Waiting:
Peterson’s Solution
Figure 2-24. Peterson’s solution for achieving mutual exclusion.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. 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 & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. 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 & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Sleep and Wakeup
The Producer-Consumer Problem (1)
Figure 2-27. The producer-consumer problem
with a fatal race condition.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Sleep and Wakeup
The Producer-Consumer Problem (2)
Figure 2-27. The producer-consumer problem
with a fatal race condition.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Semaphores (1)
Figure 2-28. The producer-consumer problem
using semaphores.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Semaphores (2)
Figure 2-28. The producer-consumer problem
using semaphores.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Mutexes
Figure 2-29. Implementation of mutex_lock
and mutex_unlock.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Mutexes in Pthreads (1)
Figure 2-30. Some of the Pthreads calls relating to mutexes.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Mutexes in Pthreads (2)
Figure 2-31. Some of the Pthreads calls relating
to condition variables.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Mutexes in Pthreads (3)
Figure 2-32. Using threads to solve the
producer-consumer problem.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Mutexes in Pthreads (4)
Figure 2-32. Using threads to solve the
producer-consumer problem.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Mutexes in Pthreads (5)
Figure 2-32. Using threads to solve the
producer-consumer problem.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Monitors (1)
Figure 2-33. A monitor.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. 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 & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. 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 & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Monitors (4)
Figure 2-35. A solution to the producer-consumer
problem in Java.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Monitors (5)
Figure 2-35. A solution to the producer-consumer
problem in Java.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Monitors (6)
Figure 2-35. A solution to the producer-consumer
problem in Java.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
The Producer-Consumer Problem
with Message Passing (1)
Figure 2-36. The producer-consumer
problem with N messages.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
The Producer-Consumer Problem
with Message Passing (2)
Figure 2-36. The producer-consumer
problem with N messages.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. 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 & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. 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 & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. 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 & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. 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 & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Categories of Scheduling
Algorithms
1. Batch.
2. Interactive.
3. Real time.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Scheduling Algorithm Goals
Figure 2-40. Some goals of the scheduling algorithm under
different circumstances.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Scheduling in Batch Systems
• First-Come First-Served
• Shortest Job First
• Shortest Remaining Time Next
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. 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 & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. 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 & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. 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 & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Priority Scheduling
Figure 2-43. A scheduling algorithm with four priority classes.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. 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 & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. 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 & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Thread Scheduling (2)
Figure 2-44. (b) Possible scheduling of kernel-level threads
with the same characteristics as (a).
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
The Dining Philosophers Problem (1)
Figure 2-45. Lunch time in the Philosophy Department.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
The Dining Philosophers Problem (2)
Figure 2-46. A nonsolution to the dining philosophers problem.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
The Dining Philosophers Problem (3)
Figure 2-47. A solution to the dining philosophers problem.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
The Dining Philosophers Problem (4)
Figure 2-47. A solution to the dining philosophers problem.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
The Dining Philosophers Problem (5)
Figure 2-47. A solution to the dining philosophers problem.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
The Readers and Writers Problem (1)
Figure 2-48. A solution to the readers and writers problem.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
The Readers and Writers Problem (2)
Figure 2-48. A solution to the readers and writers problem.
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
End
Chapter 2
Tanenbaum & Bo,Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
