Transcript Operating Systems: Concurrency and

Concurrency and Communication
Lecture 6, May 8, 2003
Mr. Greg Vogl
Operating Systems
Uganda Martyrs University
Introduction
 Sources
Ritchie ch. 11, 12, 13.4
Burgess 4.4-4.5, 6.4, 7.6
Solomon parts 3, 4
 Ways processes can interact
Processes compete for or share resources
Processes communicate with each other
May 8, 2003
Operating Systems: Lecture 6:
Concurrency and Communication
2
Contents
 Concurrent processes
mutexes/flags, semaphores, monitors, file locks
 Deadlock
avoidance, prevention, detection, recovery
 Interprocess communication
signals, messages, pipes, sockets, RPC, DDE, OLE
 Distributed systems
NFS, AFS, DCE, CORBA, DCE, DCOM
May 8, 2003
Operating Systems: Lecture 6:
Concurrency and Communication
3
Possible Process Relationships
 Fully independent processes
Users working on separate applications
 Independent but related processes
Separate programs updating the same database
 Concurrent programming applications
A set of co-operating processes
e.g. real-time systems handle asynchronous events
May 8, 2003
Operating Systems: Lecture 6:
Concurrency and Communication
4
Some Concurrent Processes
 Operating systems
 Real-time process control systems
 Online databases
 Network controllers
May 8, 2003
Operating Systems: Lecture 6:
Concurrency and Communication
5
Types of Resources
 Physical: processor, memory, I/O, disk storage
 Logical: system/app. data, in memory or on disk
 Shareable: useable by more than one at a time
Preemptable: can be “borrowed” without harm
 Consumable: gets used up (e.g. message)
 Reusable (e.g. physical; CPU and memory)
serial = one user at a time (mutual exclusion)
May 8, 2003
Operating Systems: Lecture 6:
Concurrency and Communication
6
Resource Conflict Problems
 e.g. Two processes both updating a database
 Copies in memory overwrite copy on disk
 User B’s changes overwrite user A’s changes
 Both users believe they hold the resource
 Only one can actually hold the resource, e.g.
Only one person can be booked per airplane seat
Order numbers should be unique
Only one variable can hold bank account balance
May 8, 2003
Operating Systems: Lecture 6:
Concurrency and Communication
7
Mutual Exclusion
 Race conditions lead to unpredictable results
Uncertain who will get to the resource first
 Sensitive operations require mutual exclusion
Occur within a critical region of a process
Allow only one process at a time; no overlap
 Goals of concurrent processes
Safe coexistence without data loss/corruption
Efficient and fair sharing of resources
May 8, 2003
Operating Systems: Lecture 6:
Concurrency and Communication
8
Flags
 Use a flag variable with a name like door_open
Before entering the toilet, check if the door is open
You should only enter if vacant (if the door is open)
Close the door after entering, open it after leaving
 But it doesn’t work on a computer!
Small time gap between checking, entering, closing
Possible that two can enter at about the same time
Need to test-and-set the variable in one instruction
May 8, 2003
Operating Systems: Lecture 6:
Concurrency and Communication
9
Semaphores
 s = 0, 1, … (non-negative integer variable)
If s=0 then the resource is free else it is occupied
 Wait(s)
if s > 0 then s=s-1 else wait on s
 Enter critical region
 Signal(s)
if any processes waiting then start one else s=s+1
May 8, 2003
Operating Systems: Lecture 6:
Concurrency and Communication
10
Advantages and Disadvantages
 Wait is like a single test-and-set instruction
indivisible, cannot be interrupted, therefore safe
 No “busy waiting”
waiting processes are blocked, others are scheduled
 Can be used to reserve more than one resource
Value of semaphore indicates the quantity available
 Low-level facility
Hard to program, easy to make mistakes/deadlocks
May 8, 2003
Operating Systems: Lecture 6:
Concurrency and Communication
11
Producer-Consumer Problem
 Producer puts data in a buffer array, N elements
Write only when buffer not full
 Consumer takes data from buffer
Read only when buffer not empty
 To implement, the algorithm uses 3 semaphores:
Free: mutual exclusion for buffer access, initially 1
Space: space available in buffer, initially N
Data: data available in buffer, initially 0
May 8, 2003
Operating Systems: Lecture 6:
Concurrency and Communication
12
Producer-Consumer Algorithm
Producer
 Produce item
 Wait(space)
Consumer
 Wait(data)


Wait(free)
– Get item from buffer
Wait(free)
Signal(free)
– Add item to buffer
Signal(free)

Signal(data)
May 8, 2003
Signal(space)
 Consume item

Operating Systems: Lecture 6:
Concurrency and Communication
13
Monitors
 Encapsulate data with its access procedures
E.g. provide put_item and get_item procedures
 Only one process can use a monitor procedure
If being used, put the process request in a queue
 Reduced chance of programming error
Compiler guarantees mutex, not application program
 Monitor must also provide synchronisation
E.g. put waiting processes in queue, no busy waiting
May 8, 2003
Operating Systems: Lecture 6:
Concurrency and Communication
14
Database locking
 File lock
Only necessary when whole file is being processed
Other processes cannot access any part of file
 Write lock
Only necessary when record is being written to
Other processes cannot read or write to the record
 Read lock
Other processes can read but not write to the record
May 8, 2003
Operating Systems: Lecture 6:
Concurrency and Communication
15
Deadlock
 Set of (usually) >1 forever blocked processes
Waiting for an event only caused by a member of set
E.g. each needs a resource that another holds
No process sees/controls the global situation
One or more processes must give up a resource
 Sometimes caused by program bug, not usually
 E.g. traffic jam: cars each waiting for the others
 E.g. two travelers book half of a two-way journey
May 8, 2003
Operating Systems: Lecture 6:
Concurrency and Communication
16
Conditions for deadlock
 Necessary conditions
Mutual exclusion: resource cannot be shared
Resource holding: hold some, request more
No preemption: resources not forcibly removed
 Necessary and sufficient condition
Circular wait: closed cycle of two or more
processes waiting on each other
– (or a simple program bug: one process waiting on itself)
May 8, 2003
Operating Systems: Lecture 6:
Concurrency and Communication
17
Deadlock prevention
 One shot allocation: wait for all resources
A process might hold resources long without using
A process might have a long wait to get everything
 Preemption by OS
E.g. OS saves copy of memory or registers
 To prevent circular wait: order resources
Might be difficult to order; inefficiencies
May 8, 2003
Operating Systems: Lecture 6:
Concurrency and Communication
18
Deadlock avoidance
 Dynamically predict possibility of deadlock
Time-consuming to look for >2 process deadlock
 Deny resource request if a deadlock could occur
An unsafe state will not necessarily lead to deadlock
 Banker’s algorithm: bank only loans resources if
it can meet projected needs of other customers
Process must first declare its max. resource needs
Seldom used because overhead would be large
May 8, 2003
Operating Systems: Lecture 6:
Concurrency and Communication
19
Deadlock detection
 Periodically look for deadlocks
At fixed intervals depending on deadlock probability
Whenever doing something that might cause it
Whenever a process is blocked from denied request
Whenever a process is blocked a long time
Whenever CPU utilisation is low (nothing else to do)
 May take less overhead to detect than prevent
 Can still consume too much processing time
May 8, 2003
Operating Systems: Lecture 6:
Concurrency and Communication
20
Deadlock recovery
 Abort processes or preempt resources
How many? All? (reboot the PC??) One at a time?
Which one(s)? Difficult ones to restart?
By whom? operator/user?
 Roll back to last checkpoint
E.g. database logging, enough info to undo
Avoid starvation: always roll back youngest process
May 8, 2003
Operating Systems: Lecture 6:
Concurrency and Communication
21
Signals
 Similar to interrupt; usually process is aborted
SIGFPE is floating point exception e.g. divide by 0
SIGSEGV is segment/memory address violation
Pressing Ctrl-C sends SIGINT (terminal-initiated)
SIGTERM is sent by a user process
 Some processes may want to trap signals
Ignore, apply handler function, or use default action
SIGKILL is only signal that cannot be trapped
May 8, 2003
Operating Systems: Lecture 6:
Concurrency and Communication
22
Shared memory
 Area of memory shared by multiple processes
OS and hardware must support shared segments
 Operations
Get a free segment (returns the segment address)
Destroy a shared segment (return to free list)
Attach to/detach from address space of a process
Set/get control parameters
May 8, 2003
Operating Systems: Lecture 6:
Concurrency and Communication
23
Messages
 Friendly processes communicate and cooperate
exchange messages rather than sharing memory
send(destination, msg); receive(source, msg buffer)
 Naming: direct or channel/pipe/mailbox/port?
 Synchronisation: send/receive blocking or not?
 Buffering:
queue(s)? in receiver’s or system’s memory?
 Message size: small or large? maximum?
May 8, 2003
Operating Systems: Lecture 6:
Concurrency and Communication
24
Pipes
 Output of a process directed to input of another
E.g. in DOS: dir | more; type myfile | sort
Pipes are a form of message passing
 Temporary intermediate file acts as a buffer
Managed as a FIFO queue; blocked if empty/full
Deleted when pipe closes
 Named pipes (FIFO) uses permanent file
UNIX mknod creates special file for shared space
May 8, 2003
Operating Systems: Lecture 6:
Concurrency and Communication
25
Sockets
 TCP/IP client-server connection of 2 processes
TCP stream (telephone) or UDP datagram (mailbox)
 TCP/IP servers provide services through ports
/etc/services lists port no.s of well-known services
/etc/protocols lists protocols like TCP and UDP
 Servers that receive many requests always run
Others are started by the Internet daemon if needed
Servers can be single- or multi-threaded
May 8, 2003
Operating Systems: Lecture 6:
Concurrency and Communication
26
Remote Procedure Call
 Process on one PC runs procedure on another
 Used for distributed processing
 Transparent to programmer (no net details)
 Works much like any other procedures
 Scaleable and maintainable
 Facilitates cross-platform interaction
 Implemented using named pipes or sockets
May 8, 2003
Operating Systems: Lecture 6:
Concurrency and Communication
27
Dynamic Data Exchange
 Conversation between Windows 3.x programs
DDE client requests data, DDE server replies
 Usually asynchronous: client waits for reply
If synchronous, handle error after timeout period
 Client must specify application, topic, and data
 WordAccess using Visual Basic macros
May 8, 2003
Operating Systems: Lecture 6:
Concurrency and Communication
28
Object Linking and Embedding
 Documents hold objects from different programs
e.g. text, tables, graphics
Embedded (the object is stored within the doc.)
Linked (only a reference is stored; keeps file small)
Helps to integrate OLE-compliant programs
 Common Object Model
 Drag and drop
 ActiveX controls e.g. buttons, text boxes, menus
May 8, 2003
Operating Systems: Lecture 6:
Concurrency and Communication
29