MODERN OPERATING SYSTEMS Third Edition ANDREW S. TANENBAUM Chapter 2 Processes and Threads Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 2-1. (a) Multiprogramming of four programs. (b) Conceptual model of four independent, sequential processes. (c) Only one program is active at once. The Process Model Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Events which cause process creation: • System initialization. • Execution of a process creation system call by a running process. • A user request to create a new process. • Initiation of a batch job. Process Creation Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Events which cause process termination: • Normal exit (voluntary). • Error exit (voluntary). • Fatal error (involuntary). • Killed by another process (involuntary). Process Termination Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 2-2. A process can be in running, blocked, or ready state. Transitions between these states are as shown. Process States Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 2-3. The lowest layer of a process-structured operating system handles interrupts and scheduling. Above that layer are sequential processes. Implementation of Processes (1) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 2-4. Some of the fields of a typical process table entry. Implementation of Processes (2) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 2-5. Skeleton of what the lowest level of the operating system does when an interrupt occurs. Implementation of Processes (3) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 2-6. CPU utilization as a function of the number of processes in memory. Modeling Multiprogramming Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 2-7. A word processor with three threads. Thread Usage (1) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 2-8. A multithreaded Web server. Thread Usage (2) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 2-9. A rough outline of the code for Fig. 2-8. (a) Dispatcher thread. (b) Worker thread. Thread Usage (3) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 2-10. Three ways to construct a server. Thread Usage (4) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 2-11. (a) Three processes each with one thread. (b) One process with three threads. The Classical Thread Model (1) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 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. The Classical Thread Model (2) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 2-13. Each thread has its own stack. The Classical Thread Model (3) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 2-14. Some of the Pthreads function calls. POSIX Threads (1) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 2-15. An example program using threads. POSIX Threads (2) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639 . . .Figure 2-16. (a) A user-level threads package. (b) A threads package managed by the kernel. Implementing Threads in User Space Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 2-17. Multiplexing user-level threads onto kernel-level threads. Hybrid Implementations Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 2-18. Creation of a new thread when a message arrives. (a) Before the message arrives. (b) After the message arrives. Pop-Up Threads Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 2-19. Conflicts between threads over the use of a global variable. Making Single-Threaded Code Multithreaded (1) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 2-20. Threads can have private global variables. Making Single-Threaded Code Multithreaded (2) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 2-21. Two processes want to access shared memory at the same time. Race Conditions Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Conditions required to avoid race condition: • No two processes may be simultaneously inside their critical regions. • No assumptions may be made about speeds or the number of CPUs. • No process running outside its critical region may block other processes. • No process should have to wait forever to enter its critical region. Critical Regions (1) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 2-22. Mutual exclusion using critical regions. Critical Regions (2) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Proposals for achieving mutual exclusion: • Disabling interrupts • Lock variables • Strict alternation • Peterson's solution • The TSL instruction Mutual Exclusion with Busy Waiting Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 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. Strict Alternation Tanenbaum, Modern Operating