Processes & Threads

Operating Systems
Lesson 2
Processes!

2
What is a Program?
Program is a file containing:
• executable code (machine instructions)
• data (information manipulated by these
instructions)
that together describe a computation

• Resides on disk
• Obtained via compilation & linking

3
What is a Process?
• An instance of a program
• An abstraction of a computer:
Address Space + Execution Context + Environment

A good abstraction:
• is portable and hides implementation details
• has an intuitive and easy-to-use interface
• can be instantiated many times
• is efficient and reasonably easy to implement

4
Process != Program
Aprogram is passive:
code + data

Aprocess is alive:
code + data + stack + registers + PC…

Same program can be run simultaneously.

(1 program, 2 processes)

> ./bestprogram &

> ./bestprogram & 5
CPU runs each process directly
But somehow each process has its own:
• Registers
• Memory
• I/O resources
• “thread of control”

6
Process Control Block
(PCB)
• location in memory
For each process, the OS has a
• location of executable on disk PCB containing:
• which user is executing this process
• process privilege level
• process identifier (pid)
• process arguments (for identification with ps)
• process status (Ready, waiting, finished, etc.)
• register values
• scheduling information
• PC, SP, eflags/status register
… and more!
Usually lives on the kernel stack
7
Who should be allowed to start a process?
Possibility #1:
Only the kernel may starta process

Possibility #2:
User-level processes may start processes

8
System Call Interface
Skinny! (why?)

Example:
Creating a Process
System Call
Windows: Interface

CreateProcess(…);

UNIX
fork + exec
9
CreateProcess (Simplified)
System Call:
if (!CreateProcess(
NULL, // No module name (use command line)
argv[1],// Command line
NULL, // Process handle not inheritable
NULL, // Thread handle not inheritable
FALSE, // Set handle inheritance to FALSE
0, // No creation flags
NULL, // Use parent's environment block
NULL, // Use parent's starting directory
&si, // Pointer to STARTUPINFO structure
&pi ) // Ptr to PROCESS_INFORMATION structure
)
[Windows] 10
Beginning a Process via CreateProcess
Kernel has to:
• Allocate ProcessID
• Create & initialize PCB in the kernel
• Create and initialize a new address space
• Load the program into the address space
• Copy arguments into memory in address space
• Initialize h/w context to start execution at “start”
• Inform scheduler that new process is ready to run

[Windows] 11
CreateProcess (Simplified)
System Call: fork (actual form)
int pid = fork( void ☺
NULL, // No module name (use command line)
argv[1],// Command line
NULL, // Process handle not inheritable
NULL, // Thread handle not inheritable
FALSE, // Set handle inheritance to FALSE
0, // No creation flags
NULL, // Use parent's environment block
NULL, // Use parent's starting directory
&si, // Pointer to STARTUPINFO structure
&pi )
)
[UNIX] 12
Beginning a Process via CreateProcess
Kernel has to:
fork()
• Allocate ProcessID
• Create & initialize PCB in the kernel
• Create and initialize a new address space
• Load the program into the address space
• Copy arguments into memory in address space
• Initialize the address space with a copy of the entire
contents of the address space of the parent
• Initialize h/w context to start execution at “start”
• Inherit execution context of parent (e.g., open files)
• Inform scheduler that new process is ready to run

[UNIX] 13
Creating and Managing Processes
Create a child process as a clone of the current
fork process. Returns to both parent and child. Returns
child pid to parent process, 0 to child process.

exec Run the application prog in the current process

(prog, args) with the specified arguments.

wait(pid) Pause until the child process has exited.

Tell the kernel the current process is complete, and its
exit data structures (stack, heap, code) should be garbage
collected. Why not necessarily PCB?
kill Send an interrupt of a specified type to a process.
(pid, type) (a bit of a misnomer, no?)

[UNIX] 14
Fork + Exec
Process 1
Program A
PC child_pid = fork();
if (child_pid==0)
exec(B);
else
wait(child_pid);
child_pid ?

[UNIX] 15
Fork + Exec fork returns
Process 1
Program A twice!
child_pid = fork();
PC if (child_pid==0)
exec(B);
else
wait(child_pid);
child_pid 42
Process 42
Program A
child_pid = fork();
PC if (child_pid==0)
exec(B);
else
wait(child_pid);
child_pid 0
[UNIX] 16
Fork + Exec
Process 1
Program A
child_pid = fork();
if (child_pid==0)
exec(B);
else
PC wait(child_pid); Waits until child exits.
child_pid 42
Process 42
Program A
child_pid = fork();
PC if (child_pid==0)
exec(B);
else
wait(child_pid);
child_pid 0
[UNIX] 17
Fork + Exec
Process 1
Program A
child_pid = fork();
if (child_pid==0)
exec(B);
else
PC wait(child_pid);
child_pid 42
if and else
Process 42 both executed!
Program A
child_pid = fork();
if (child_pid==0)
PC exec(B);
else
wait(child_pid);
child_pid 0
[UNIX] 18
Fork + Exec
Process 1
Program A
child_pid = fork();
if (child_pid==0)
exec(B);
else
PC wait(child_pid);
child_pid 42
Process 42
Program B
PC main() {
...

[UNIX] 19
Fork + Exec
Process 1
Program A
child_pid = fork();
if (child_pid==0)
exec(B);
else
PC wait(child_pid);
child_pid 42

[UNIX] 20
Signals (virtualized interrupt)
Allo applications to behave like operating systems.
w
ID Name Default Action Corresponding Event

Interrupt
2 SIGINT Terminate
(e.g., ctrl-c from keyboard)
Kill program
9 SIGKILL Terminate
(cannot override or ignore)
14 SIGALRM Terminate Timer signal

17 SIGCHLD Ignore Child stopped or terminated

Stop until next Stop signal from terminal
20 SIGTSTP
SIGCONT (e.g. ctrl-z from keyboard)
[UNIX] 21
Sending a Signal
Kernel delivers a signal to a destination process

For one of the following reasons:

• Kernel detected a system event (e.g., div-by-zero
(SIGFPE) or termination of a child (SIGCHLD))
• A process invoked the kill system call requesting
kernel to send signal to another process
- debugging
- suspension
- resumption
- timer expiration

22
Receiving a Signal
A destination process receives a signal when
it is forced by the kernel to react in some way
to the delivery of the signal.

Three possible ways to react:

1. Ignore the signal (do nothing)
2. Terminate process (+ optional core dump)
3. Catch the signal by executing a user-level
function called signal handler
- Like a hardware exception handler being called in
response to an asynchronous interrupt
23
Signal Example (signal.c)
int main() {
pid_t pid[N];
int i, child_status;

for (i = 0; i < N; i++) // N forks

if ((pid[i] = fork()) == 0) {
while(1); //child infinite loop
}
/* Parent terminates the child processes */
for (i = 0; i < N; i++) { // parent continues executing
printf("Killing proc. %d\n", pid[i]);
kill(pid[i], SIGINT);
}
/* Parent reaps terminated children */
for (i = 0; i < N; i++) {
pid_t wpid = wait(&child_status);
if (WIFEXITED(child_status)) // parent checks for each child’s exit
printf("Child %d terminated w/exit status %d\n", wpid,
WEXITSTATUS(child_status));
else
printf("Child %d terminated abnormally\n", wpid);
}
exit(0); 24
}
Handler Example (handler.c)
void int_handler(int sig) {
printf("Process %d received signal %d\n", getpid(), sig);
exit(0);
}
int main() {
pid_t pid[N];
int i, child_status;
signal(SIGINT, int_handler); //register handler for SIGINT
for (i = 0; i < N; i++) // N forks
if ((pid[i] = fork()) == 0) {
while(1); //child infinite loop
}
for (i = 0; i < N; i++) { // parent continues executing
printf("Killing proc. %d\n", pid[i]);
kill(pid[i], SIGINT);
}
for (i = 0; i < N; i++) {
pid_t wpid = wait(&child_status);
if (WIFEXITED(child_status)) // parent checks for each child’s exit
printf("Child %d terminated w/exit status %d\n", wpid,
WEXITSTATUS(child_status));
else
printf("Child %d terminated abnormally\n", wpid);
}
exit(0); 25
}
Context Switch
• Exchange current running process for
another runnable process
• Similar to interrupt handling:
• Save the registers of process 1 on its stack
• Save the SP and PC of process 1 in its PCB
• Restore the SP and PC of process 2 from its
PCB
• Restore the registers of process 2 from its
stack
• Also: change virtual memory address
space from process 1 to process 2*
(Virtual memory details coming later) 26
Threads!

Other terms for threads:

• Lightweight Process
• Thread of Control
• Task
27
 0xFFFFFFFF
What happens when… Mail

Apache wants to run multiple

Emacs
concurrent computations?
Stack
Two heavyweight address Heap Apache
spaces for two concurrent Data
computations? Insns
Apache
Stack
What is distinct about
Heap
these address spaces?
Data
Insns Kernel
Physical address space PCBs
Each process’ address space by color
(shown contiguous to look nicer) 0x00000000 28
 0xFFFFFFFF
Idea Mail

Emacs

Place concurrent
computations in the Stack 2
same address space! Stack 1
Heap Apache
Data
Insns
Kernel
Physical address space PCBs
Each process’ address space by color
(shown contiguous to look nicer) 0x00000000 29
Process vs. Thread
Process:
• Privilege Level
• Address Space Code,
• Data, Heap Shared
• I/O resources
• One or more Threads:
• Stack
• Registers
• PC, SP
30
Thread Memory Layout
Thread 1 Stack 1
SP
PC Stack 2

Thread 2 Stack 3
SP
PC
Data
Thread 3
SP
PC Insns

Virtual
Address
(Heap subdivided, shared, & not shown.) Space 31
Processes and Threads
Process abstraction combines two concepts
• Concurrency: each process is a sequential
execution stream of instructions
• Protection: Each process has own address
space
Threads decouple concurrency & protection
• A thread represents a sequential execution
stream of instructions.
• Aprocess defines the address space that may
be shared by multiple threads
• Threads must be mutually trusting. Why?
32
Thread: abstraction for concurrency
A single-execution stream of instructions;
represents a separately schedulable task
• OS can run, suspend, resume it at any time
• bound to a process
• execution speed is unspecified, non-zero
Virtualizes the processor
• programs run on machine with an infinite
number of processors (hint: not true!)

33
Why Threads?
Performance: exploiting multiple processors
Do threads make sense on a single core?
Encourages natural program structure
• Expressing logically concurrent tasks
• update screen, fetching data, receive user input
Responsiveness
• splitting commands, spawn threads to do work
in the background
Mask long latency of I/O devices
• do useful work while waiting 34
Some Thread Examples
for (k = 0; k < n; k++) {
a[k] = b[k] × c[k] + d[k] × e[k]
}

Web server:
1. get network message (URL) from client
2. get URL data from disk
3. compose response
4. send response
35
 Processes vs. Threads
• Have data/code/heap/stack • Have own stack
• Have at least one thread • 1+ threads live in a process
• Process dies → resources • Thread dies → its stack
reclaimed, its threads die reclaimed
• Interprocess communication • Inter-thread communication
via OS and data copying via memory
• Have own address space, • Have own stack and regs,
isolated from other but no isolation from other
processes’ threads in the same process
• Expensive creation and • Inexpensive creation and
context switch context switch

• Each can run on a different processor 36

Simple Thread API
void
Creates a new thread in thread, which will execute
thread_create function func with the arguments arg
(thread,func,arg)

void Calling thread gives up processor. Scheduler can

thread_yield() resume running this thread at any point.

int Wait for thread to finish, then return the value

thread_join thread passed to thread_exit.
(thread ) May be called only once for each thread.
void
Finish caller; store ret in caller’s TCB and wake up
thread_exit
any thread that invoked thread_join(caller).
(re t)

37
 0xFFFFFFFF
#1: Kernel-Level Threads Mail

Kernel knows about, schedules Emacs

threads (just like processes)

Stack 2
• Threads share virtual
Stack 1
address space Heap Apache
• Separate PCB (TCB) Data
for each thread Insns
• PCBs have: Kernel
• same: page table base reg. PCBs

• different: PC, SP, registers 0x00000000 38

 0xFFFFFFFF
#2: User-Level Threads Mail

Build a mini-OS in user space Emacs

• Real OS unaware of threads
• Single PCB “os” stack
stack 1
Generally more efficient stack 2
than kernel-level threads Heap Apache
(Why?) Data
Insns
But kernel-level threads simplify Kernel
system call handling and
PCBs
scheduling (Why?)
0x00000000 39
Thread LifeCycle

Init Finished

Ready Running

Waiting

Processes go through these states, too. 40

Thread creation

Init Finished

Ready Running

Waiting

TCB status:being created

Registers: in TCB 41
Thread is Ready to Run

Init Finished

Admitted to
Run Queue
Ready Running

Waiting

TCB: on Ready list

Registers: in TCB 42
Thread is Running

Init Finished

Admitted to
Run Queue
dispatch
Ready Running

Waiting

TCB: on Running list

Registers: Processor 43
Thread Yields (back to Ready)
yield,
interrupt,
Init descheduled Finished

Admitted to
Run Queue
dispatch
Ready Running

Waiting

TCB: on Ready list

Registers: in TCB 44
Thread is Running Again!
yield,
interrupt,
Init descheduled Finished

Admitted to
Run Queue
dispatch
Ready Running

Waiting

TCB: on Running list

Registers: Processor 45
Thread is Waiting
yield,
interrupt,
Init descheduled Finished

Admitted to
Run Queue
dispatch
Ready Running

I/O operation
join(), wait()
Waiting

TCB: on Waiting list (scheduler’s or other)

Registers: TCB 46
Thread is Ready Again!
yield,
interrupt,
Init descheduled Finished

Admitted to
Run Queue
dispatch
Ready Running

I/O or thread I/O operation

completion join(), wait()
Waiting

TCB: on Ready list

Registers: in TCB 47
Thread is Running Again!
yield,
interrupt,
Init descheduled Finished

Admitted to
Run Queue
dispatch
Ready Running

I/O or thread I/O operation

completion join(), wait()
Waiting

TCB: on Running list

Registers: Processor 48
Thread is Finished (Process = Zombie)
yield,
interrupt,
Init descheduled Finished

Admitted to done,
Run Queue thread_exit()
dispatch
Ready Running

I/O or thread I/O operation

completion join(), wait()
Waiting

TCB: on Finished list (to pass exit value), ultimately deleted

Registers: TCB 49
Do not presume to know the schedule

Synchronization
Matters!

50