02-Processes-Threads.pptx
Processes and Threads
Processes
Non-determinism & concurrency
Why multiple processes
Process creation, termination, switching and PCBs
Linux Case Study
Threads
Concepts and models
Threads vs processes
Posix PThread case study
Kernel and user threads
2
Introduction to Processes
• One of the oldest abstractions in computing
– An abstraction of a running program
– Encapsulates code and state of a program
• Allows a single processor to run multiple
programs “simultaneously”
– Processes turn a single CPU into multiple virtual
CPUs
– Each process runs on a virtual CPU
3
Why Have Processes?
• Provide (the illusion of) concurrency
– Real vs. apparent concurrency
• Provide isolation
– Each process has its own address space
• Simplicity of programming
– E.g. Firefox does not need to worry about gcc
• Allow better utilization of machine resources
– Different processes require different resources at a certain
time
4
EXAMPLE: Print spooler
Consider Operating System as a
set of co-operating concurrent
processes.
Word
processor
Print
Request
Keyboard & screen: processes to manage these devices
Word processor: User edits document, requests printing
Print queue manager: Maintains queue of jobs for printer. If queue was previously
empty, starts printer process.
Printer Process:Translates document to printer commands, and sends them to it.
On completion, removes job from queue, and repeats. Terminates when queue
is empty.
Printer
Process
Print
queue
manager
Laser
Printer
Print
queue
Keyboard
Screen
Processes for OS Structuring
5
Non – Determinism
• Operating Systems and Real-Time systems are
non-deterministic
• They must respond to events (I/O) which occur in an
unpredictable order, and at any time
6
• Apparent Concurrency (pseudo-concurrency): A single
hardware processor which is switched between processes by
interleaving. Over a period of time this gives the illusion of
concurrent execution.
• Real Concurrency: Multiple hardware processors;
usually less processors than processes
Concurrency
7
Process Switches
• Events (or interrupts) cause process switches.
– For example, an I/O completion interrupt will cause the OS to
switch to an I/O process
The way an OS switches between processes cannot be
pre-determined, since the events which cause the
switches are not deterministic
• The interleaving of instructions, executed by a processor,
from a set of processes is non-deterministic
– Not reproducible, no built-in assumptions about timing
8
Fairness
gcc
gcc
firefox
firefox gcc
9
Better CPU utilization
firefox
gcc
firefox
Waiting
for input
Input
arrives
menti.com Multiprogramming Q1 98 63 88
10
Why Multiprogramming?
• Why do most Operating Systems provide multiprogramming?
12
CPU Utilization in Multiprogramming
Q: Average process computes 20% time, then with five processes we
should have 100% CPU utilization, right?
A: In the ideal case, if the five processes never wait for I/O at the
same time
• Better estimate
§ n = total number of processes
§ p = fraction of time a process is waiting for I/O
§ pn = probability that all processes are waiting for I/O
CPU utilization = 1 – pn
Q: How many processes need to be in memory to only waste 10% of
CPU where we know that processes spend 80% waiting for I/O
(e.g. data oriented or interactive systems)?
menti.com Q2 CPU utilization 98 63 88
14
CPU Utilization = 1 – pn
No. of processes (Degree of multiprogramming)
15
Context Switches
• On a context switch, the processor switches from
executing process A to executing process B, because:
– Time slice expired (periodic)
– Process A blocked waiting for e.g. I/O or a resource
– Process A completed (run to completion)
– External event results in a higher priority process B to be
run (priority preemption)
• Non-deterministic process switches as events causing
them are non-deterministic.
16
Context Switches
• On a context switch, the processor switches from
executing process A to executing process B
• Process A may be restarted later, therefore, all
information concerning the process, needed to restart
safely, should be stored
• For each process, all this data is stored in a process
descriptor, or process control block (PCB), which is kept
in the process table
17
Process Control Block (PCB)
• A process has its own virtual machine, e.g.:
– Its own virtual CPU
– Its own address space (stack, heap, text, data etc.)
– Open file descriptors, etc.
• What state information should be stored?
– Program counter (PC), page table register, stack pointer,
etc.
– Process management info:
• Process ID (PID), parent process, process group, priority,
CPU used, etc.
– File management info
• Root directory, working directory, open file descriptors, etc.
18
Simplified Process Control Block (PCB)
• PCB: Data structure representing a process in the kernel
– Process IDs: unique identifier to distinguish it from other
processes.
– State: running, waiting, ready etc. (details later)
– Priority: priority level relative to other processes
– Program counter: address of next instruction in program to be
executed
– Context data: data saved from registers
– Memory pointers: to program code, data associated with
process and shared memory with other processes
– I/O status: I/O requests outstanding, I/O devices allocated
– File Management: Required directories, list of open files
– Accounting information: processor time used, time limits,
memory limits, file usage + limits etc
19
Detailed PCB
Process List Structures
20
Running
Ready
Blocked
Process
Control Block
Figure 3.14 Process List Structures
21
Process in Memory
Stack: temporary data e.g.
function parameters, return
addresses, local variables.
Heap: dynamically allocated data
structures.
Data: global variables
Text: program code
Multiple processes can
share code e.g. 2
concurrent word processors
can edit different files,
using same code.
Stack
Heap
Data
Text (Code)
0
max
Process Switch Implementation
1. Each IO class has interrupt
vector containing the
address of interrupt service
procedure
2. On interrupt the PC, PSW,
some registers pushed onto
the (current) stack by the
interrupt hardware
3. Hardware jumps to address
(PC from Interrupt vector)
to service interrupt
4. Assembly language routine
saves registers to PCB then
calls device specific
interrupt service routine
5. C interrupt service runs
(typically reads, writes &
buffers data)
6. Scheduler decides which
process to run next
7. C procedure returns
control to assembly code
8. Assembly procedure starts
up new current process
22
23
Context (Process) Switches are Expensive
• Direct cost: save/restore process state
• Indirect cost: perturbation of memory caches, memory
management registers etc.
• Important to avoid unnecessary context switches
24
Process Creation
• When are processes created?
– System initialisation
– User request
– System call by a running process
• Processes can be
– Foreground processes: interact with users
– Background processes: handle incoming mail, printing
requests, etc. (daemons)
25
Process Termination
• Normal completion: Process completes execution of
body
• System call:
§ exit() in UNIX
§ ExitProcess() in Windows
• Abnormal exit: The process has run into an error or an
unhandled exception, e.g. illegal instruction, memory
violation
• Aborted: The process stops because another process
has overruled its execution (e.g., killed from terminal)
• Never: Many real-time processes run in endless loop
and never terminate unless error occurs
26
Process Hierarchies
• Some OSes (e.g., UNIX) allow processes to create process
hierarchies e.g. parent, child, child’s child, etc.
– E.g., when UNIX boots it starts running init
– It reads a file saying how many terminals to run, and forks off
one process per terminal
– They wait for someone to login
– When login successful login process executes a shell to accept
commands which in turn may start up more processes etc.
– All processes in the entire system form a process tree with init
as the root (process group)
• Windows has no notion of hierarchy
– When a child process is created the parent is given a token
(handle) to use to control it
– The handle can be passed to other processes thus no hierarchy
27
Hardware Support for Multiprogramming
• Explain why multiprogramming systems require:
•
• a) Hardware interrupts from I/O devices
• b) Independent direct memory access channel
Case Study: Linux
30
Creating processes
§ Creates a new child process by making an exact copy of the
parent process image.
§ The child process inherits the resources of the parent process
and will be executed concurrently with the parent process.
§ fork() returns twice:
– In the parent process: fork() returns the process ID of the child
– In the child process: fork() returns 0
§ On error, no child is created and -1 is returned in the parent
§ How can fork() fail?
– Global process limit exceeded, per-user limit exceeded,
not enough swap space
int fork(void)
31
fork() example (1)
#include
#include
int main() {
if (fork() != 0)
printf(“Parent code\n”);
else printf(“Child code\n”);
printf(“Common code\n”);
}
1
2
“Parent code”
“Common code”
“Child code”
“Common code”
32
fork() example (2)
#include
#include
int main() {
if (fork() != 0)
printf(“X\n”);
if (fork() != 0)
printf(“Y\n”);
printf(“Z\n”);
}
What does initial
process print?
menti.com Q3: 98 63 88
34
Executing processes
• Arguments:
§ path – full pathname of program to run
§ argv – arguments passed to main
§ envp – environment variables (e.g., $PATH, $HOME)
• Changes process image and runs new process
• Lots of useful wrappers:
E.g., execl, execle, execvp, execv, etc.
int execve(const char *path, char *const argv[],
char *const envp[])
man execve
Consult man(ual) pages!
35
Waiting for Process Termination
§Suspends execution of the calling process until the
process with PID pid terminates normally or a signal is
received
§Can wait for more than one child:
– pid = -1 wait for any child
– pid = 0 wait for any child in the same process group as caller
– pid = -gid wait for any child with process group gid
§Returns:
– pid of the terminated child process
– 0 if WNOHANG is set in options (indicating the call should not
block) and there are no terminated children
– -1 on error, with errno set to indicate the error
int waitpid(int pid, int* stat, int options)
36
Example: Command Interpreter
• Use of fork, execve and waitpid
37
Why both fork() and execve() ?
• UNIX design philosophy: simplicity
– Simple basic blocks that can be easily combined
• Contrast with Windows:
– CreateProcess() => equivalent of fork() + execve()
– Call has 10 parameters!
• program to be executed
• parameters
• security attributes
• meta data regarding files
• priority,
• pointer to the structure in which info regarding new process
is stored and communicated to the caller
• …
38
Windows CreateProcess()
BOOL WINAPI CreateProcess(
__in_opt LPCTSTR lpApplicationName,
__inout_opt LPTSTR lpCommandLine,
__in_opt LPSECURITY_ATTRIBUTES lpProcessAttributes,
__in_opt LPSECURITY_ATTRIBUTES lpThreadAttributes,
__in BOOL bInheritHandles,
__in DWORD dwCreationFlags,
__in_opt LPVOID lpEnvironment,
__in_opt LPCTSTR lpCurrentDirectory,
__in LPSTARTUPINFO lpStartupInfo,
__out LPPROCESS_INFORMATION lpProcessInformation )
39
Linux Termination
– Terminates a process
– Called implicitly when program finishes execution
– Never returns in the calling process
– Returns an exit status to the parent.
–Sends signal sig to process pid to terminate it.
void exit(int status)
void kill(int pid, int sig)
Peter R. Pietzuch
prp@doc.ic.ac.uk
Threads
41
What Are Threads?
• Execution streams that share the same address
space
• When multithreading is used, each process can
contain one or more threads
– a lightweight mini-process within a user process
3 Processes, each with 1 thread 1 process with 3 threads
One or More Threads
in a Process
• an execution state (Running, Ready, etc.)
• saved thread context when not running
• an execution stack
• some per-thread static storage for local
variables
• access to the memory and resources of its
process (all threads of a process share this)
Each thread has:
43
Thread Model
Per process items Per thread items
Address space Program counter (PC)
Global variables Registers
Open files Stack
Child processes State
Pending alarms
Signals and signal handlers
Accounting information
44
Thread Model (2)
Multithreaded Process Model
• Each thread has its own stack & context
45
Registers for Threads
• The register set is a per-thread rather than a per-process
item. Why? After all, the machine has only one set of
registers.
Output thread
• writes output buffer
to disk
Example Word Processor
Input thread
• reads data into buffer
Processing thread
• processes input buffer
• writes result into output buffer
48
Example Multi-threaded Web Server
Threads vs Proceses
Processes are too
heavyweight
– Expensive to
create/destroy activities
– Difficult to communicate
between different
address spaces
– An activity that blocks
might switch out the
entire application
– Expensive to context
switch between activities
Threads are lightweight
– Create/delete up to 100
times quicker
– Activities can share data
– Efficient communication
between threads
– Reflect parallelism
within application,
where some activities
may block
49
50
Threads – Problems/Concerns
• Shared address space
– Memory corruption
• One thread can write another thread’s stack
– Concurrency bugs
• Concurrent access to shared data (e.g., global variables)
• Forking
– What happens on a fork()?
• Create a new process with the same number of threads
• Create a new process with a single thread?
– Single thread i.e. the thread which executed fork
• Signals
– When a signal arrives, which thread should handle it?
– For fault, the thread causing the fault
– For other signal e.g. SIGALARM, any thread
51
Case Study: PThreads
52
PThreads (Posix Threads)
• Defined by IEEE standard 1003.1c
– Implemented by most UNIX systems
#include
pthread_t à type representing a thread
pthread_attr_t à type representing the attributes of a thread
53
Creating Threads
Creates a new thread
– The newly created thread is stored in *thread
– The function returns 0 if thread was successfully created, or error
code
Arguments:
– attr -> specifies thread attributes, can be NULL for default
attributes
• Attributes include: minimum stack size, guard size, detached/ joinable, etc.
– start_routine -> the C function the thread will start to execute
once created
– arg -> The argument to be passed to start_routine (of pointer type
void*). Can be NULL if no arguments are to be passed.
int pthread_create(pthread_t *thread,
const pthread_attr_t *attr,
void *(*start_routine)(void*), void *arg);
54
Terminating Threads
• Terminates the thread and makes value_ptr available to
any successful join with the terminating thread
• Called implicitly when the thread’s start routine returns
– But not for the initial thread which started main()
– If main() terminates before other threads, w/o calling
pthread_exit(), the entire process is terminated
– If pthread_exit() is called in main()the process
continues executing until the last thread terminates (or
exit() is called)
void pthread_exit(void *value_ptr);
55
PThread Example
#include #include void *thread_work(void *threadid) { long id = (long) threadid; printf(“Thread %ld\n”, id); } int main (int argc, char *argv[]) { pthread_t threads[5]; long t; for (t=0; t<5; t++)
pthread_create(&threads[t], NULL,
thread_work, (void *)t);
}
$ gcc pt.c –lpthread
$ ./a.out
Thread 0
Thread 1
Thread 2
Thread 3
Thread 4
$ ./a.out
Thread 0
Thread 3
Thread 1
Thread 2
56
Passing Arguments to Threads
• What if we want to pass more than one argument to the
start routine?
– Create a structure containing the arguments and pass a
pointer to that structure to pthread_create()
57
Yielding the CPU
• Releases the CPU to let another thread run
• Returns 0 on success, or an error code
• Always succeeds on Linux
int pthread_yield(void)
• Why would a thread ever voluntarily give up the CPU by
calling thread yield()?
After all, since there is no periodic clock interrupts, it
may never get the CPU back.
59
Joining Other Threads
• Blocks until thread terminates
• The value passed to pthread_exit() by the terminating
thread is available in the location referenced by
value_ptr
– value_ptr can be NULL
int pthread_join(pthread_t thread, void **value_ptr);
60
Join Example
#include #include long a, b, c; void *work1(void *x) { a = (long)x * void *work2(void *y) { b = (long)y * int main (int argc, char *argv[]) { pthread_t t1, t2; pthread_create(&t1, NULL, work1, (void*) pthread_create(&t2, NULL, work2, (void*) pthread_join(t1, NULL); pthread_join(t2, NULL); c = a + b; printf(“3^2 + 4^2 = %ld\n”, c); } $ ./a.out 61 Threads Implementation User-level threads aware of threads manages its own Kernel-level threads kernel Hybrid and user level – User threads map 62 User-Level Threads • Kernel thinks it is managing processes only privileges scheduling 63 USER Level Threads © Pearson Prentice Hall 64 Advantages of User-Level Threads • Better performance • Allows application-specific run-times 65 Disadvantages of User-Level Threads • Blocking system calls stops all threads in the process • Non-blocking I/O can be used (e.g., select()) • During a page fault the OS blocks the whole process… • Difficult to implement preemptive scheduling • Messy to program 66 Kernel Threads Thread management is § no thread § Windows is an § Recent Linux Figure 4.5 User-Level and Kernel-Level Threads P P User Threads Kernel P P User Kernel P User Threads Kernel (c) Combined(b) Pure kernel-level(a) Pure user-level User-level thread Kernel-level thread Process 67 Advantages of Kernel Threads § The kernel can simultaneously schedule multiple threads § Blocking system calls/page faults can be easily – If one thread calls a blocking system call or causes a page § Kernel routines can be multithreaded 68 Disadvantages of Kernel Threads • Thread creation and termination more expensive pools) – Requires blocking system calls – Requires kernel call • Same address space menti.com Q 4 Stacks 98 63 88 69 Hybrid Approaches § Thread creation is § Use kernel threads § Bulk of scheduling and Figure 4.5 User-Level and Kernel-Level Threads P P User Threads Kernel P P User Kernel P User Threads Kernel (c) Combined(b) Pure kernel-level(a) Pure user-level User-level thread Kernel-level thread Process 70 Multithreaded Web Server • If in a multithreaded web server the only way to read 72 Process and Thread Summary • Non-determinism è concurrency è multiple processes • Processes: creation, termination, switching & PCBs • Linux – supports process hierarchies • Threads: lightweight concurrency with shared data 73 When Do Threads Improve Efficiency? • Would an algorithm that performs several independent • Hint: consider uniprocessor and multiprocessor •
(long)x;}
(long)y;}
3);
4);
3^2 + 4^2 = 25
– The kernel is not
– Each process
threads
– Managed by the
– Combined Kernel
threads
onto kernel threads
• Threads implemented by software library
• Thread switching does not require kernel mode
• Process maintains a thread table and does thread
• PThread is user level
– Thread creation and termination are fast
– Thread switching is fast
– Thread synchronization (e.g., joining other threads) is fast
– All these operations do not require any kernel activity
– Each application can have its own scheduling algorithm
– Denies one of the core motivations for using threads
– Harder to use and understand, inelegant
– But other threads might be runnable
– Run-time can request a clock interrupt
• High-frequency clock interrupts not always available
• Individual threads may also need to use a clock interrupt
done by the kernel
management is done
by the application
example of this
approach
implementations
also support this.
Space
Library
Space
Space
Space
Space
Library
Space
from the same process on multiple processors
accommodated
fault, the kernel can schedule a runnable thread from the
same process
– Require kernel call
– But still much cheaper than process creation/termination
– One mitigation strategy is to recycle threads (thread
• Thread synchronization more expensive
• Thread switching is more expensive
– But still much cheaper than process switches
• No application-specific scheduler
done in the user space
and multiplex user-
level threads onto
some (or all) kernel
threads
synchronization of
threads is by the
application
Space
Library
Space
Space
Space
Space
Library
Space
from a file is the normal blocking read() system call, do
you think user-level threads or kernel-level threads are
being used? Why?
è better utilization
• Heavyweight management
– Child is clone of parent process
– Load new code to execute different process
• Posix threads case study
• Thread implementation – user vs kernel level
• Shared memory in threads requires synchronisation
• Thread switching can be controlled by programmer
CPU-intensive calculations concurrently (e.g., matrix
multiplication) be more efficient if it used threads, or if it
did not use threads?
Menti.com: Q5 Thread efficiency 98 63 88