OS Walkthrough 02 — Synchronization

PKU’s OS on Coursera: Week 05 ~ Week 06

Published in

Analytics Vidhya

5 min readFeb 1, 2023

Here we delve into synchronization approaches ranging from semaphore, monitor, & IPC (interprocess communication); methods ranging from atomic action/primitive, Dekker, Peterson, semaphore, mutex, Hoare monitor, Mesa monitor, spinlock, deadlock VS. starvation, & polling VS. busy waiting.

Last article:

OS Walkthrough 01— Multi-threading & CPU Scheduling

PKU’s OS on Coursera: Week 01 ~ Week 04

yc-kuo.medium.com

PKU’s OS on Coursera: Week 07 ~ Week 08

yc-kuo.medium.com

(1) Week 05: Process Synchronization-1

(2) Week 06: Process Synchronization-2

(1) Week 05: Process Synchronization-1

Exclusion VS. Synchronization
Critical section / critical region / critical resource
Mutual exclusion / mutual exclusion lock: to prevent race condition
Software solutions to exclusion & synchronization:

Dekker algorithm
Peterson algorithm
Semaphore
Mutex

5. Hardware solutions to exclusion & synchronization:

Enabling or disabling interrupts: privileged instructions [ CLI (Clear Global Interrupt Flag) & STI (Set Global Interrupt Flag) ]
Test and set lock (e.g., spinlock): temporarily blocking the buses.
Exchange

The process of vectored interrupting [3]

6. Semaphore & PV operations

initialization: initial value s
test (proberen): P operation, an atomic action
increment (verhogen): V operation, an atomic action

7. Binary semaphore: Semaphore with initial value s = 1

8. Mutex (Mutual exclusion): In some OSs, it’s a semaphore with an initial value s = 1, the same as a binary semaphore. In others, it’s a little different from the binary semaphore. Here, we view mutex the same as a binary semaphore.

9. Mutex VS. Semaphore

Mutex only allows one process/thread to enter the critical section. Mutex is used for exclusion. Only the process/thread entering the critical section can unlock.
Semaphore allows more than one processes/threads to enter the critical section. Semaphore can be used for synchronization and protecting variables. Not only the process/thread entering the critical section can unlock.

10. Producer-consumer problem (bounded-buffer problem)

A mutex can solve this problem

11. Readers-writers problem

Readers-writer lock

12. Spinlock: provided multiple CPUs

Can be achieved by hardware approach Test-and-set lock (TSL): an atomic action. Also can be implemented by software approach.
No overhead of context switching
More efficient than semaphore/mutex when the critical section is short (the waiting time is shorter).
May cause busy waiting when the critical section is long (the waiting time is longer).

13. Spinlock VS. Semaphore

Spinlock adopts test and set lock; semaphore adopts PV operations
Spinlock is more efficient than semaphore provided multiple CPUs
Spinlock is busy-waiting; semaphore put the processes that fail to enter the critical section in blocked/waiting state.

(2) Week 06: Process Synchronization-2

Monitor

Exclusion: guaranteed by the compiler.
Synchronization: realized by conditional variables, wait() & signal()/notify()/broadcast() operations.
Conditional variable: introduced for synchronization or process communication.
Operations on conditional variables: wait()/signal() OR wait/notify() OR wait/broadcast()

2. Hoare monitor: When P wakes Q up, execute Q first.

wait() & signal()
if(): check the condition 1 time only.
Overhead of context switching

3. Mesa monitor: When P wakes Q up, execute P first.

wait() & notify()
while(): check the condition at least 2 times.
No overhead of context switching

4. Interprocess communication (IPC)

Message passing: send() & receive(). Offered by OS using a buffer.
Shared memory: Mapping a chunk of memory in physical memory to the address spaces of process 1 & process 2. Handling Readers–writers problem.
Pipe: FIFO.
Semaphore

5. Synchronization in Linux

Atomic action / primitive
readers-writer lock
Semaphore / readers-writer semaphore / mutex
spinlock / readers-writer spinlock
Enabling or disabling interrupts [ CLI (Clear Interrupt) & STI (Set Interrupt) ]
Barrier

6. Deadlock VS. starvation

Deadlock: In concurrent computing, deadlock is any situation in which no member of some group of entities can proceed because each waits for another member. [6]
Starvation: A thread/process perpetually being postponed. A process may never be moved out of the waiting queue of semaphore. In the context of the process state diagram, a thread experiencing starvation could be in either the ready state or the blocked state, depending on the specific scenario.

Check the following article for more about deadlock:

OS Walkthrough 05 — Deadlock

PKU’s OS on Coursera: Week 12

yc-kuo.medium.com

7. Polling VS. busy waiting

If a program polls a device say every second, and does something else in the meantime if no data is available (including possibly just sleeping, leaving the CPU available for others), it’s polling. [6]
If a program continuously polls the device (or resource or whatever) without doing anything in between checks, it’s called a busy-wait. [7]