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-6006639
 PROCESSES
process: an abstraction of a running program.

A program in this state of execution is what

we call a process.
A program exists on a hard drive; a process
exists in RAM.
They support the ability to have (pseudo)
concurrent operation even when there is only one
CPU available. They turn a single CPU into multiple
virtual CPUs. Without the process abstraction,
modern computing could not exist.
 The Process Model

Figure 2-1. (a) Multiprogramming of four programs. (b) Conceptual

model of four independent, sequential processes. (c) Only
one program is active at once.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 Process Creation

Events 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.

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Process Termination

After a process has been created, it starts running and does whatever
its job [Link], nothing lasts forever, not even processes. Sooner or
later the new process will terminate, usually due to one of the
following conditions:
1. Normal exit .
2. Error exit .
3. Fatal error .
4. Killed by another process .
Events which cause process termination:

• Normal exit (voluntary).

• Error exit (voluntary).
• Fatal error (involuntary).
• Killed by another process (involuntary).

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
[Link] processes terminate because they have done their work. When
a compiler has compiled the program given to it, the compiler executes
a system call to tell the operating system that it is finished. This call is
exit in UNIX and ExitProcess in Windows.
[Link]-oriented programs also support voluntary termination. Word
processors, Internet browsers, and similar programs always have an
icon or menu item that the user can click to tell the process to remove
any temporary files it has open and then terminate.
[Link] second reason for termination is that the process
discovers a fatal [Link] example, if a user types the
command
cc foo.c
to compile the program foo.c and no such file exists, the
compiler simply announces this fact and exits.

[Link] third reason for termination is an error caused by

the process, often due to
a program bug. Examples include executing an illegal
instruction, referencing
nonexistent memory, or dividing by zero.
 Process Hierarchies
• Parent creates a child process, child processes can create its own child process
• Forms a hierarchy – UNIX calls this a "process group"
• Windows has no concept of process hierarchy –
all processes are created equal
• In some systems, when a process creates another process, the parent process and
child process continue to be associated in certain ways.
• The child process can itself create more processes, forming a process hierarchy.
• After the computer is booted. A special process, called init, is present in the boot
image.
• When it starts running, it reads a file telling how many terminals there are. Then it
forks off a new process per terminal. These processes wait for someone to log in. If a
login is successful, the login process executes a shell to accept commands.
• These commands may startup more processes, and so forth. Thus, all the processes
in the whole system belongto a single tree, with init at the root.
• In contrast, Windows has no concept of a process hierarchy. All processes are
equal.
• The only hint of a process hierarchy is that when a process is created, the parent
is given a special token (called a handle) that it can use to control the child.
• However, it is free to pass this token to some other process, thus invalidating the
hierarchy.
 Process States
• Although each process is an independent entity, with its own program counter
and internal state, processes often need to interact with other processes. One
processmay generate some output that another process uses as input. In the
shell command
• Three state of process
[Link] (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).
Figure 2-2. A process can be in running, blocked, or ready state.
Transitions between these states are as shown.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 Process Management Operations

• Process creation and termination

• Process scheduling and dispatching
• Process switching
• Process synchronization and support for inter-process communication
•
The OS maintains process data in the
• Process Control Blocks (PCB)
Process Control Block
Figure 2-3. The lowest layer of a process-structured operating
system handles interrupts and scheduling. Above that layer
are sequential processes.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
• When a process blocks, it does so because logically it cannot continue, typically
because it is waiting for input that is not yet available.
• It is also possible for a process that is conceptually ready and able to run to be
stopped because the operating system has decided to allocate the CPU to
another process for a while.
• Here the lowest level of the operating system is the scheduler, with a variety of
processes on top of it.
• All the interrupt handling and details of actually starting and stopping processes
are hidden away in what is here called the scheduler, which is actually not much
code.
• The rest of the operating system is nicely structured in process form. Few real
systems are as nicely structured as this however.
 Thread
• A thread refers to a single sequential flow of activities being executed in a
process; it is also known as the thread of execution or the thread of control.
Now, thread execution is possible within any OS's process. Apart from that, a
process can have several threads.
• Each process has an address space and a single thread of control. In fact, that is
almost the definition of a process. Nevertheless, in many situations, it is
desirable to have multiple threads of control in the same address space running
in quasi-parallel, as though they were (almost) separate processes (except for the
shared address space).
 Main reason for having threads

• In many applications, multiple activities are going on at once.

• Threads is that since they are lighter weight than processes
• Threads is also a performance argument
• Threads are useful on systems with multiple CPUs
 Thread Usage (1)

Figure 2-7. A word processor with three threads.

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 Thread Usage (2)

Figure 2-8. A multithreaded Web server.

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 Implementing Threads in User Space

• The first method is to put the threads package entirely in userspace. The kernel
knows nothing about them.
• When threads are managed in user space, each process needs its own private
thread table to keep track of the threads in that process.
• If thread is blocked due to some reason-If so, it stores the thread’s registers (i.e.,
its own) in the thread table, looks in the table for a ready thread to run, and
reloads the machine registers with the new thread’s saved values.
• System call is required for blocking -thread yield
 Implementing Threads in User Space

Figure 2-16. (a) A user-level threads package. (b) A threads

package managed by the kernel.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 Implementing Threads in the Kernel
• Now let us consider having the kernel know about and manage the threads. No
run-time system is needed in each, as shown in Fig. 2-16(b).
• Also, there is no thread table in each process. Instead, the kernel has a thread
table that keeps track of all the threads in the system.
• When a thread wants to create a new thread or destroy an existing thread, it
makes a kernel call, which then does the creation or destruction by updating the
kernel thread table.
• Kernel threads do not require any new, nonblocking system calls.
• Issue- when signal is received which thread should handle it
 Hybrid Implementations

Figure 2-17. Multiplexing user-level threads

onto kernel-level threads.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 Scheduling – Process Behavior

Figure 2-38. Bursts of CPU usage alternate with periods of waiting

for I/O. (a) A CPU-bound process. (b) An I/O-bound process.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Categories of Scheduling Algorithms

• Batch
• Interactive
• Real time

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 Scheduling Algorithm Goals

Figure 2-39. Some goals of the scheduling algorithm under

different circumstances.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 Scheduling in Batch Systems

• First-come first-served
• Shortest job first
• Shortest remaining Time next

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 Shortest Job First

Figure 2-40. An example of shortest job first scheduling.

(a) Running four jobs in the original order. (b) Running them
in shortest job first order.

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Scheduling in Interactive Systems

• Round-robin scheduling
• Priority scheduling
• Multiple queues
• Shortest process next
• Guaranteed scheduling
• Lottery scheduling
• Fair-share scheduling

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 Round-Robin Scheduling

Figure 2-41. Round-robin scheduling.

(a) The list of runnable processes. (b) The list of runnable
processes after B uses up its quantum.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 Priority Scheduling

Figure 2-42. A scheduling algorithm with four priority classes.

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639