I. Reader-writer problem: Readers come first
1. Problem description
There are two groups of concurrent processes: reader and writer, sharing the same file F. The requirements are as follows: (1) multiple readers are allowed to read at the same time; (2) no other reader or writer is allowed to work until the writer completes the write operation; (3) before the writer performs the write operation, all existing writers and readers should quit
2. Problem analysis
(1) Data (files and records) is shared by two groups of concurrent processes, Reader and Writer. (2) Two groups of concurrent processes, Reader and Writer. (3) Readers in the same group can read files at the same time without mutual exclusion
3. Reader Writer problem — Reader first
For readers first, the following conditions should be met: (1) if the new readers to: but other readers are reading, the new readers can also read; ② If there is a writer waiting, but there are other readers reading, the new readers can also read; ③ There are writers to write, new readers to wait.
If the new writer reaches: ① No readers, the new writer can write; ② There are readers, new writers waiting; ③ There are other writers, new writers waiting.
4. Semaphore and variable design
(1) Count variable for the read process: readcount=0. (2) Mutex semaphore for the counter operation: rc_mutex=1. (3) Write and read mutex semaphore: writeBlock =1
5. Reader-first algorithm design
int readcount=0; // Read process counter semaphore writeblock, rc_mutex; writeblock=1; rc_mutex=1;mainCobegin process reader_i()// I =1,2... N process writer_j() //j=1,2... m coend } processreader_i()
{
P(rc_mutex);
readcount++;
if(readcount==1) P(writeblock); V(rc_mutex); {read file}; P(rc_mutex); readcount--;if(readcount==0)
V(writeblock);
V(rc_mutex);
}
process writer_j( ) { P(writeblock); {write file}; V(writeblock); }Copy the code6. Problem analysis
(1) Readers first, when there are readers, the writer will be delayed (2) there will be writer hunger
Two, reader – writer problem: solve the hunger of writing process
1. Semaphore Settings
(1) Semaphore Rw: used to guarantee mutually exclusive access of reader and writer (2) Semaphore mutex: used to guarantee mutually exclusive access of count variable (3) Semaphore W: used to solve writer hunger problem
2. Algorithm design
int count=0; Semaphore mutex=1; semaphore mutex=1; Semaphore rw=1; Semaphore w=1; semaphore w=1; // Use void to solve writer hunger problemreader_i()
{
while(1){ P(w); // Request entry to P(mutex) when there is no read/write process; count++;if(count==1) P(rw); V(mutex); V(w); // Restore access to shared files {read files}; P(mutex); count--;if(count==0)
V(rw);
V(mutex);
}
}
Void writer()
{
while(1){ P(w); // Enter P(rw) when there is no write process; // Mutually exclusive access to shared files {write files}; / / write V (rw); // Release shared file V(w); // Restore access to shared files}}Copy the code3. The analysis
When have the reading process is to read file sharing, have write request access process, will be banned last in reading process request at this moment, wait to have in the Shared file to read, process has been completed immediately let write process into execution, only under the condition of no writing process execution allows reading process is run again, which solved the problem of the writing process of hunger.
Three, the application of the reader writer problem — the log bridge problem
Type 1. Only one vehicle can pass at a time
1. Problem description
In order to ensure traffic safety, as long as there are no cars on the bridge, the cars of one party are allowed to cross the bridge, and the cars of the other party are allowed to cross the bridge after all of them have passed, limiting the bridge deck to only one car at a time. Please use semaphore and PV operation to write the synchronization algorithm for the problem of vehicle crossing a single-log bridge.
2. Problem analysis
(1) There are two types of processes in the system: cars moving from east to west; Cars travelling from west to east (2) The relationship between processes ① Cars travelling in the same direction need to queue up; (2) The cars running in the direction need to be synchronized to ensure that they cannot meet on the single-plank bridge
3. Semaphore design
(1) mutexA: The amount of mutually exclusive credits used for cars travelling in the same direction (from east to west) to modify statistics, with an initial value of 1 (2) mutexB: The amount of mutually exclusive credits used for cars travelling in the same direction (from west to east) to modify statistics, with an initial value of 1 (3) Bridge: The semaphore of cars crossing a bridge in two directions. Two directions compete for the semaphore. The successful one is qualified to cross the bridge
4. Algorithm design
semaphore mutexA,mutexB,bridge,mutex;
mutexA=1,mutexB=1,bridge=1,mutex=1;
int countA=0,countB=0;
main() { cobegin process east-to-west-i(); / / I = 1, 2, 3... n process west-to-east-j(); / / j = 1, 2, 3... m coend } process east-to-west-i(); / / I = 1, 2, 3... n { p(mutexA); countA++;if(countA==1) p(bridge); v(mutexA); p(mutex); Cross the bridge. v(mutex); p(mutexA); countA--;if(countA==0) v(bridge); v(mutexA); } process west-to-east-j(); / / j = 1, 2, 3... . { { p(mutexB); countB++;if(countB==1) p(bridge); v(mutexB); p(mutex); Cross the bridge. v(mutex); p(mutexB); countB--;if(countB==0) v(bridge);
v(mutexB);
}
Copy the codeType 2. Multiple cars at a time
1. Problem description
In order to ensure traffic safety, as long as there is no car on the bridge, the car of one party is allowed to cross the bridge, and the car of the other party is allowed to cross the bridge after it is all over. The bridge surface can be more than one car at a time. Please use semaphore and PV operation to write the synchronization algorithm for the problem of vehicle crossing a single-log bridge.
2. Process design
There are two types of processes: east to west vehicle PA and west to east vehicle PB (1)PA process: each vehicle crosses the bridge from east to west in one activity as a process (2)PB process: each vehicle crosses the bridge from west to east in one activity as a process
3. Semaphore design
(1) Mutex1: used for modifying statistics between PA processes, initial value is 1 (2) Mutex2: used for modifying statistics between PB processes, initial value is 1 (3) Bridge: The semaphore of cars crossing the bridge in two directions. The two directions compete for this semaphore, and the successful one is qualified to cross the bridge. The initial value is 1 (4) number: the semaphore of cars crossing the bridge in the same direction, and the initial value is K
4. Algorithm design
Semaphore mutex1=1, mutex2=1,bridge=1, number=k; Int count1=0, count2=0; Cobegin process PA_i () / / I = 1, 2,... . { p(mutex1); Count1 ++; count1++; count1++; If (count1==1) p (bridge) // The first east to west car competing bridge mutex v(mutex1); P (number); // All cars in the same direction can cross the bridge at the same time. V(number); p(mutex1); Count1 -- coun1; count1 -- count1; If (count1==0) v(bridge) // The last car from east to west releases bridge's mutex v(mutex1); } the process PB_j () / / j = 1, 2,... . { p(mutex2); Count2 ++; count1 ++; If (count2==1) p (bridge) // The first east to west car competing bridge mutex v(mutex2); P (number); // All cars in the same direction can cross the bridge at the same time. V(number); p(mutex2); Count1 --; coun2--; count1 --; If (count2==0) v(bridge) // The last car from east to west releases bridge's mutex v(mutex2); } coendCopy the codeFour,
The difference between the reader writer problem and the producer consumer problem lies in: (1) the producer consumer problem can be executed alternately in the same period; The reader writer problem can only be executed by one party at the same time, and the other party can only start executing after all the readers (or writers) have been executed. (2) Caches shared by producers and consumers must be mutually exclusive; A file shared by a reader writer does not need to be mutually exclusive. A file shared only needs to be mutually exclusive if the restriction is that it cannot be read or written simultaneously. (3) wooden bridge problem is a little special, code is not reflected in sync, when a party all vehicles through the bridge deck, release the right to use the bridge, because of all the vehicle has passed, now this one has no vehicles, nature of the other party will get the right to use the bridge, and started across the bridge and so on, which reflects the synchronization.