Process Synchronization

Definition

Every process is sequential, but in a multiprogramming system, multiple processes compete for the processor and take turns occupying it.
Suppose two processes A and B execute the following operation sequences when running sequentially on their own:
Process A: a1, a2, a3, …, am
Process B: b1, b2, b3, …, bm
In a multiprogramming system, the processor may execute sequences such as
a1, b1, a2, b2, a3, b3 …
a1, a2, b1, a3, b2, b3 …

Concurrency of processes: if one process can start working before another has finished, these processes are said to be executable at the same time. In other words, they exhibit concurrency, and processes that can execute simultaneously are called concurrent processes.

• If the execution of one process neither affects the result of another process nor depends on its progress, i.e., they are independent of each other, these processes are said to be unrelated.
• If the execution of one process depends on the progress of other processes, or may affect their results, these processes are said to be interacting.
  • For interacting concurrent processes, concurrency breaks “closure” and “reproducibility”.

Mutual exclusion: multiple processes cannot use the same resource at the same time; while one process is using the resource, others must wait.
Process synchronization: the invocations of multiple processes have a temporal order; some processes must execute before others.
Interprocess communication: passing messages between multiple processes.

Intro

Because processes take turns modifying a shared variable, the result may be incorrect.

     Producer                          Consumer register1∶ = counter;             register2∶= counter; register1∶= register1+1;         register2∶ = register2-1; counter∶= register1;               counter∶ = register2;Assume: the current value of counter is 5.Whether the producer runs first or the consumer runs first, the result is 5.But if executed in the following order:         register1 ∶  = counter;               (register1 = 5)         register1 ∶  = register1 + 1;        (register1 =6)         register2 ∶  = counter;               (register2 = 5)         register2 ∶  = register2 - 1;         (register2=4)         counter  ∶  = register 1;             (counter=6)         counter  ∶  = register2;               (counter=4)The final value of counter is 4.The two results differ; the program has lost reproducibility.

When interacting concurrent processes execute, time-dependent errors (i.e., errors related to the scheduling order) may occur. The root cause is unrestricted access to shared resources (variables). For concurrent processes to execute correctly, access to shared variables must be restricted.

When processes compete for resources, the “mutual exclusion” problem must be solved first. Some resources must be used exclusively, such as printers, shared variables, tables, and files. Such resources are called critical resources, and the section of code that accesses a critical resource is called a critical section.
At any moment, only one process is allowed inside the critical section, thereby ensuring mutually exclusive access to the critical resource.

A cyclic process that accesses a critical resource can be described as follows:

repeat    entry section    critical section    exit section    remainder sectionuntil false<entry section>: checks whether the process may enter the critical section; if so, it must setthe in-use flag of the critical section to prevent later processes from entering.<critical section>: enters the critical section and uses the critical resource.<exit section>: when the process inside the critical section finishes and leaves, it resetsthe in-use flag in the "exit section", and is responsible for waking up one process in theblocking queue so it can enter the critical section.<remainder section>: other code

Blocking Queue: when a process tries to enter the critical section while it is occupied by another process, it must wait until the critical section becomes free. The queue of these waiting processes is called the blocking queue.
Deadlock: when two or more processes wait for each other to release resources so that none of them can proceed, this is called a deadlock.

Rules for using critical sections (mutual exclusion conditions)

1. Entry Allowed When Free: if the critical section is free, any requesting process should be allowed to enter immediately
2. Busy Then Wait: only one process is allowed in the critical section at a time
3. Limited Waiting: a process may stay in the critical section only for a finite time, and must not make other processes wait indefinitely outside
4. Yielding While Waiting: when a process cannot enter its critical section, it should release the processor immediately to avoid “busy waiting”

Semaphore

In 1965, E.W. Dijkstra of the Netherlands proposed the semaphore mechanism for process synchronization. It is now widely used wherever critical resources and critical sections need to be controlled.
A semaphore is a generalized lock; the semaphore is the count of signals. Unlocking is essentially sending a signal, and waiting for the lock to open is waiting for a signal.
lock: {0,1} semaphore: {-∞, … , -2, -1, 0, 1, 2, … , ∞}

Semaphores classified by function:

• Mutex semaphore: used to request or release the right to use a resource, usually initialized to 1.
• Resource semaphore: used to request or return resources; can be initialized to a positive integer greater than 1, representing the number of available units of a resource class.
  Classified by the evolution of semaphore mechanisms:
• Integer semaphore
• Record semaphore
• AND semaphore
• Semaphore set

In computer science, a semaphore is a variable or abstract data type used to control access to a common resource by multiple threads and avoid critical section problems in a concurrent system such as a multitasking operating system. Semaphores are a type of synchronization primitive. A trivial semaphore is a plain variable that is changed (for example, incremented or decremented, or toggled) depending on programmer-defined conditions.
The semaphore concept was invented by Dutch computer scientist Edsger Dijkstra in 1962 or 1963, when Dijkstra and his team were developing an operating system for the Electrologica X8. That system eventually became known as the THE multiprogramming system.

Two or more processes can cooperate by passing signals: a process can be forced to pause at a certain point (blocked waiting) until it receives a signal that lets it “move forward” (be woken up). The variable that plays the role of this signal light is called a semaphore.

Integer Semaphore

Defined as an integer that represents the number of free resources; it can only be accessed through two standard atomic operations, wait(s) and signal(s), also known as the P operation and V operation.

• Proberen (Dutch for “to test”): the wait(s) operation requests a resource (or the right to use it); a process executing the wait primitive may block itself;
  while S <= 0 do no-op; S--; // request a resource
• Verhogen (Dutch for “to increment”): the signal(s) operation releases a resource (or returns the right to use it); a process executing the signal primitive is responsible for waking up one blocked process.
  S++; // release a resource

Record Semaphore

The record semaphore mechanism is a process synchronization mechanism without busy waiting.
The OS kernel provides the wait and signal primitives as system calls, and applications use these system calls to achieve mutual exclusion between processes.
Engineering practice has proven that implementing mutual exclusion with semaphores is efficient, and this approach has been widely adopted.

Data structure of a record semaphore

#include <stdio.h>#include <stdlib.h>// Linked-list node representing a process in the waiting queuetypedef struct Node {    int pid;  // process ID    struct Node* next;  // pointer to the next node} Node;// Record semaphoretypedef struct {  // The initial value of value represents the number of a certain resource in the system.  // When the initial value > 1, it is a resource semaphore; when it = 1, it is a mutex semaphore.    int value;    Node* listOfProcess;  // the semaphore's blocking queue} RecordSemaphore;

“Busy waiting” is a phenomenon in process synchronization strategies, also known as “spin waiting”. When a process tries to enter a critical section occupied by another process, under a busy-waiting strategy it keeps checking in a loop whether the critical section is available, until it becomes available. In other words, the process stays active and consumes CPU time while waiting, instead of being suspended or moved to a waiting state.
Although busy waiting can provide good response time in some cases (e.g., when the expected wait is very short), it is generally considered inefficient because it wastes CPU cycles, especially when the wait is long.
In contrast, the record semaphore mechanism (blocking or sleeping semaphore mechanism) allows a process to sleep while waiting to enter a critical section, consuming no CPU time. When the critical section becomes available, the process is woken up. This approach is more efficient but may incur context-switch overhead, since the system must switch between running and waiting processes.

The P and V operations of a record semaphore, wait(s) and signal(s)

When s.value>=0, s.queue is empty;
when s.value<0, the absolute value of s.value is the number of processes waiting in s.queue.
When the initial value of s.value is 1, it is a mutex semaphore; when the initial value is greater than 1, it is a resource semaphore.
When only two concurrent processes share a critical resource, the mutex semaphore can only take the values 1, 0, and -1, where

• s.value=1 means no process is in the critical section
• s.value=0 means one process has entered the critical section
• s.value=-1 means one process is waiting to enter the critical section
  When s is used to achieve mutual exclusion among n processes, s.value ranges from 1 to -(n-1)

void wait(RecordSemaphore* s) {    s->value--;    if (s->value < 0) {        block(s->listOfProcess); // block the process and put it into the S.L queue    }}void singal(RecordSemaphore* s) {    s->value++;    if (s->value <= 0) { // if s->value=0, then value=-1 before s->value++, i.e., one process is waiting        wakeup(s->listOfProcess); // wake up one process in the blocking queue    }}

AND Semaphore

Consider a process that must acquire one or more shared resources before it can perform its task. For example:

   process A:                 process B:   wait(Dmutex);            wait(Emutex);   wait(Emutex);             wait(Dmutex);

In the end, processes A and B are stuck in a stalemate; without outside intervention, neither can escape. A and B have entered a deadlock.

The basic idea of the AND synchronization mechanism: allocate to a process, all at once, every resource it needs throughout its execution, and release them together after the process finishes. As long as even one resource cannot be allocated to the process, none of the other resources that could be allocated is given to it either.
Atomic operation: either all resources are allocated to the process, or none is.
An “AND” condition is added to the wait operation, hence the name AND synchronization, also called the simultaneous wait operation.

void Swait(S1, S2, …, Sn) { // P primitive  if (S1 ≥1 and S2 ≥ 1 … Sn ≥ 1) {// handling when resource requirements are satisfied    for (i = 1; i <= n; ++i){      // wait decrements s first, then checks whether it is < 0, and blocks if so. To avoid blocking, s must start >= 1      // Swait differs from wait: it only decrements after confirming the resource requirements can be met      Si=Si-1;    }  } else {    /* handling when some resources are insufficient;    the process enters the blocking queue of the first semaphore whose value is less than 1;    restore the PC register to the state at the start of Swait; */  }}void  Ssignal(S1, S2, …, Sn){  for (i = 1; i <= n; i++){    Si++; // release the occupied resources    for (each process P waiting in Si.L){      // check all processes in the blocking queue of each resource;      // take process P out of the blocking queue Si.queue;      P = Si.queue.getHead();      if(P passes the test in Swait){// note: unlike signal, process P must be re-tested before entering the ready queue        break;      }else{ // handling when the check fails (resources insufficient)        process P enters some blocking queue; // then continue the loop with the next process      }    }   } }

Semaphore Set

In the record semaphore mechanism, wait(S) and signal(S) can only add 1 to or subtract 1 from the semaphore, meaning only one unit of a critical resource can be acquired or released at a time.
By using a semaphore set to control each allocation, multiple units of a resource can be allocated at once.

// Si—current amount of resource class i; ti—lower bound for allocating resource class i; di—requested amount of resource class ivoid Swait ( S1, t1, d1; ... ; Sn, tn, dn ){  if (S1 ≥ t1 and S2 ≥ t2 … Sn ≥ tn) {    for (i = 1; i <= n; i++){      Si=Si-di;    }  } else {    // suppose Sj < tj is found first; the process enters the Sj.L queue;    // the process is put into the blocking queue associated with Sj    // restore the PC register to the state at the start of Swait;    // start the process scheduler and schedule another process to run;  }}// si—current amount of resource class i; di—amount of resource class i to releasevoid Ssignal ( S1, d1; ... ; Sn, dn ){  for (i = 1; i <= n; i++){    Si=Si+di;  }  // move the processes in the queues related to Si into the ready queue}

The “semaphore set mechanism” can be used for resource allocation and release in various situations. Some special cases:

• Swait(S, d, d) requests d units of the resource each time; when fewer than d units remain, none is allocated
• Swait(S, 1, 1) is an ordinary record-type mutex semaphore (when S=1) or resource semaphore (when S>1)
• Swait(S, 1, 0) can serve as a controllable switch (when S is 1, multiple processes may enter the critical section; when S=0, no process may enter)

Applications of Semaphores

Using semaphores for mutual exclusion
To let multiple processes access a critical resource mutually exclusively, simply create a mutex semaphore mutex for the resource, set its initial value to 1, and place each process’s critical section CS between the wait(mutex) and signal(mutex) operations.
Using semaphores to describe precedence (cooperation) relations
Suppose we have two tasks A and B, where task B depends on the completion of task A. We can use a semaphore initialized to 0 to describe this precedence relation. The steps are:
After task A finishes, it performs a V operation (signal) on the semaphore, incrementing its value by 1.
Before task B starts, it performs a P operation (wait) on the semaphore. If the semaphore’s value is greater than 0, it decrements the value by 1 and continues. If the value equals 0, task B blocks until the value becomes greater than 0.

parbegin and parend are keywords in concurrent programming marking the beginning and end of parallel execution

Example: use AND semaphores to describe the following precedence graph

Var a,b,c,d,e,f,g: semaphore: 0,0,0,0,0,0,0;Parbegin       begin S1; Ssignal(a,b); end;       begin wait(a); S2; Ssignal(c,d); end;       begin wait(b); S3; signal(e); end;       begin wait(c); S4; signal(f); end;       begin wait(d); S5; signal(g); end;       begin Swait(e,f,g); S6; end;Parend;

Hardware Synchronization Mechanism

Solving the critical section problem with hardware instructions
For critical section management, treat the flag as a lock: “unlocked” means enter, “locked” means wait.
Initially the lock is open, and every process entering the critical section must test the lock.
The test and the lock operation must be consecutive (an atomic operation).

Although software methods can solve the problem of processes entering the critical section mutually exclusively, they are difficult to get right and have significant limitations, so they are rarely used now. Instead, many computers today provide special hardware instructions that allow testing and modifying the contents of a word, or swapping the contents of two words. These special instructions can be used to solve the critical section problem.

1. Disabling interrupts
2. Using the Test-and-Set instruction for mutual exclusion
3. Using the Swap instruction for mutual exclusion

Disable Interrupts

An interrupt is the process by which, during execution, any unusual or unexpected event requiring urgent handling occurs in the system, causing the CPU to temporarily suspend the currently running program and switch to the corresponding event handler; after handling completes, it returns to the interrupted point or schedules a new process.
Interrupt handling means the CPU responds to the interrupt, enters the interrupt handler, and the system starts processing the interrupt.
Interrupt response means the CPU, upon receiving an interrupt request, transfers to the corresponding event handler.
Enabling interrupts means the system can be interrupted during continuous execution to run interrupt service routines.
Disabling interrupts means turning off system interrupts; the system does not respond to other interrupts and does not allow its continuous execution to be broken.

Disabling interrupts
Disable interrupts before entering the lock test; re-enable them after completing the lock test and acquiring the lock.
While a process is in the critical section, the computer system does not respond to interrupts and no scheduling occurs.

Pros And Cons

• Disabling interrupts is one of the simplest ways to achieve mutual exclusion.

• Abusing the power to disable interrupts can have serious consequences;
• Disabling interrupts for too long hurts system efficiency and limits the processor’s ability to interleave program execution;
• The method also does not work on multi-CPU systems, because disabling interrupts on one processor does not prevent processes on other processors from executing the same critical section code.

extern bool are_interrupts_enabled();void atomic_operation(void (*operation)()) {    start_atomic_operation();    operation();    end_atomic_operation(are_interrupts_enabled());}void start_atomic_operation() {    // If interrupts are enabled, disable them    if (are_interrupts_enabled()) {        disable_interrupts();    }}void end_atomic_operation(bool were_interrupts_enabled) {    // If interrupts were enabled before the atomic operation began, re-enable them    if (were_interrupts_enabled) {        enable_interrupts();        return;    }    enable_interrupts();}

Test And Set Instruction for Mutual Exclusion

This is a method that achieves mutual exclusion with the help of the TS (Test-and-Set) hardware instruction, which many computers provide.

lock=false means the resource is free; *lock=TURE means the resource is in use.
When the resource is in use, TS returns true, so the condition of the while TS(&lock); statement stays true and the loop keeps waiting.

This code is an example of a simple spinlock, implemented with an atomic operation called Test-and-Set (TS). A spinlock is a low-level atomic synchronization primitive, usually used to protect short-lived critical sections.
Spinlocks can waste resources, because while waiting to acquire the lock, a thread does not release the CPU but keeps busy-waiting. Therefore, spinlocks are usually only used to protect very short critical sections. For longer critical sections, other synchronization mechanisms such as mutexes are typically used.

boolen TS(boolen *lock){    boolean old;    old = *lock;    *lock =TURE;    return old;}do{    …    while TS( &lock);    critical section;    lock :=FALSE;    remainder section;}while(TRUE);

Swap Instruction for Mutual Exclusion

This instruction is called the exchange instruction, also known as the XCHG instruction on Intel 80x86, and is used to swap the contents of two words.

Monitor

Although the semaphore mechanism is a convenient and effective process synchronization mechanism, every process that wants to access a critical resource must supply its own wait(S) and signal(S) synchronization operations. This scatters a large number of synchronization operations across processes, which not only complicates system management but can also cause system deadlock through misuse of synchronization operations. To solve these problems, a new process synchronization tool emerged — the monitor.

Monitors are a higher-level synchronization construct that simplifies process synchronization by providing a high-level abstraction for data access and synchronization. Monitors are implemented as programming language constructs, typically in object-oriented languages, and provide mutual exclusion, condition variables, and data encapsulation in a single construct.
Moniter-Ref

Classic Synchronization Problems

• Producer-Consumer Problem
• Dining Philosophers Problem
• Readers-Writers Problem

Producer-Consumer Problem

Producers and consumers are generalized concepts that can represent classes of processes with the same properties. Producer and consumer processes share a buffer pool of fixed size; one or more producers produce data and store it in the buffer pool; one or more consumers take data from the buffer pool.

Producers and consumers must enter the buffer mutually exclusively. That is, at any moment only one entity (a producer or a consumer) may access the buffer; a producer excludes consumers and all other producers.
A producer must not write data into a full buffer pool, and a consumer must not take data from an empty buffer pool, i.e., producers and consumers must synchronize.

Two classes of processes are involved:
producer processes and consumer processes
The following synchronization relations must be guaranteed:

1. Multiple processes access the shared buffer pool mutually exclusively: mutex semaphore mutex
2. Products must not be added to a full buffer pool: available empty-slot resource semaphore empty
3. Products must not be taken from an empty buffer pool: available full-slot resource semaphore full
   full + empty=N

The order of the wait operations in each process matters: check the resource count first, then check mutual exclusion; otherwise deadlock may occur.
For example: the producer first requests the mutex, enters, then requests an empty slot, finds none available, and must wait for the consumer to request a full slot, use it, and release it. But since the producer holds the mutex, the consumer cannot enter. The system falls into deadlock.

Dining Philosophers Problem

Five philosophers and five chopsticks; each philosopher cycles through thinking and eating. The eating routine is: pick up the left chopstick, then the right chopstick, eat, then put down the chopsticks.

1. Allow at most four philosophers to eat at the same time, ensuring that at least one philosopher can eat and will eventually release the two chopsticks he used, so that more philosophers can eat.
2. In the dining philosophers problem, each philosopher must acquire two critical resources (chopsticks) before eating. This is essentially the AND synchronization problem introduced earlier, so the AND semaphore mechanism gives the most concise solution and avoids deadlock.
3. Require odd-numbered philosophers to pick up their left chopstick first and then the right, while even-numbered philosophers do the opposite. Under this rule, philosophers 2 and 3 compete for chopstick 3, and philosophers 4 and 5 compete for chopstick 5. That is, three philosophers compete for odd-numbered chopsticks; whoever wins then competes for an even-numbered chopstick. Eventually one philosopher will obtain two chopsticks and eat.

Readers-Writers Problem

This problem establishes a general model for multiple processes accessing a shared data area, such as a database, a file, a memory region, or a set of registers. Some reader processes only read the data, and some writer processes only write the data.

For example, in a networked ticketing system, queries and updates are very frequent, so multiple processes will inevitably attempt to query or modify (read/write) the same record. Multiple processes reading the same record simultaneously is fine. But if one process is updating a record in the database, no other process may access (read or write) that record; otherwise the same seat might be sold multiple times.

Conditions for reader/writer processes

1. Multiple reader processes may read the data at the same time;
2. Multiple writer processes must not write the data at the same time; writes must be mutually exclusive;
3. If a writer process is writing, no reader process may read the data.

Sol
Solve the readers-writers problem with record semaphores
Solve the readers-writers problem with semaphore sets

Exercises

EX1
Three processes P1, P2, P3 cooperate to print a file. P1 reads file records from disk into buffer 1 in memory, one record per execution; P2 takes the content of buffer 1 and puts it into buffer 2; P3 prints the content of buffer 2, one record per execution. Each buffer is the size of one record.
Use P and V operations to guarantee the file is printed correctly.
Extension
Three processes A1, A2, A3 share two buffers B1 and B2. Buffer B1 can hold n products and buffer B2 can hold m products. Process A1 produces one product at a time and stores it in buffer B1. Process A2 produces one product at a time and stores it in buffer B2. Process A3 takes one product at a time from buffer B2 to consume. To prevent storing a product into a full buffer, taking a product from an empty buffer, or taking the same product twice, use PV operations to implement their mutual constraints.

---

EX2
A factory has a warehouse that can hold up to 8 machines. Every machine produced by the production department must be stored in the warehouse, and the sales department can take machines out of the warehouse to supply customers. Moving machines in or out of the warehouse requires a transport tool; there is only one set of transport tools, which can carry one machine at a time.
Design the production department and sales department processes.

---

EX3
There is a plate on the table that can hold only one fruit at a time. Dad puts apples on the plate, Mom puts oranges on the plate, the daughter eats only apples, and the son eats only oranges. Dad or Mom may put a fruit on the plate only when it is empty, and a child may take a fruit only when the plate contains the fruit they want. Treating Dad, Mom, the son, and the daughter as four processes, use PV operations to manage them so that these four processes execute concurrently and correctly.
Extension
Suppose the plate’s capacity becomes 2, and at any moment only one of Dad, Mom, the daughter, or the son may access the plate (to put or take).

Ref

Semaphore-wikipedia
多线程信号量 Semaphore 使用 - youxin - 博客园
Monitors in Process Synchronization - GeeksforGeeks