Transcript No Slide Title

Chapter 6 : Concurrent Processes
• What is Parallel Processing?
• Typical Multiprocessing
Configurations
• Process Synchronization
Software
• Process Cooperation
• Concurrent Programming
Single Processor Configurations
Multiple Process Synchronization
Multiple Processor Programming
Understanding
Operating Systems
1
What is Parallel Processing?
• Parallel processing (multiprocessing) -- 2+ processors
operate in unison.
– 2+ CPUs are executing instructions simultaneously.
– Each CPU can have a process in RUNNING state at same time.
• Processor Manager has to coordinate activity of each
processor and synchronize interaction among CPUs.
• Synchronization is key to system’s success because many
things can go wrong in a multiprocessing system.
Understanding
Operating Systems
2
Development of Parallel Processing
• Major forces behind the development of multiprocessing:
– Enhance throughput
– Increase computing power.
• Primary benefits:
– increased reliability due to availability of 1+ CPU
– faster processing because instructions can be processed in parallel,
two or more at a time.
• Major challenges:
– How to connect the processors into configurations
– How to orchestrate their interaction
Understanding
Operating Systems
3
Typical Multiprocessing Configurations
• Master/slave
• Loosely coupled
• Symmetric
Understanding
Operating Systems
4
Master/Slave Multiprocessing
Configuration
Slave
Main
Memory
Master
Processor
Slave
Understanding
Operating Systems
I/O
Devices
• Asymmetric configuration.
• Single-processor system with
additional “slave” processors.
• Each slave, all files, all devices,
and memory managed by
primary “master” processor.
• Master processor maintains
status of all processes in
system, performs storage
management activities,
schedules work for the other
processors, and executes all
control programs.
5
Pros & Cons of Master/Slaves
• The primary advantage is its simplicity.
• Reliability is no higher than for a single processor system
because if master processor fails, entire system fails.
• Can lead to poor use of resources because if a slave
processor becomes free while master is busy, slave must
wait until the master can assign more work to it.
• Increases number of interrupts because all slaves must
interrupt master every time they need OS intervention
(e.g., I/O requests).
Understanding
Operating Systems
6
Loosely Coupled Multiprocessing
Configuration
Processor 1
I/O
Devices
1
Main
Memory
Processor 2
I/O
Devices
2
Main
Memory
Processor 3
I/O
Devices
3
Main
Memory
Understanding
Operating Systems
• Features several complete computer
systems, each with own memory,
I/O devices, CPU, & OS.
• Each processor controls own
resources, maintains own
commands & I/O management
tables.
• Each processor can communicate
and cooperate with the others.
• Each processor must have “global”
tables indicating jobs each
processor has been allocated.
7
Loosely Coupled - 2
• To keep system well-balanced & ensure best use of
resources, job scheduling is based on several requirements
and policies.
– E.g., new jobs might be assigned to the processor with lightest load
or best combination of output devices available.
• System isn’t prone to catastrophic system failures because
even when a single processor fails, others can continue to
work independently from it.
• Can be difficult to detect when a processor has failed.
Understanding
Operating Systems
8
Symmetric Multiprocessing Configuration
• Processor scheduling is
decentralized.
• A single copy of OS & a
global table listing each
process and its status is
stored in a common area
of memory so every
processor has access to it.
• Each processor uses same
scheduling algorithm to
select which process it
will run next.
Processor 1
Main
Memory
Processor 2
I/O
Devices
Processor 3
9
Advantages of Symmetric over Loosely
Coupled Configurations
•
•
•
•
More reliable.
Uses resources effectively.
Can balance loads well.
Can degrade gracefully in the event of a failure.
• Most difficult to implement because processes must be
well synchronized to avoid problems of races and
deadlocks.
Understanding
Operating Systems
10
Process Synchronization Software
• Success of process synchronization hinges on capability
of OS to make a resource unavailable to other processes
while it’s being used by one of them.
– E.g., I/O devices, a location in storage, or a data file.
• The Missed Waiting Customer Problem
• In essence, used resource must be locked away from other
processes until it is released.
• Only when it is released is a waiting process allowed to
use resource. A mistake could leave a job waiting
indefinitely.
Understanding
Operating Systems
11
Synchronization Mechanisms
• Common element in all synchronization schemes is to
allow a process to finish work on a critical region of
program before other processes have access to it.
– Applicable both to multiprocessors and to 2+ processes in a singleprocessor (time-shared) processing system.
• Called a critical region because its execution must be
handled as a unit.
• Synchronization is sometimes implemented as a lock-andkey arrangement
– Before a process can work on a critical region, it’s required to get
the key
Understanding
Operating Systems
12
Lock-and-Key Synchronization
• Process first checks if key is available
• If it is available, process must pick it up and put it in lock
to make it unavailable to all other processes.
• For this scheme to work both actions must be performed in
a single machine cycle.
• Several locking mechanisms have been developed
including test-and-set, WAIT and SIGNAL, and
semaphores.
Understanding
Operating Systems
13
Test-And-Set (TS) Locking
• Test-and-set is a single indivisible machine instruction
(TS).
• In a single machine cycle it tests to see if key is available
and, if it is, sets it to “unavailable.”
• Actual key is a single bit in a storage location that can
contain a zero (if it’s free) or a one (if busy).
• Simple procedure to implement.
• Works well for a small number of processes.
Understanding
Operating Systems
14
Test-and-Set
Test and modify the content of a word atomically.
Understanding
Operating Systems
15
Mutual Exclusion with Test-and-Set
Understanding
Operating Systems
16
Problems with Test-And-Set
• When many processes are waiting to enter a critical region,
starvation could occur because processes gain access in an
arbitrary fashion.
– Unless a first-come first-served policy were set up, some processes
could be favored over others.
• Waiting processes remain in unproductive, resourceconsuming wait loops (busy waiting).
– Consumes valuable processor time.
– Relies on the competing processes to test key.
Understanding
Operating Systems
17
WAIT and SIGNAL Locking
• Modification of test-and-set.
• Adds 2 new operations, which are mutually exclusive and
become part of the process scheduler’s set of operations
– WAIT
– SIGNAL
• Operations WAIT and SIGNAL frees processes from “busy
waiting” dilemma and returns control to OS which can
then run other jobs while waiting processes are idle.
Understanding
Operating Systems
18
WAIT
• Activated when process encounters a busy condition code.
• Sets process control block (PCB) to the blocked state
• Links it to the queue of processes waiting to enter this
particular critical region.
• Process Scheduler then selects another process for
execution.
Understanding
Operating Systems
19
SIGNAL
• Activated when a process exits the critical region and the
condition code is set to “free.”
• Checks queue of processes waiting to enter this critical
region and selects one, setting it to the READY state.
• Process Scheduler selects this process for running.
Understanding
Operating Systems
20
Semaphores
• Semaphore -- nonnegative integer variable used as a flag.
• Signals if & when a resource is free & can be used by a
process.
• Most well-known semaphores are signaling devices used
by railroads to indicate if a section of track is clear.
• Dijkstra (1965) -- 2 operations to operate semaphore to
overcome the process synchronization problem.
– P stands for the Dutch word proberen (to test)
– V stands for verhogen (to increment)
Understanding
Operating Systems
21
Semaphore used by railroads indicates
whether the train can proceed
Understanding
Operating Systems
22
P (Test) and V (Increment)
• If we let s be a semaphore variable, then the V operation
on s is simply to increment s by 1.
V(s): s: = s + 1
– (fetch, increment, and store sequence)
• Operation P on s is to test value of s and, if it’s not zero, to
decrement it by one.
P(s): If s > 0 then s: = s – 1
– (test, fetch, decrement, and store sequence)
Understanding
Operating Systems
23
P (Test) and V (Increment)
•
P and V are executed by OS in response to calls issued by
any one process naming a semaphore as parameter.
• s = 0 implies busy critical region and the process calling on
the P operation must wait until s > 0
• Choice of which of the waiting jobs will be processed next
depends on the algorithm used by this portion of the
Process Scheduler
Understanding
Operating Systems
24
P and V operations on the binary semaphore s
Understanding
Operating Systems
25
MUTual EXclusion (Mutex)
• P and V operations on semaphore s enforce concept of
mutual exclusion, which is necessary to avoid having 2
operations attempt to execute at same time.
• Called mutex ( MUTual EXclusion)
P(mutex): if mutex > 0 then mutex: = mutex – 1
V(mutex): mutex: = mutex + 1
Understanding
Operating Systems
26
Semaphores (continued)
• Critical region ensures that parallel processes will modify
shared data only while in the critical region
• In parallel computations, mutual exclusion must be
explicitly stated and maintained
Understanding
Operating Systems
27
Process Cooperation
• Occasions when several processes work directly together
to complete a common task.
• Each case requires both mutual exclusion and
synchronization
• Two famous examples are problems of “producers and
consumers” and “readers and writers.”
• Each case requires both mutual exclusion and
synchronization, and they are implemented by using
semaphores.
Understanding
Operating Systems
28
Producers and Consumers
• Arises when one process produces some data that another
process consumes later
• Because buffer holds finite amount of data, synchronization
process must delay producer from generating more data
when buffer is full.
• Delay consumer from retrieving data when buffer is empty.
• This task can be implemented by 3 semaphores:
– Indicate number of full positions in buffer.
– Indicate number of empty positions in buffer.
– Mutex, will ensure mutual exclusion between processes
Understanding
Operating Systems
29
Producers and Consumers : One Process Produces
Some Data That Another Process Consumes Later.
Buffer
Producer
Consumer
Buffer
Producer
Consumer
Buffer
Producer
Consumer
The bounded buffer problem.
Understanding
Operating Systems
30
Producers and Consumers (continued)
• Definitions of producer and consumer processes:
•
•
•
•
•
•
•
Producer
produce data
P (empty)
P (mutex)
write data into buffer
V (mutex)
V (full)
Understanding
Operating Systems
Consumer
P (full)
P (mutex)
read data from buffer
V (mutex)
V (empty)
consume data
31
Producers and Consumers (continued)
• Definitions of variables and functions:
•
•
•
•
•
Given: Full, Empty, Mutex defined as semaphores
n: maximum number of positions in the buffer
V (x): x: = x + 1 (x is any variable defined as a semaphore)
P (x): if x > 0 then x: = x – 1
mutex = 1 means the process is allowed to enter the critical
region
Understanding
Operating Systems
32
Producers and Consumers (continued)
• Producers and Consumers Algorithm:
empty: = n
full: = 0
mutex: = 1
COBEGIN
repeat until no more data PRODUCER
repeat until buffer is empty CONSUMER
COEND
Understanding
Operating Systems
33
Readers and Writers
• Arises when two types of processes need to access shared
resource such as a file or database
• Example: An airline reservation system
– Implemented using two semaphores to ensure mutual exclusion
between readers and writers
– A resource can be given to all readers, provided that no writers are
processing (W2 = 0)
– A resource can be given to a writer, provided that no readers are
reading (R2 = 0) and no writers are writing (W2 = 0)
Understanding
Operating Systems
34
Reader & Writer Solutions
Using P and V Operations
• Two solutions using P and V operations:
1. Give priority to readers over writers so readers are kept
waiting only if a writer is actually modifying the data.
• However, this policy results in writer starvation if there is a
continuous stream of readers.
Understanding
Operating Systems
35
Reader & Writer Solutions
Using P and V Operations
2. Give priority to the writers.
• In this case, as soon as a writer arrives, any readers that are
already active are allowed to finish processing, but all
additional readers are put on hold until the writer is done.
• Obviously this policy results in reader starvation if a
continuous stream of writers is present
Understanding
Operating Systems
36
State of System Summarized By 4 Counters
• Number of readers who have requested a resource and
haven’t yet released it (R1=0);
• Number of readers who are using a resource and haven’t
yet released it (R2=0);
• Number of writers who have requested a resource and
haven’t yet released it (W1=0);
• Number of writers who are using a resource and haven’t
yet released it (W2=0).
• Implemented using 2 semaphores to ensure mutual
exclusion between readers and writers.
37
A Solution to Readers and Writers
reader() {
bufType *next, *here;
while (TRUE) {
// other computing...
P(mutex);
readCount++;
if (readCount == 1)
P(writeBlock);
V(mutex);
access(resource);
P(mutex);
readCount--;
if (readCount == 0)
V(writeBlock);
V(mutex);
}
Understanding
}
Operating Systems
writer() {
while (TRUE) {
//other computing
P(writeBlock);
access(resource);
V(writeBlock);
}
}
resourceType *resource;
int readCount = 0;
semaphore mutex = 1;
semaphore writeBlock = 1;
38
Concurrent Programming
• Concurrent processing system -- one job uses several
processors to execute sets of instructions in parallel.
– Requires a programming language and a computer system that can
support this type of construct.
• Increases computation speed.
• Increases complexity of programming language and
hardware (machinery & communication among machines).
• Reduces complexity of working with array operations
within loops, of performing matrix multiplication, of
conducting parallel searches in databases, and of sorting or
merging files.
Understanding
Operating Systems
39
Application of Concurrent Programming
• A = 3 * B * C + 4 / ( D + E ) ** ( F – G )
–
–
–
–
–
–
–
T1 = F - G
T2 = D + E
T3 = T2 ** T1
T4 = 4 / T3
T5 = 3 * B
T6 = T5 * C
A = T6 + T4
• T1, T2, T5 可以同時計算
• T3, T6 可以同時計算
Understanding
Operating Systems
COBEGIN
T1 = F – G
T2 = D + E
T5 = 3 * B
COEND
COBEGIN
T3 = T2 ** T1
T6 = T5 * C
COEND
T4 = 4 / T3
A = T6 + T4
40
Applications of Concurrent Programming
• Explicit parallelism: Requires that the programmer
explicitly state which instructions can be executed in
parallel
• Disadvantages:
–
–
–
–
Coding is time-consuming
Leads to missed opportunities for parallel processing
Leads to errors where parallel processing is mistakenly indicated
Programs are difficult to modify
Understanding
Operating Systems
41
Applications of Concurrent Programming
(continued)
• Implicit parallelism: Compiler automatically detects
which instructions can be performed in parallel
• Advantages:
– Solves the problems of explicit parallelism
– Dramatically reduces the complexity of
• Working with array operations within loops
• Performing matrix multiplication
• Conducting parallel searches in databases
• Sorting or merging file
Understanding
Operating Systems
42
Threads and Concurrent Programming
• Child processes (heavyweight processes)
– Require space in main memory where they reside during execution
– Require other resources such as data files or I/O devices
• Threads (lightweight processes)
– A smaller unit within a process, which can be scheduled and
executed
– Minimizes the overhead from swapping a process between main
memory and secondary storage
– Each active thread in a process has its own processor registers,
program counter, stack and status
– Shares data area and the resources allocated to its process
Understanding
Operating Systems
43
Thread States
Creation
Ready
Running
Finished
Waiting
Delayed
Blocked
Understanding
Operating Systems
A typical thread
changes states
as it moves
through the
system.
44
Thread States (continued)
• Operating system must be able to support
– Creating new threads
– Setting up a thread so it is ready to execute
– Delaying, or putting to sleep, threads for a specified amount of
time
– Blocking, or suspending, threads that are waiting for I/O to
complete
– Setting threads on a WAIT state until a specific event has occurred
– Scheduling threads for execution
– Synchronizing thread execution using semaphores, events, or
conditional variables
– Terminating a thread and releasing its resources
Understanding
Operating Systems
45
Thread States (continued)
• RUNNING to WAITING
– Wait for an event outside its control to occur
– E.g. a mouse click
• RUNNING to DELAYED
– Delay the processing of a thread by a specified amount of time
– Sleep()
• RUNNING to BLOCKED
– Waiting for I/O request to complete
Understanding
Operating Systems
46
Thread Control Block (TCB)
• Contains information about the current status and
characteristics of a thread
–
–
–
–
–
–
Thread ID: a unique identifier
Thread state
CPU information: program counter, register contents
Thread priority
Pointer to process that created this thread
Pointers to other threads that were created by this thread
Understanding
Operating Systems
47
Typical Thread Control Block (TCB)
Understanding
Operating Systems
48
Concurrent Programming Languages: Ada
• High-level concurrent programming language developed
by the U.S Department of Defense
• Initially intended for real-time and embedded systems
• Made available to the public in 1980, named after Augusta
Ada Byron
• Standardized by ANSI in 1983 and nicknamed Ada83
• Latest standard is ANSI/ISO/IEC-8652:1995 Ada 95
Understanding
Operating Systems
49
Concurrent Programming Languages: Java
• First software platform that promised to allow
programmers to code an application once, that would run
on any computer
• Developed at Sun Microsystems, Inc. (1995)
• Uses both a compiler and an interpreter
• Solves several issues:
– High cost of developing software applications for different
incompatible computer architectures
– Needs of distributed client-server environments
– Growth of the Internet and the World Wide Web
Understanding
Operating Systems
50
The Java Platform
Java platform is a software-only platform that runs on top
of other hardware-based platforms
A process used by the Java platform to shield a
Java program from a computer’s hardware
Understanding
Operating Systems
51
The Java Language Environment
• Looks and feels like C++
• Object oriented and fits well into distributed client-server
applications
• Memory allocation done at run time
• Compile-time and run-time checking
• Sophisticated synchronization capabilities
– Supports multithreading at the language level
Understanding
Operating Systems
52
Case Study: Process Management
in Linux
• Linux scheduler scans the list of processes in the READY
state and, using predefined criteria, chooses which process
to execute
• Three scheduling policies:
– Two for real-time processes and one for normal processes
• Each process has three attributes:
– Associated process type
– Fixed priority
– Variable priority
Understanding
Operating Systems
53
Case Study: Process Management in Linux
(continued)
• Combination of type and priority determines which
scheduling policy to use on the processes in the ready
queue
• For example, each process is one of three types
– SCHED_FIFO for nonpreemptible “real time” processes
– SCHED_RR for preemptible “real time” processes
– SCHED_OTHER for “normal” processes
Understanding
Operating Systems
54
Summary
• Multiprocessing occurs in single-processor systems
between interacting processes that obtain control of the one
CPU at different times
• Multiprocessing also occurs in systems with two or more
CPUs; synchronized by Processor Manager
• Each processor must communicate and cooperate with the
others
• Systems can be configured as master/slave, loosely
coupled, and symmetric
Understanding
Operating Systems
55
Summary (continued)
• Success of multiprocessing system depends on the ability
to synchronize the processors or processes and the
system’s other resources
• Mutual exclusion helps keep the processes with the
allocated resources from becoming deadlocked
• Mutual exclusion is maintained with a series of techniques
including test-and-set, WAIT and SIGNAL, and
semaphores (P, V, and mutex)
Understanding
Operating Systems
56
Terminology
•
•
•
•
•
•
•
•
•
•
•
•
Ada
busy waiting
COBEGIN
COEND
concurrent processing
concurrent programming
critical region
embedded computer systems
explicit parallelism
implicit parallelism
loosely coupled configuration
master/slave configuration
•
•
•
•
•
•
•
•
•
•
•
•
multiprocessing
mutex
P
parallel processing
process synchronization
producers and consumers
readers and writers
semaphore
symmetric configuration
test-and-set
V
WAIT and SIGNAL
57