Transcript threads library

UNIX Process Creation

Every process, except process 0, is
created by the fork() system call
 fork()
allocates entry in process table and
assigns a unique PID to the child process
 Child gets a copy of the parent process image
Both child and parent are executing the same
code following fork()
 Need to invoke execve to load new binary file

 fork()
returns the PID of the child to the parent
process and returns 0 to the child process
1
UNIX System Processes


2
Process 0 is created at boot time and
becomes the “swapper” after forking
process 1 (the INIT process)
When a user logs in, process 1 creates a
process for that user
UNIX Process Image

User-level context
 Process
Text (ie: code: read-only)
 Process Data
 User Stack (calls/returns in user mode)
 Shared memory (for IPC)
 only
one physical copy exists but, with virtual
memory, it appears as it is in the process’s
address space

3
Register context
UNIX Process Image

System-level context
 Process
table entry
 the
actual entry concerning this process in the
Process Table maintained by OS
• Process state, UID, PID, priority, event awaiting, signals
sent, pointers to memory holding text, data...
U
(user) area
 additional
process info needed by the kernel
when executing in the context of this process
• effective UID, timers, limit fields, files in use ...
 Kernel
stack (calls/returns in kernel mode)
 Per Process Region Table (used by memory manager)
4
Process Characteristics



5
The two characteristics are treated
independently by some recent OS
The unit of dispatching is usually referred
to a thread or a lightweight process
The unit of resource ownership is usually
referred to as a process or task
Multithreading vs. Single threading





6
Multithreading: when the OS supports
multiple threads of execution within a
single process
Single threading: when the OS does not
recognize the concept of thread
MS-DOS support a single user process and
a single thread
UNIX supports multiple user processes but
only supports one thread per process
Solaris supports multiple threads
Threads

Has an execution state (running, ready, etc.)
 Context


is saved when not running
Has an execution stack and some perthread static storage for local variables
Has access to the memory address space
and resources of its process
 All
threads of a process share this
 When one thread alters a (non-private) memory
item, all other threads (of the process) sees that
 A file opened by one thread, is available to
others
7
Single Threaded and Multithreaded
Process Models
8
Thread Control Block contains a register image, thread priority and
thread state information
Benefits of Threads vs Processes



9
Takes less time to create a new thread
than a process
Less time to terminate a thread than a
process
Less time to switch between two threads
within the same process
Benefits of Threads

Client/Server paradigm
 Server
may need to handle several file
requests over a short period of time
 More efficient to create (and destroy) a thread
for each request

10
Multiple threads can execute
simultaneously on different processors
Application benefits of threads



11
Consider an application that consists of
several independent parts that do not need
to run in sequence
Each part can be implemented as a thread
Whenever one thread is blocked waiting for
an I/O, execution could possibly switch to
another thread of the same application
(instead of switching to another process)
Benefits of Threads


12
Since threads within the same process
share memory and files, they can
communicate with each other without
invoking the kernel
Therefore, it becomes necessary to
synchronize the activities of various
threads so that they do not obtain
inconsistent views of the data
Threads States


Three key states: running, ready, blocked
They have no suspend state because all
threads within the same process share the
same address space
 Indeed:
suspending (ie: swapping) a single
thread involves suspending all threads of the
same process

13
Termination of a process, terminates all
threads within the process
User-Level Threads (ULT)




14
The kernel is not aware
of the existence of
threads
All thread management
is done by the
application, using a
thread library
Thread switching does
not require kernel mode
privileges
Scheduling is application
specific
Threads library

Contains code for:
 Creating
and destroying threads
 Passing messages and data between threads
 Scheduling thread executions
 Saving and restoring thread contexts
15
Kernel Activity for ULTs




16
The kernel is not aware of thread activity
but it is still managing process activity
When a thread makes a system call, the
whole process will be blocked
For the thread library that thread is still in
the running state
So thread states are independent of
process states
Advantages and inconveniences of ULT

Advantages
Thread switching does
not involve the kernel:
no mode switching
 Scheduling can be
application specific:
choose the best
algorithm.
 ULTs can run on any
OS. Only needs a
thread library

17

Inconveniences
Most system calls are
blocking and the kernel
blocks processes. So
all threads within the
process will be blocked
 The kernel can only
assign processes to
processors. Two
threads within the
same process cannot
run simultaneously on
two processors

Kernel-Level Threads (KLT)





18

All thread management is
done by kernel
No thread library but an
API to the kernel thread
facility
Kernel maintains context
information for the process
and the threads
Switching between threads
requires the kernel
Scheduling occurs on a
thread basis, usually
Ex: Windows NT and OS/2
Advantages and inconveniences of KLT

Advantages
the kernel can
simultaneously schedule
many threads of the
same process on many
processors
 blocking is done on a
thread level
 kernel routines can be
multithreaded

19

Inconveniences
thread switching within
the same process
involves the kernel. We
have 2 mode switches
per thread switch
 this results in a
significant slow down

Combined ULT/KLT Approaches





20
Thread creation done
in the user space
Bulk of scheduling
and synchronization of
threads done in the
user space
The programmer may
adjust the number of
KLTs
May combine the best
of both approaches
Example: Solaris
Solaris




21
Process includes the user’s address space, stack,
and process control block
User-level threads (threads library)
 Invisible to the OS
 Form the interface for application parallelism
Kernel threads
 The unit that can be dispatched on a processor and
its structures are maintain by the kernel
Lightweight processes (LWP)
 Each LWP supports one or more ULTs and maps to
exactly one KLT
 Each LWP is visible to the application
22
Process 2 is equivalent to a pure ULT approach
Process 4 is equivalent to a pure KLT approach
We can specify a different degree of parallelism (process 3 and 5)
Solaris: versatility

We can use ULTs when logical parallelism
does not need to be supported by hardware
parallelism (we save mode switching)
 Ex:
Multiple windows but only one is active at
any one time

23
If threads may block then we can specify
two or more LWPs to avoid blocking the
whole application
Solaris: user-level thread execution


24
Transitions among these states is under the
exclusive control of the application
 A transition can occur only when a call is made to a
function of the thread library
It’s only when a ULT is in the active state that it is
attached to a LWP (so that it will run when the
kernel level thread runs)
 A thread may transfer to the sleeping state by
invoking a synchronization primitive (chap 5) and
later transfer to the runnable state when the event
waited for occurs
 A thread may force another thread to go to the stop
state...
Solaris: user-level thread states
(attached to a LWP)
25
Decomposition of user-level Active state



When a ULT is Active, it is associated to a
LWP and, thus, to a KLT
Transitions among the LWP states is under
the exclusive control of the kernel
A LWP can be in the following states:
 running:
when the KLT is executing
 blocked: because the KLT issued a blocking
system call (but the ULT remains bound to that
LWP and remains active)
 runnable: waiting to be dispatched to CPU
26
Solaris: Lightweight Process States
LWP states are independent of ULT states
(except for bound ULTs)
27
Operating System Control Structures

The OS maintains the following tables for
managing processes and resources:
 Memory
tables
 I/O tables
 File tables
 Process tables
28
Process images in virtual memory
29
Location of the Process Image

Each process image is in virtual memory
 May
not occupy a contiguous range of
addresses (depending on the memory
management scheme used)
 Both a private and shared memory address
space is used


30
Location if each process image is pointed
to by an entry in the Primary Process Table
For the OS to manage the process, at least
part of its image must be brounght into
main memory
Process Control Block
pointer
process
state
process number
program counter
registers
memory limits
list of open files
.
.
.
31
PCB
Process Identification

A few numeric identifiers may be used
 Unique
process identifier (always)
 Indexes,
directly or indirectly, into the primary
process table
 User
identifier
 The
user who is responsible for the job
 Identifier
process
32
of the parent process that created this
PCB
Processor State Information

Contents of processor registers
 User-visible
registers
 Control and status registers
 Stack pointers

Program status word (PSW)
 Contains
status information
 Example: the EFLAGS register on Pentium
machines
33
PCB
Process Control Information

Scheduling and state information
 Process
state ( i.e: running, ready, blocked...)
 Priority of the process
 Event for which the process is waiting (if
blocked)

Data structuring information
 May
hold pointers to other PCBs for process
queues, parent-child relationships and other
structures
34
Execution Modes

To protect PCBs, and other OS data, most
processors support at least 2 execution
modes:
 Privileged
mode (a.k.a. system mode, kernel
mode, supervisor mode, control mode )
 manipulating
control registers, primitive I/O
instructions, memory management...
 User

35
mode
Proper mode is set via a mode bit which
can only be set by an interrupt, a trap or
OS call
CPU Context Switch
process P0
operating system
process P1
interrupt or system call
executing
save state into PCB0
reload state into PCB1
idle
idle
executing
interrupt or system call
save state into PCB1
reload state into PCB0
36
executing
idle
Context Switching
Basic Steps






37
Save context of processor including
program counter and other registers
Update the PCB of the running process
with its new state and other associate info
Move PCB to appropriate queue - ready,
blocked
Select another process for execution
Update PCB of the selected process
Restore CPU context from that of the
selected process
Process Scheduling

Differential responsiveness
 Discriminate

between different classes of jobs
Fairness
 Give
equal and fair access to all processes of
the same class

Efficiency
 Maximize
throughput, minimize response time,
and accommodate as many users as possible
38
Scheduling Queues

OS maintains queues of processes
waiting for resources
 Short
term queue of processes in memory
ready to execute
 The
dispatcher decides who goes next
 Long
term queue of new jobs waiting to use
the system
 OS
must not admit too many processes on
short-term queue
 A queue
for each I/O device consisting of
processes that want to use that I/O device
39
Ready and I/O Device Queues
queue header
ready head
queue
tail
mag
tape
unit 0
mag
tape
unit 1
head
tail
disk
unit 0
head
tail
terminal
unit 0
head
tail
40
PCB7
PCB2
registers
registers
PCB3
head
tail
PCB5
PCB14
PCB6
Process Scheduling
Queueing Diagram
41
Schedulers

Short-term Scheduler
 Also,


Long-term Scheduler
Mid-term Scheduler
 Also,
42
referred to as dispatcher
referred to as the swapper
Short-term Scheduler
Dispatcher

Dispatcher selects from among ready
processes and allocate the CPU to one of
them
 It
selects the next process according to a
scheduling algorithm


43
It prevents a single process from
monopolizing CPU
CPU always executes instructions from the
dispatcher when switching from one
process to another
Long-term Scheduler

This scheduler controls the degree of
multiprogramming



It strives to select a good process mix of I/O
bound and CPU-bound processes
If the degree of multiprogramming is stable, the
average process arrival rate must be equal to the
average process departure rate

44
The number of processes in memory
Thus, long-term scheduler usually gets invoked when a
process leaves the system
The need for swapping



Even with virtual memory, keeping too
many processes in main memory may
deteriorate the system’s performance
The OS may need to suspend some
processes, ie: to swap them out to disk.
Two new states are added states:
 Blocked
Suspended: blocked processes which
have been swapped out to disk
 Ready Suspended: ready processes which
have been swapped out to disk
45