Producer and consumer issues

1. Mutex: the access of producer process and consumer process to buffer pool is mutually exclusive.

2. Synchronization relationship: only when the buffer pool is not full can producers put products into it; Consumers can only take products out of the buffer pool if it is not empty.

1. Use recording semaphore to solve the problem

semaphore mutex = 1, empty = n, full = 0; // Represents the mutually exclusive access to the buffer pool, the number of empty buffers and the number of full buffers in the buffer pool
cobegin
	producer() {
		while(true){
			Produce a product
			Swait(empty, mutex);
			Put a product into the buffer pool
			Ssignal(mutex, full);
		}
	}
	consumer() {
		while(true){
			Swait(full, mutex);
			Remove a product from the buffer pool
			Ssignal(mutex, empty);
			Consume a product
		}
	}
coend

2. Use AND semaphore to solve

semaphore mutex = 1, empty = n, full = 0;// Represents the mutually exclusive access to the buffer pool, the number of empty buffers and the number of full buffers in the buffer pool
cobegin
	producer() {
		while(true){
			Produce a product
			wait(empty);
			wait(mutex);
			Put a product into the buffer pool
			signal(mutex);
			signal(full);
		}
	}
	consumer() {
		while(true){
			wait(full);
			wait(mutex);
			Remove a product from the buffer pool
			signal(mutex);
			signal(empty);
			Consume a product
		}
	}
coend

the dining philosophers problem

There is only a mutually exclusive relationship and no synchronization relationship

Three solutions

1. At most 4 people are allowed to pick up the chopsticks on the left at the same time to ensure that at least one person can eat;
2. Only when the left and right chopsticks can be used, it is allowed to pick up chopsticks for dinner;
3. Odd numbered philosophers take the left chopsticks first and then the right chopsticks, and even numbered philosophers take the right chopsticks first and then the left chopsticks;

At most 4 people pick up the left chopsticks at the same time

semaphore chopstick = {1, 1, 1, 1, 1}; // Each chopstick corresponds to a mutually exclusive semaphore
semaphore count = 4; // At most 4 people pick up the left chopsticks at the same time
cobegin
	Pi() {
		while(true) {
			reflection
			wait(count); // No more than 4 people can pick up the left chopsticks at the same time
			wait(chopstick[i]); // Pick up the chopsticks on the left
			wait(chopstick[(i+1)%5]); //Pick up the chopsticks on the right
			having dinner
			signal(chopstick[(i+1)%5]);
			signal(chopstick[i);
			signal(count);
		}
	}
coend

Only when the left and right chopsticks can be used, it is allowed to pick up chopsticks for dinner

semaphore chopstick = {1, 1, 1, 1, 1}; // Each chopstick corresponds to a mutually exclusive semaphore
cobegin
	Pi() {
		while(true){
			reflection
			Swait(chopstick[i], chopstick[(i+1)%5]);
			having dinner
			Ssignal( chopstick[(i+1)%5], chopstick[i]);
		}
	}
coend

Odd numbered philosophers take the left chopsticks first and then the right chopsticks. Even numbered philosophers operate the opposite

semaphore chopstick = {1, 1, 1, 1, 1}; // Each chopstick corresponds to a mutually exclusive semaphore
cobegin
	Pi() {
		while(true){
			reflection
			if (i % 2 == 1) { // Odd scientists left first and then right
				wait(chopstick[i]);
				wait(chopstick[(i+1)%5];
				having dinner
				signal(chopstick[(i+1)%5];
				signal(chopstick[i]);
			}
			else {// Odd scientists first right then left
				wait(chopstick[(i+1)%5];
				wait(chopstick[i]);
				having dinner
				signal(chopstick[i]);
				signal(chopstick[(i+1)%5];
			}
		}
	}
coend

Readers and writers

Mutex: read / write mutex and writer mutex

We also need an rcount shaping variable to record the number of readers to maintain read-write mutual exclusion. In order to achieve mutually exclusive access, we also need a mutually exclusive semaphore.

Recording semaphore

int rcount = 0; // Record the number of readers
semaphore rmutex = 1, wmutex = 1; // Mutually exclusive access semaphore for rcount, mutually exclusive semaphore for writer
cobegin
	Reader() {
		while(true){
				wait(rmutex);
				if (rcount == 0) {
					wait(wmutex);
				}
				rcount += 1;
				signal(rmutex);
				Read operation
				wait(rmutex);
				rcount -= 1;
				if (rcount == 0) {
					signal(wmutex);
				}
				signal(rmutex);
		}
	}
	Writer() {
		while(true){
			wait(wmutex);
			Write operation
			signal(wmutex);
		}
	}
coend

Semaphore set resolution allows at most RN readers to read

Introduce a new semaphore l with an initial value of RN. When there are readers entering, reduce L by 1 through wait(L,1,1). When there are RN readers entering, l is 0 and cannot enter.

int RN;
semaphore L = RN, mx = 1; // L records the number of readers that can be entered, mx realizing mutual exclusion between reading and writing and between writers
cobegin
	Reader(){
		while(true){
			Swait(L, 1, 1); // L minus one
			Swait(mx, 1, 0); // Switch. When mx is 1, it can be read, and mx is 0, it means writing
			Read operation
			Ssignal(L,1);
		}
	}
	Writer(){
		while(true){
			Swait(mx, 1, 1; L, RN, 0); // Write operations can only be performed when there is no writer operation (mx=1) and no reader operation (L=RN)
			Write operation
			Ssignal(mx, 1);
		}
	}
coend

Three special semaphore sets

1. SWAT (S, D, d) has only one semaphore S, and only D resources are allowed to be applied each time. If the number of resources is less than D, it will not be allocated;
2. SWAT (s, 1,1), when s > 1, it is equivalent to a general recording semaphore; When S=1, it is equivalent to mutually exclusive semaphore;
3. SWAT (s, 1,0) is equivalent to a switch. When s > = 1, multiple processes (Readers) are allowed to enter the critical area; when S=0, any process is prevented from entering the critical area;