Lecture 17
18585 ワード
6.4 Lock Programming
S1: a := 1
S2: b := 2
S3: c := a + b
S4: d := 2 * a
S5: e := c + d
Make the 5 lines execute as fast as possible, but end up in same result as it would have executed sequenciallyS1: independent
S2: independent
S3: dependent on S1, S2
S4: dependent on S1
S5: dependent on S3, S4
So in semephore,
Semaphore L1(0), L2(0), L3(0), L4(0)
COBEGIN
/*S1*/ BEGIN a:=1; V(L1); END;
/*S2*/ BEGIN b:=2; V(L2); END;
/*S3*/ BEGIN P(L1); P(L2); c:=a+b; V(L3) END;
/*S4*/ BEGIN P(L1); d:=2*a; V(L4) END;
/*S5*/ BEGIN P(L3); P(L4); e:=c+d; END;
COEND
This will not work because as soon as S3 or S4 acquires L1, it will block the other statement from execution. - we can solve by calling V(L1) twice from S1
- we can solve by calling V(L1) after P(L1) from both S3 and S4 to let the other in.
Semaphore L1(0), L4(0)
COBEGIN
BEGIN a:=1; V(L1); d:=2*a; V(L4) END;
BEGIN b:=2; P(L1); c:=a+b; P(L4); e:=c+d; END;
COEND
6.4.2 Buffering
Tasks communicate unidirectionally through a queue
producer and consumer example
unbounded buffer
#define QueueSize /*infinite*/
int front=0, back=0;
int Elements[QueueSize]
uSemaphore full(0);
void Producer::main(){
for(;;){
// produce an item
// add it to the back of queue
full.V();
}
// produce a stopping value
full.V();
}
void Consumer::main(){
for(;;){
full.P();
// take an item from the front of the queue
if (stopping value?) break;
// process of consume the item
}
}
bounded bufferuSemaphore full(0), empty(QueueSize);
void Producer::main() {
for ( ;; ) {
// produce an item
empty.P();
// add element to buffer
full.V();
}
// produce a stopping value
full.V();
}
void Consumer::main() {
for ( ;; ) {
full.P();
// remove element from buffer
empty.V();
if ( stopping value ? ) break;
// process or consume the item
}
}
if you pick a right buffer size, then the buffer would be half full for the most of the time.This does not work with multiple producers and consumers
because producers may try to insert item into same buffer slot
and same thing can happen with consumers as well.
So you need mutual exclusion locks
bounded buffer with multiple producers/consumers capability
uSemaphore full(0), empty(QueueSize);
uOwnerLock pLock, cLock;
void Producer::main() {
for ( ;; ) {
// produce an item
empty.P();
pLock.acquire();
// add element to buffer
pLock.release();
full.V();
}
// produce a stopping value
full.V();
}
void Consumer::main() {
for ( ;; ) {
full.P();
cLock.acquire();
// remove element from buffer
cLock.release();
empty.V();
if ( stopping value ? ) break;
// process or consume the item
}
}
If the array/buffer specifically indicates that it is save to concurrently execute insert and remove, you can use two different locks for consumers and producers.But in other cases, you must assume the buffer is not insert/remove safe for concurrent execution.
Reference
この問題について(Lecture 17), 我々は、より多くの情報をここで見つけました https://velog.io/@wjddlstjd396/Lecture-17テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol