operating system project

Description

This case study provides students with an opportunity to apply theoretical knowledge of operating systems concepts in real-world scenarios, while also emphasizing teamwork, communication, and ethical considerations in the field of computer science. It has 2 partsand you must divide the work into 5 students with the work. i will upload all the chapters I have macOS so choose this existing system

Unformatted Attachment Preview

Chapter 7: Deadlocks
Operating System Concepts – 9th Edition
Silberschatz, Galvin and Gagne ©2013
Chapter 7: Deadlocks

System Model

Deadlock Characterization

Methods for Handling Deadlocks
 Deadlock Prevention

Deadlock Avoidance

Deadlock Detection

Recovery from Deadlock
Operating System Concepts – 9th Edition
7.2
Silberschatz, Galvin and Gagne ©2013
Chapter Objectives
 To develop a description of deadlocks, which prevent
sets of concurrent processes from completing their
tasks
 To present a number of different methods for
preventing or avoiding deadlocks in a computer
system
Operating System Concepts – 9th Edition
7.3
Silberschatz, Galvin and Gagne ©2013
System Model
 System consists of resources
 Resource types R1, R2, . . ., Rm
CPU cycles, memory space, I/O devices
 Each resource type Ri has Wi instances.
 Each process utilizes a resource as follows:

request

use

release
Operating System Concepts – 9th Edition
7.4
Silberschatz, Galvin and Gagne ©2013
Deadlock Characterization
Deadlock can arise if four conditions hold simultaneously.
 Mutual exclusion: only one process at a time can use a
resource
 Hold and wait: a process holding at least one resource is
waiting to acquire additional resources held by other
processes
 No preemption: a resource can be released only voluntarily
by the process holding it, after that process has completed
its task
 Circular wait: there exists a set {P0, P1, …, Pn} of waiting
processes such that P0 is waiting for a resource that is held
by P1, P1 is waiting for a resource that is held by P2, …, Pn–1
is waiting for a resource that is held by Pn, and Pn is waiting
for a resource that is held by P0.
Operating System Concepts – 9th Edition
7.5
Silberschatz, Galvin and Gagne ©2013
Deadlock with Mutex Locks
 Deadlocks can occur via system calls, locking, etc.
 See example box in text page 318 for mutex deadlock
Operating System Concepts – 9th Edition
7.6
Silberschatz, Galvin and Gagne ©2013
Resource-Allocation Graph
A set of vertices V and a set of edges E.
 V is partitioned into two types:

P = {P1, P2, …, Pn}, the set consisting of all the processes
in the system

R = {R1, R2, …, Rm}, the set consisting of all resource
types in the system
 request edge – directed edge Pi ® Rj
 assignment edge – directed edge Rj ® Pi
Operating System Concepts – 9th Edition
7.7
Silberschatz, Galvin and Gagne ©2013
Resource-Allocation Graph (Cont.)
 Process
 Resource Type with 4 instances
 Pi requests instance of Rj
Pi
Rj
 Pi is holding an instance of Rj
Pi
Rj
Operating System Concepts – 9th Edition
7.8
Silberschatz, Galvin and Gagne ©2013
Example of a Resource Allocation Graph
Operating System Concepts – 9th Edition
7.9
Silberschatz, Galvin and Gagne ©2013
Resource Allocation Graph With A Deadlock
Operating System Concepts – 9th Edition
7.10
Silberschatz, Galvin and Gagne ©2013
Graph With A Cycle But No Deadlock
Operating System Concepts – 9th Edition
7.11
Silberschatz, Galvin and Gagne ©2013
Basic Facts
 If graph contains no cycles Þ no deadlock
 If graph contains a cycle Þ

if only one instance per resource type, then deadlock

if several instances per resource type, possibility of
deadlock
Operating System Concepts – 9th Edition
7.12
Silberschatz, Galvin and Gagne ©2013
Methods for Handling Deadlocks
 Ensure that the system will never enter a deadlock
state:

Deadlock prevention

Deadlock avoidence
 Allow the system to enter a deadlock state and then
recover
 Ignore the problem and pretend that deadlocks never
occur in the system; used by most operating systems,
including UNIX
Operating System Concepts – 9th Edition
7.13
Silberschatz, Galvin and Gagne ©2013
Deadlock Prevention
Restrain the ways request can be made
 Mutual Exclusion – not required for sharable resources
(e.g., read-only files); must hold for non-sharable resources
 Hold and Wait – must guarantee that whenever a process
requests a resource, it does not hold any other resources

Require process to request and be allocated all its
resources before it begins execution, or allow process
to request resources only when the process has none
allocated to it.

Low resource utilization; starvation possible
Operating System Concepts – 9th Edition
7.14
Silberschatz, Galvin and Gagne ©2013
Deadlock Prevention (Cont.)
 No Preemption –

If a process that is holding some resources requests
another resource that cannot be immediately allocated to
it, then all resources currently being held are released

Preempted resources are added to the list of resources
for which the process is waiting

Process will be restarted only when it can regain its old
resources, as well as the new ones that it is requesting
 Circular Wait – impose a total ordering of all resource types,
and require that each process requests resources in an
increasing order of enumeration
Operating System Concepts – 9th Edition
7.15
Silberschatz, Galvin and Gagne ©2013
Deadlock Example
/* thread one runs in this function */
void *do_work_one(void *param)
{
pthread_mutex_lock(&first_mutex);
pthread_mutex_lock(&second_mutex);
/** * Do some work */
pthread_mutex_unlock(&second_mutex);
pthread_mutex_unlock(&first_mutex);
pthread_exit(0);
}
/* thread two runs in this function */
void *do_work_two(void *param)
{
pthread_mutex_lock(&second_mutex);
pthread_mutex_lock(&first_mutex);
/** * Do some work */
pthread_mutex_unlock(&first_mutex);
pthread_mutex_unlock(&second_mutex);
pthread_exit(0);
}
Operating System Concepts – 9th Edition
7.16
Silberschatz, Galvin and Gagne ©2013
Deadlock Example with Lock Ordering
void transaction(Account from, Account to, double amount)
{
mutex lock1, lock2;
lock1 = get_lock(from);
lock2 = get_lock(to);
acquire(lock1);
acquire(lock2);
withdraw(from, amount);
deposit(to, amount);
release(lock2);
release(lock1);
}
Transactions 1 and 2 execute concurrently. Transaction 1 transfers $25
from account A to account B, and Transaction 2 transfers $50 from account
B to account A
Operating System Concepts – 9th Edition
7.17
Silberschatz, Galvin and Gagne ©2013
Deadlock Avoidance
Requires that the system has some additional a priori information
available
 Simplest and most useful model requires that each process
declare the maximum number of resources of each type
that it may need
 The deadlock-avoidance algorithm dynamically examines
the resource-allocation state to ensure that there can never
be a circular-wait condition
 Resource-allocation state is defined by the number of
available and allocated resources, and the maximum
demands of the processes
Operating System Concepts – 9th Edition
7.18
Silberschatz, Galvin and Gagne ©2013
Safe State
 When a process requests an available resource, system must
decide if immediate allocation leaves the system in a safe state
 System is in safe state if there exists a sequence
of ALL the processes in the systems such that for each Pi, the
resources that Pi can still request can be satisfied by currently
available resources + resources held by all the Pj, with j < I  That is:  If Pi resource needs are not immediately available, then Pi can wait until all Pj have finished  When Pj is finished, Pi can obtain needed resources, execute, return allocated resources, and terminate  When Pi terminates, Pi +1 can obtain its needed resources, and so on Operating System Concepts – 9th Edition 7.19 Silberschatz, Galvin and Gagne ©2013 Basic Facts  If a system is in safe state Þ no deadlocks  If a system is in unsafe state Þ possibility of deadlock  Avoidance Þ ensure that a system will never enter an unsafe state. Operating System Concepts – 9th Edition 7.20 Silberschatz, Galvin and Gagne ©2013 Safe, Unsafe, Deadlock State Operating System Concepts – 9th Edition 7.21 Silberschatz, Galvin and Gagne ©2013 Avoidance Algorithms  Single instance of a resource type  Use a resource-allocation graph  Multiple instances of a resource type  Use the banker’s algorithm Operating System Concepts – 9th Edition 7.22 Silberschatz, Galvin and Gagne ©2013 Resource-Allocation Graph Scheme  Claim edge Pi ® Rj indicated that process Pj may request resource Rj; represented by a dashed line  Claim edge converts to request edge when a process requests a resource  Request edge converted to an assignment edge when the resource is allocated to the process  When a resource is released by a process, assignment edge reconverts to a claim edge  Resources must be claimed a priori in the system Operating System Concepts – 9th Edition 7.23 Silberschatz, Galvin and Gagne ©2013 Resource-Allocation Graph Operating System Concepts – 9th Edition 7.24 Silberschatz, Galvin and Gagne ©2013 Unsafe State In Resource-Allocation Graph Operating System Concepts – 9th Edition 7.25 Silberschatz, Galvin and Gagne ©2013 Resource-Allocation Graph Algorithm  Suppose that process Pi requests a resource Rj  The request can be granted only if converting the request edge to an assignment edge does not result in the formation of a cycle in the resource allocation graph Operating System Concepts – 9th Edition 7.26 Silberschatz, Galvin and Gagne ©2013 Banker’s Algorithm  Multiple instances  Each process must a priori claim maximum use  When a process requests a resource it may have to wait  When a process gets all its resources it must return them in a finite amount of time Operating System Concepts – 9th Edition 7.27 Silberschatz, Galvin and Gagne ©2013 Data Structures for the Banker’s Algorithm Let n = number of processes, and m = number of resources types.  Available: Vector of length m. If available [j] = k, there are k instances of resource type Rj available  Max: n x m matrix. If Max [i,j] = k, then process Pi may request at most k instances of resource type Rj  Allocation: n x m matrix. If Allocation[i,j] = k then Pi is currently allocated k instances of Rj  Need: n x m matrix. If Need[i,j] = k, then Pi may need k more instances of Rj to complete its task Need [i,j] = Max[i,j] – Allocation [i,j] Operating System Concepts – 9th Edition 7.28 Silberschatz, Galvin and Gagne ©2013 Safety Algorithm 1. Let Work and Finish be vectors of length m and n, respectively. Initialize: Work = Available Finish [i] = false for i = 0, 1, …, n- 1 2. Find an i such that both: (a) Finish [i] = false (b) Needi £ Work If no such i exists, go to step 4 3. Work = Work + Allocationi Finish[i] = true go to step 2 4. If Finish [i] == true for all i, then the system is in a safe state Operating System Concepts – 9th Edition 7.29 Silberschatz, Galvin and Gagne ©2013 Resource-Request Algorithm for Process Pi Requesti = request vector for process Pi. If Requesti [j] = k then process Pi wants k instances of resource type Rj 1. If Requesti £ Needi go to step 2. Otherwise, raise error condition, since process has exceeded its maximum claim 2. If Requesti £ Available, go to step 3. Otherwise Pi must wait, since resources are not available 3. Pretend to allocate requested resources to Pi by modifying the state as follows: Available = Available – Requesti; Allocationi = Allocationi + Requesti; Needi = Needi – Requesti;  If safe Þ the resources are allocated to Pi  If unsafe Þ Pi must wait, and the old resource-allocation state is restored Operating System Concepts – 9th Edition 7.30 Silberschatz, Galvin and Gagne ©2013 Example of Banker’s Algorithm  5 processes P0 through P4; 3 resource types: A (10 instances), B (5instances), and C (7 instances)  Snapshot at time T0: Allocation Max Available ABC ABC ABC P0 010 753 332 P1 200 322 P2 302 902 P3 211 222 P4 002 433 Operating System Concepts – 9th Edition 7.31 Silberschatz, Galvin and Gagne ©2013 Example (Cont.)  The content of the matrix Need is defined to be Max – Allocation Need ABC P0 743 P1 122 P2 600 P3 011 P4 431  The system is in a safe state since the sequence < P1, P3, P4, P2, P0>
satisfies safety criteria
Operating System Concepts – 9th Edition
7.32
Silberschatz, Galvin and Gagne ©2013
Example: P1 Request (1,0,2)
 Check that Request £ Available (that is, (1,0,2) £ (3,3,2) Þ true
Allocation
Need
Available
ABC
ABC
ABC
P0
010
743
230
P1
302
020
P2
302
600
P3
211
011
P4
002
431
 Executing safety algorithm shows that sequence < P1, P3, P4, P0, P2>
satisfies safety requirement
 Can request for (3,3,0) by P4 be granted?
 Can request for (0,2,0) by P0 be granted?
Operating System Concepts – 9th Edition
7.33
Silberschatz, Galvin and Gagne ©2013
Deadlock Detection
 Allow system to enter deadlock state
 Detection algorithm
 Recovery scheme
Operating System Concepts – 9th Edition
7.34
Silberschatz, Galvin and Gagne ©2013
Single Instance of Each Resource Type
 Maintain wait-for graph

Nodes are processes

Pi ® Pj if Pi is waiting for Pj
 Periodically invoke an algorithm that searches for a cycle in the
graph. If there is a cycle, there exists a deadlock
 An algorithm to detect a cycle in a graph requires an order of n2
operations, where n is the number of vertices in the graph
Operating System Concepts – 9th Edition
7.35
Silberschatz, Galvin and Gagne ©2013
Resource-Allocation Graph and Wait-for Graph
Resource-Allocation Graph
Operating System Concepts – 9th Edition
7.36
Corresponding wait-for graph
Silberschatz, Galvin and Gagne ©2013
Several Instances of a Resource Type
 Available: A vector of length m indicates the number of
available resources of each type
 Allocation: An n x m matrix defines the number of resources
of each type currently allocated to each process
 Request: An n x m matrix indicates the current request of
each process. If Request [i][j] = k, then process Pi is
requesting k more instances of resource type Rj.
Operating System Concepts – 9th Edition
7.37
Silberschatz, Galvin and Gagne ©2013
Detection Algorithm
1. Let Work and Finish be vectors of length m and n, respectively
Initialize:
(a) Work = Available
(b) For i = 1,2, …, n, if Allocationi ¹ 0, then
Finish[i] = false; otherwise, Finish[i] = true
2. Find an index i such that both:
(a) Finish[i] == false
(b) Requesti £ Work
If no such i exists, go to step 4
Operating System Concepts – 9th Edition
7.38
Silberschatz, Galvin and Gagne ©2013
Detection Algorithm (Cont.)
3. Work = Work + Allocationi
Finish[i] = true
go to step 2
4. If Finish[i] == false, for some i, 1 £ i £ n, then the system is in
deadlock state. Moreover, if Finish[i] == false, then Pi is
deadlocked
Algorithm requires an order of O(m x n2) operations to detect
whether the system is in deadlocked state
Operating System Concepts – 9th Edition
7.39
Silberschatz, Galvin and Gagne ©2013
Example of Detection Algorithm
 Five processes P0 through P4; three resource types
A (7 instances), B (2 instances), and C (6 instances)
 Snapshot at time T0:
Allocation
Request
Available
ABC
ABC
ABC
P0
010
000
000
P1
200
202
P2
303
000
P3
211
100
P4
002
002
 Sequence will result in Finish[i] = true for all i
Operating System Concepts – 9th Edition
7.40
Silberschatz, Galvin and Gagne ©2013
Example (Cont.)
 P2 requests an additional instance of type C
Request
ABC
P0
000
P1
202
P2
001
P3
100
P4
002
 State of system?

Can reclaim resources held by process P0, but insufficient
resources to fulfill other processes; requests

Deadlock exists, consisting of processes P1, P2, P3, and P4
Operating System Concepts – 9th Edition
7.41
Silberschatz, Galvin and Gagne ©2013
Detection-Algorithm Usage
 When, and how often, to invoke depends on:

How often a deadlock is likely to occur?

How many processes will need to be rolled back?
4 one for each disjoint cycle
 If detection algorithm is invoked arbitrarily, there may be many
cycles in the resource graph and so we would not be able to tell
which of the many deadlocked processes “caused” the
deadlock.
Operating System Concepts – 9th Edition
7.42
Silberschatz, Galvin and Gagne ©2013
Recovery from Deadlock: Process Termination
 Abort all deadlocked processes
 Abort one process at a time until the deadlock cycle is eliminated
 In which order should we choose to abort?
1.
Priority of the process
2.
How long process has computed, and how much longer to
completion
3.
Resources the process has used
4.
Resources process needs to complete
5.
How many processes will need to be terminated
6.
Is process interactive or batch?
Operating System Concepts – 9th Edition
7.43
Silberschatz, Galvin and Gagne ©2013
Recovery from Deadlock: Resource Preemption
 Selecting a victim – minimize cost
 Rollback – return to some safe state, restart process for that
state
 Starvation – same process may always be picked as victim,
include number of rollback in cost factor
Operating System Concepts – 9th Edition
7.44
Silberschatz, Galvin and Gagne ©2013
End of Chapter 7
Operating System Concepts – 9th Edition
Silberschatz, Galvin and Gagne ©2013
Chapter 4: Multithreaded
Programming
Operating System Concepts – 9th Edition
Silberschatz, Galvin and Gagne ©2013
Chapter 4: Multithreaded Programming
!
Overview
!
Multicore Programming
!
Multithreading Models
!
Thread Libraries
!
Implicit Threading
!
Threading Issues
!
Operating System Examples
Operating System Concepts – 9th Edition
4.2
Silberschatz, Galvin and Gagne ©2013
Objectives
!
To introduce the notion of a thread—a fundamental unit of CPU utilization that forms the basis of
multithreaded computer systems
!
To discuss the APIs for the Pthreads, Windows, and Java thread libraries
!
To explore several strategies that provide implicit threading
!
To examine issues related to multithreaded programming
!
To cover operating system support for threads in Windows and Linux
Operating System Concepts – 9th Edition
4.3
Silberschatz, Galvin and Gagne ©2013
Motivation
!
Thread is a basic unit of CPU utilization, it consists a thread ID, a program counter, a register set, and a stack.
!
It shares with other threads belonging to the same process its code section, data section, and other operating
system resources such as open files and signals
!
Traditional process (heavy-weigh) process has a single thread of control.
!
If a process has Multiple threads of control, it can perform more than one task at a time
!
Most modern applications are multithreaded
!
Threads run within application
!
Multiple tasks with the application can be implemented by separate threads
!
Update display
!
Fetch data
!
Spell checking
!
Answer a network request
Operating System Concepts – 9th Edition
4.4
Silberschatz, Galvin and Gagne ©2013
Single and Multithreaded Processes
code
registers
data
files
code
data
files
stack
registers
registers
registers
stack
stack
stack
thread
thread
single-threaded process
Operating System Concepts – 9th Edition
multithreaded process
4.5
Silberschatz, Galvin and Gagne ©2013
Benefits
!
Responsiveness – may allow continued execution if part of process is blocked, especially important for user
interfaces
!
Resource Sharing – threads share resources of process, easier than shared memory or message passing
!
Economy – cheaper than process creation, thread switching lower overhead than context switching
!
Scalability – process can take advantage of multiprocessor architectures
Operating System Concepts – 9th Edition
4.6
Silberschatz, Galvin and Gagne ©2013
Multicore Programming
!
Single Chip contains multiple computing cores where each core appears as a separate processor
to the OS
!
Multithreaded programming provides a mechanism for more efficient use of multiple core and
provided concurrency.
!
!
System with a single computing core: concurrency mean execution of the threads will be
interleaved .
!
System with multiple cores: concurrency means that threads run in parallel.
Multicore or multiprocessor systems putting pressure on programmers, challenges include:
!
Dividing activities
!
Balance
!
Data splitting
!
Data dependency
!
Testing and debugging
!
Parallelism implies a system can perform more than one task simultaneously
!
Types of parallelism
!
Data parallelism – distributes subsets of the same data across multiple cores, same operation on
each
!
Task parallelism – distributing threads across cores, each thread performing unique operation
Operating System Concepts – 9th Edition
4.7
Silberschatz, Galvin and Gagne ©2013
Concurrency vs. Parallelism
!
Concurrent execution on single-core system:
single core
T1
T2
T3
T4
T1
T2
T3
T4
T1
…
time
!
Parallelism on a multi-core system:
core 1
T1
T3
T1
T3
T1
…
core 2
T2
T4
T2
T4
T2
…
time
Operating System Concepts – 9th Edition
4.8
Silberschatz, Galvin and Gagne ©2013
User Threads and Kernel Threads
!
User threads – management done by user-level threads library
!
Three primary thread libraries:
!
POSIX Pthreads
!
Win32 threads
!
Java threads
!
Kernel threads – Supported by the Kernel
!
Examples – virtually all general purpose operating systems, including:
!
Windows
!
Solaris
!
Linux
!
Tru64 UNIX
!
Mac OS X
Operating System Concepts – 9th Edition
4.9
Silberschatz, Galvin and Gagne ©2013
Multithreading Models
!
Many-to-One
!
One-to-One
!
Many-to-Many
Operating System Concepts – 9th Edition
4.10
Silberschatz, Galvin and Gagne ©2013
Many-to-One
!
Many user-level threads mapped to single kernel thread
!
One thread blocking causes all to block
!
Multiple threads may not run in parallel on muticore system
because only one may be in kernel at a time
!
Few systems currently use this model
user thread
!
Examples:
!
Solaris Green Threads
!
GNU Portable Threads
k
Operating System Concepts – 9th Edition
4.11
kernel thread
Silberschatz, Galvin and Gagne ©2013
One-to-One
!
Each user-level thread maps to kernel thread
!
Creating a user-level thread creates a kernel thread
!
More concurrency than many-to-one
!
Number of threads per process sometimes restricted due to overhead
!
Examples
!
Windows NT/XP/2000
!
Linux
!
Solaris 9 and later
user thread
k
Operating System Concepts – 9th Edition
k
k
k
4.12
kernel thread
Silberschatz, Galvin and Gagne ©2013
Many-to-Many Model
!
Allows many user level threads to be mapped to many
kernel threads
!
Allows the operating system to create a sufficient number
of kernel threads
!
Solaris prior to version 9
!
Windows NT/2000 with the ThreadFiber package
user thread
k
Operating System Concepts – 9th Edition
4.13
k
k
kernel thread
Silberschatz, Galvin and Gagne ©2013
Two-level Model
!
Similar to M:M, except that it allows a user thread to be bound to kernel thread
!
Examples
!
IRIX
!
HP-UX
!
Tru64 UNIX
!
Solaris 8 and earlier
user thread
k
Operating System Concepts – 9th Edition
4.14
k
k
k
kernel thread
Silberschatz, Galvin and Gagne ©2013
Thread Libraries
!
Thread library provides programmer with API for creating and managing threads
!
Two primary ways of implementing
!
Library entirely in user space
!
Kernel-level library supported by the OS
Operating System Concepts – 9th Edition
4.15
Silberschatz, Galvin and Gagne ©2013
Pthreads
!
May be provided either as user-level or kernel-level
!
A POSIX standard (IEEE 1003.1c) API for thread creation and synchronization
!
Specification, not implementation
!
API specifies behavior of the thread library, implementation is up to development of the library
!
Common in UNIX operating systems (Solaris, Linux, Mac OS X)
Operating System Concepts – 9th Edition
4.16
Silberschatz, Galvin and Gagne ©2013
Pthreads Example
Operating System Concepts – 9th Edition
4.17
Silberschatz, Galvin and Gagne ©2013
Pthreads Example (Cont.)
Operating System Concepts – 9th Edition
4.18
Silberschatz, Galvin and Gagne ©2013
Pthreads Code for Joining 10 Threads
Operating System Concepts – 9th Edition
4.19
Silberschatz, Galvin and Gagne ©2013
Win32 API Multithreaded C Program
Operating System Concepts – 9th Edition
4.20
Silberschatz, Galvin and Gagne ©2013
Win32 API Multithreaded C Program (Cont.)
Operating System Concepts – 9th Edition
4.21
Silberschatz, Galvin and Gagne ©2013
Java Threads
!
Java threads are managed by the JVM
!
Typically implemented using the threads model provided by underlying OS
!
Java threads may be created by:
!
Extending Thread class
!
Implementing the Runnable interface
Operating System Concepts – 9th Edition
4.22
Silberschatz, Galvin and Gagne ©2013
Java Multithreaded Program
Operating System Concepts – 9th Edition
4.23
Silberschatz, Galvin and Gagne ©2013
Java Multithreaded Program (Cont.)
Operating System Concepts – 9th Edition
4.24
Silberschatz, Galvin and Gagne ©2013
Thread Pools
!
Create a number of threads in a pool where they await work
!
Advantages:
!
Usually slightly faster to service a request with an existing thread than create a new thread
!
Allows the number of threads in the application(s) to be bound to the size of the pool
!
Separating task to be performed from mechanics of creating task allows different strategies for
running task
4
!
i.e.Tasks could be scheduled to run periodically
Windows API supports thread pools:
Operating System Concepts – 9th Edition
4.25
Silberschatz, Galvin and Gagne ©2013
Threading Issues
!
Semantics of fork() and exec() system calls
!
Signal handling
!
!
Synchronous and asynchronous
Thread cancellation of target thread
!
Asynchronous or deferred
!
Thread-local storage
!
Scheduler Activations
Operating System Concepts – 9th Edition
4.26
Silberschatz, Galvin and Gagne ©2013
Semantics of fork() and exec()
!
Does fork()duplicate only the calling thread or all threads?
!
!
Some UNIXes have two versions of fork
Exec() usually works as normal – replace the running process including all threads
Operating System Concepts – 9th Edition
4.27
Silberschatz, Galvin and Gagne ©2013
Signal Handling
!
Signals are used in UNIX systems to notify a process that a particular event has occurred.
!
A signal handler is used to process signals
!
!
1.
Signal is generated by particular event
2.
Signal is delivered to a process
3.
Signal is handled by one of two signal handlers:
1.
default
2.
user-defined
Every signal has default handler that kernel runs when handling signal
!
User-defined signal handler can override default
!
For single-threaded, signal delivered to process
Where should a signal be delivered for multi-threaded?
!
Deliver the signal to the thread to which the signal applies
!
Deliver the signal to every thread in the process
!
Deliver the signal to certain threads in the process
!
Assign a specific thread to receive all signals for the process
Operating System Concepts – 9th Edition
4.28
Silberschatz, Galvin and Gagne ©2013
Thread Cancellation
!
Terminating a thread before it has finished
!
Thread to be canceled is target thread
!
Two general approaches:
!
!
Asynchronous cancellation terminates the target thread immediately
!
Deferred cancellation allows the target thread to periodically check if it should be cancelled
Pthread code to create and cancel a thread:
Operating System Concepts – 9th Edition
4.29
Silberschatz, Galvin and Gagne ©2013
Scheduler Activations
!
Both M:M and Two-level models require communication to maintain the
appropriate number of kernel threads allocated to the application
!
Typically use an intermediate data structure between user and kernel
threads – lightweight process (LWP)
!
Appears to be a virtual processor on which process can schedule
user thread to run
!
Each LWP attached to kernel thread
!
How many LWPs to create?
!
Scheduler activations provide upcalls – a communication mechanism
from the kernel to the upcall handler in the thread library
!
This communication allows an application to maintain the correct
number kernel threads
Operating System Concepts – 9th Edition
4.30
Silberschatz, Galvin and Gagne ©2013
Operating System Examples
!
Windows XP Threads
!
Linux Thread
Operating System Concepts – 9th Edition
4.31
Silberschatz, Galvin and Gagne ©2013
Windows Threads
!
Windows implements the Windows API – primary API for Win 98, Win NT, Win 2000, Win XP, and Win 7
!
Implements the one-to-one mapping, kernel-level
!
Each thread contains
!
A thread id
!
Register set representing state of processor
!
Separate user and kernel stacks for when thread runs in user mode or kernel mode
!
Private data storage area used by run-time libraries and dynamic link libraries (DLLs)
!
The register set, stacks, and private storage area are known as the context of the thread
!
The primary data structures of a thread include:
!
ETHREAD (executive thread block) – includes pointer to process to which thread belongs and to
KTHREAD, in kernel space
!
KTHREAD (kernel thread block) – scheduling and synchronization info, kernel-mode stack, pointer
to TEB, in kernel space
!
TEB (thread environment block) – thread id, user-mode stack, thread-local storage, in user space
Operating System Concepts – 9th Edition
4.32
Silberschatz, Galvin and Gagne ©2013
Windows XP Threads Data Structures
ETHREAD
thread start
address
pointer to
parent process
•
•
•
KTHREAD
scheduling
and
synchronization
information
kernel
stack
TEB
thread identifier
•
•
•
user
stack
thread-local
storage
•
•
•
kernel space
Operating System Concepts – 9th Edition
user space
4.33
Silberschatz, Galvin and Gagne ©2013
Linux Threads
!
Linux refers to them as tasks rather than threads
!
Thread creation is done through clone() system call
!
clone() allows a child task to share the address space of the parent task (process)
!
!
Flags control behavior
flag
meaning
CLONE_FS
File-system information is shared.
CLONE_VM
The same memory space is shared.
CLONE_SIGHAND
Signal handlers are shared.
CLONE_FILES
The set of open files is shared.
struct task_struct points to process data structures (shared or unique)
Operating System Concepts – 9th Edition
4.34
Silberschatz, Galvin and Gagne ©2013
Chapter 3: Process Concept
Operating System Concepts – 9th Edition
Silberschatz, Galvin and Gagne ©2013
Chapter 3: Process Concept
!
Process Concept
!
Process Scheduling
!
Operations on Processes
!
Interprocess Communication
!
Examples of IPC Systems
!
Communication in Client-Server Systems
Operating System Concepts – 9th Edition
3.2
Silberschatz, Galvin and Gagne ©2013
Objectives
!
To introduce the notion of a process — a program in execution, which forms the basis of all
computation
!
To describe the various features of processes, including scheduling, creation and termination,
and communication
!
To explore interprocess communication using shared memory and mes- sage passing
!
To describe communication in client-server systems
Operating System Concepts – 9th Edition
3.3
Silberschatz, Galvin and Gagne ©2013
Process Concept
!
An operating system executes a variety of programs:
!
!
Batch system – jobs
Time-shared systems – user programs or tasks
!
Textbook uses the terms job and process almost interchangeably
Process – a program in execution; process execution must progress in sequential fashion
!
Multiple parts
!
!
The program code, also called text section
!
Current activity including program counter, processor registers
!
Stack containing temporary data
4
!
Function parameters, return addresses, local variables
!
Data section containing global variables
!
Heap containing memory dynamically allocated during run time
Program is passive entity stored on disk (executable file), process is active
!
Program becomes process when executable file loaded into memory
!
Execution of program started via GUI mouse clicks, command line entry of its name, etc
!
One program can be several processes
!
Consider multiple users executing the same program
Operating System Concepts – 9th Edition
3.4
Silberschatz, Galvin and Gagne ©2013
Process in Memory
Operating System Concepts – 9th Edition
3.5
Silberschatz, Galvin and Gagne ©2013
Process State
!
As a process executes, it changes state
!
new: The process is being created
!
running: Instructions are being executed
!
waiting: The process is waiting for some event to occur
!
ready: The process is waiting to be assigned to a processor
!
terminated: The process has finished execution
Operating System Concepts – 9th Edition
3.6
Silberschatz, Galvin and Gagne ©2013
Diagram of Process State
Operating System Concepts – 9th Edition
3.7
Silberschatz, Galvin and Gagne ©2013
Process Control Block (PCB)
Information associated with each process
(also called task control block)
!
Process state – running, waiting, etc
!
Program counter – location of instruction to next execute
!
CPU registers – contents of all process-centric registers
!
CPU scheduling information- priorities, scheduling queue
pointers
!
Memory-management information – memory allocated to
the process
!
Accounting information – CPU used, clock time elapsed
since start, time limits
!
I/O status information – I/O devices allocated to process, list
of open files
Operating System Concepts – 9th Edition
3.8
Silberschatz, Galvin and Gagne ©2013
CPU Switch From Process to Process
Operating System Concepts – 9th Edition
3.9
Silberschatz, Galvin and Gagne ©2013
Threads
!
So far, process has a single thread of execution
!
Consider having multiple program counters per process
!
M