Modern Operating Systems 笔记 - Interprocess Communication
race conditions
Two or more processes are reading or writing some shared data and the final result depends on who runs precisely when.
Critical Regions
mutual exclusion
Prohibit more than one process from reading and writing the shared data at the same time.
critical region
Also called critical section , the part of the program where the shared memory is accessed.
Conditions to a good solution
- No two processes may be simultaneously inside their critical regions
- No assumptions may be made about speeds or the number of CPUs
- No process running outside its critical region may block other processes
- No process should have to wait forever to enter its critical region
Mutual Exclusion with Busy Waiting
Disable Interrupts
Problems
- It's unwise to give user processes the power to turn off interrupts.
- It's convenient for the kernel itself to disable interrupts for a few instructions, when race conditions could occur.
Lock Variables
This would not take place without atom operations.
Strict Alternation
//Process 1
while(TRUE){
while (turn != 0);
critical_region();
turn = 1;
noncritical_region();
}
//Process 2
while(TRUE){
while(turn != 1);
critical_region();
turn = 0;
noncritical_regino();
}
Problem: neither of them could run twice in a row, which violates condition 3.
Continuously testing a variable until some value apperas is called busy waiting , a lock that uses busy waiting is called a spin lock .
Peterson's Solution
Busy waiting lock variables.
#define FALSE 0
#define TRUE 1
#define N 2
int turn;
int interested[N];
void enter_region(int process)
{
int other = 1 - process;
interested[process] = TRUE;
turn = process;
while (turn == process && interested[other] == TRUE);
}
void leave_region(int process)
{
interested[process] = FALSE;
}
TSL Instruction
TSL RX, LOCK
Test and lock lock instruction reads the content of the memory word lock
into register RX
and then stores a nonzero value at the memory address lock
.
It's guaranteed by the hardware that the read and set operations are indivisible.
enter_region:
TSL REGISTER, LOCK
JNE REGISTER, #0, enter_region
RET 'return
leave_region:
MOVE LOCK, #0
RET
An alternative instruction to TSL
is XCHG
. The implementations are similiar.
Sleep and Wakeup
Problems in busy waiting:
- wasting CPU time
- process with higer priority will keep busy waiting while lower priority process never run
The Product-Consumer Problem
Producer loop:
if count == N:
sleep
else:
produce one
if count == 1:
wakeup consumer
Consumer loop:
if count == 0:
sleep
else:
consume one
if count == N-1
wakeup producer
Since count
is unconstrained, race condition could occur. When consumer is about to sleep, wakeup signal from producer is lost, causing both of them sleeping.
Semaphores
Semaphores are used to buffer signals, keep them from losing. Value 0 indicating that no wakeups were saved; positive value if some wakeups were pending.
down
(Proberen, try in Dutch) operation: checking the value and cosume one or sleep to wait one.
up
(Verhogen, raise in Dutch) operation: produce one, if someone's waiting, wake him.
Mutexes
mutex
A kind of semaphore, a variable that can be in 1 of 2 states: unlocked or locked, used when the semaphore's ability to count is not needed.
Monitors
When several mutexes are refered to, deadlock could occur by a subtle error. Monitors are provided by some programming languages to manage a group of mutual exclusive threads.
Only one of the threads in this group would run in a certain time. It's up to the compiler to arrange mutexes to accomplish the monitor.
Message Passing
message passing is used for information exchange between machines. This method of interprocess communication uses 2 primitives, send
and receive
.
Approaches:
-
mailbox
A mailbox is a place to buffer a certian number of messages.
-
rendezvous
No buffering, either of each primitive is blocked until the other occurs.
Barriers
With multiple processes, a barrier can be placed at the end of each phase. When a process reaches the barrier, it's blocked until all processes have reached the barrier.
本文采用 知识共享署名 4.0 国际许可协议(CC-BY 4.0)进行许可,转载注明来源即可: https://harttle.land/2013/11/25/modern-os-ipc.html。如有疏漏、谬误、侵权请通过评论或 邮件 指出。