Process Synchronization

7.1 Why Process Synchronization?

7.1.1 The Basic Problem: n Processes, One Resource

Suppose $n$ processes are running, and all $n$ of them are trying to compete for the same resource. Only one process can access the resource at a time; every other process has to wait. It is quite possible for more than one process to be waiting — the waiters are not limited to one. Think of a printer shared by a lab full of students: many students may have queued their print jobs, but the printer prints one page at a time. Process synchronization is what we use to synchronize the access of resources by any number of processes, so that the competition is managed instead of chaotic.

Why bother at all? Because we always want the CPU to stay busy. Maximum utilization of the CPU, improving the efficiency of the system, is the constant goal. The first tool we have for that goal is scheduling, which we covered in the previous session: if scheduling is done properly, the CPU stays well used. Scheduling decides which process runs next; synchronization decides what the running processes are allowed to do at the same time. Scheduling alone is not enough — a well-scheduled system can still corrupt its own data if two processes collide on a shared variable. That is where this session begins.

7.1.2 Recap: Scheduling and the Optimal Time Quantum

We saw many scheduling algorithms, in this order: first-come-first-serve (FCFS), then shortest job first or shortest remaining time first (we can call it either name, depending on whether we use the non-preemptive or preemptive version of the algorithm), followed by priority scheduling — this is still a "shortest job" idea in spirit, but access to the CPU is decided by priority rather than length. The last algorithm is round robin, which is the combination of FCFS plus a time quantum.

In round robin, the process that comes is placed automatically in the ready queue. From the ready queue we take the process to the CPU for execution, and the execution takes place only for a particular time quantum — also called the time slice, whichever name you prefer. The time slice may be three milliseconds or four milliseconds. When the slice runs out, the CPU is taken away from the process and handed to the next one in the ready queue, which runs for its own slice.

The size of the time quantum matters a lot. If the time quantum increases, a single process itself will take more time, which makes the other processes wait for a long time; that should not happen. If the time quantum is very small — suppose we say the time quantum is only one millisecond — then a job cannot execute for more than one millisecond, so every time it is taken out of the CPU and the next process comes in. Many context switches take place, and the overhead involved in the context switching becomes more than the time spent executing a process. That is the reason the time quantum should always be optimal: large enough that one process does not hog the CPU, small enough that context switching overhead does not dominate.

A context switch is the work the operating system does to save one process's state (its registers, program counter, and so on) and load the next process's state. It is pure overhead — no useful instructions run during a switch. A one-millisecond quantum spent mostly switching means the CPU's time is going to the switch, not to the processes. This is the same trade-off the scheduler faces everywhere: sharing the CPU costs a little bit of the CPU itself.

7.1.3 Multiprogramming, Multiprocessing, and Concurrent Execution

We always have multiprogramming and multiprocessing. Multiprogramming means: how many programs are present in the memory. Multiprocessing means: how many processes are in execution. If we have to perform multiprogramming, multiprocessing, or multitasking — whatever it is — we need to see how to achieve it in a uniprocessor system or in a multiprocessor system, and that is exactly what synchronization is about: in what way can we synchronize a larger number of processes, and at the same time perform operations concurrently?

Concurrent execution (many tasks making progress at the same time, from the system's point of view) must not be confused with parallel execution (many tasks literally running at the same instant). The difference is decided by the hardware underneath:

In a uniprocessor system there is only one processor, so all the processes get interleaved: the first process starts, completes after a particular point of time, the second process starts and ends after its time period, then maybe the first process starts again — whichever process is free, or whichever comes according to the scheduling policy, comes for execution. It looks as if all processes are executing simultaneously, but they are not; a uniprocessor can execute only one process at a time. The time taken to switch is so fast that the illusion of simultaneity is convincing.

In a multiprocessor system, by contrast, the processes are overlapped. Why? Because we have more than one processor. A multiprocessor environment means a single chip with multiple cores, and each core can have many hardware threads; each thread is capable of executing a particular process. So processes are overlapped across the cores: when one is in execution, before it completes, the second will start and execute; similarly, before the second completes, the first may start again. But remember, these executions all happen on different processors — that is the difference. By overlapping we achieve concurrent execution, and that is the advantage of the multiprocessor system.

Picture both cases on a time axis, with the horizontal axis measured in milliseconds and one row per process:

• Uniprocessor (interleaved): process A runs, then process B runs, then process C, then back to A — each row is a sequence of non-overlapping blocks. At every single instant exactly one block is active. The rows never overlap because there is only one CPU to fill.
• Multiprocessor (overlapped): the blocks in the A, B, and C rows do overlap in time, because each row has its own processor (or hardware thread). Two processes genuinely execute in the same instant, on different cores.

The one-sentence takeaway from the picture: interleaving fakes simultaneity on one CPU; overlapping delivers real simultaneity on many. This distinction decides how hard synchronization is — on a single CPU a simple trick like disabling interrupts can protect shared data, while on multiple CPUs the same trick no longer works, as we will see in Section 7.5.

Real-world: every modern CPU chip is exactly this structure — multiple cores, each with multiple hardware threads — and the OS lets processes run concurrently across them.

But there is a disadvantage too. Interleaving and overlapping automatically improve efficiency, yet we cannot predict the results if we do not control things properly. If we are not controlling the processes, or not synchronizing them — synchronizing means controlling the time or the rate of arrival of processes and the usage of the system by $n$ processes — then the result may be unpredictable. Efficiency and correctness pull in opposite directions here: the more processes we overlap, the more chances they have to collide, and the more carefully their access must be synchronized.

7.1.4 The Echo Example: Shared Code with Unpredictable Results

Here is a concrete sample to make the problem visible. Consider a small procedure, an echo program, with two variables: in and out. We take the value for in from the keyboard and assign it to out, then display out. Two processes, P1 and P2, share the same code — both processes execute this same program.

read in;          /* take a character from the keyboard into in */
... some lines ...                                  /* four or five other instructions */
out = in;         /* copy the input character into out */
print out;        /* display the character that was copied */

This is the problem when two or more processes try to run the same code or share the same variable. It is not a matter of code alone — it may be a variable, a line, or a whole program. Whenever the same program or variable is going to be shared between processes, we need synchronization. Notice how the failure mode is timing: neither process "misbehaves", but the order in which their instructions interleave decides the result. This is the defining signature of a race condition, which we formalize in Section 7.3.

7.1.5 Where the Unpredictability Comes From

Why do we get unpredictable results? Three reasons were laid out.

Because of these three facts, the outcome of an unmanaged system is a function of timing: the same two processes, run twice, can produce two different results. Synchronization exists to remove timing from the outcome — the result should depend on the program logic, never on the accident of when each process happened to run.

7.1.6 Shareable and Non-shareable Resources

A resource can be shared by more than one process at a time, or it cannot. The class was asked for real-time examples. The discussion is worth keeping exactly, because it corrects a common mistake about memory.

The memory correction is the important one. It seems natural to call memory non-shareable because two processes cannot own the same bytes at the same time — but that is exactly what sharing means at the OS level: the same physical memory is given to one program, then released when the program ends and given to another. Sequential reuse is still sharing. A printer, by contrast, cannot be reused this way at an arbitrary moment — a printing job is a continuous, exclusive act, and a single physical device serves one system (or one queued job) at a time.

Where this shows up in the real world: a lab printer queue is a daily example of a non-shareable resource — two students cannot use the same printer at the same instant, and the spooler (the OS software that queues print jobs) is doing exactly the synchronization this lecture is about. Meanwhile, the memory of the same lab machine is silently shared by every running program: the browser's memory is reused by the editor after the browser closes, and the CPU cycles between all of them thousands of times per second.

Recap + bridge: Process synchronization manages the competition of $n$ processes for one resource so the CPU stays busy and results stay predictable. The danger is real — shared variables, like in and out in the echo program, can be corrupted by mere timing. Next, we look at the two kinds of processes that can collide — cooperating and independent — and the three problems their competition creates: deadlock, mutual exclusion, and starvation.

7.2 Cooperating Processes and the Problems of Concurrency

7.2.1 Independent Processes vs Cooperating Processes

Processes come in two kinds. Cooperating processes are the processes which are affected by other processes. If a process is going to change the value of a variable, and another process also uses the same variable — suppose variable A is used by both P1 and P2 — then these two are cooperating processes: whatever value is changed by either of the processes, both are affected. The word "cooperating" does not mean they deliberately work together; it means their behavior is coupled. Anything one of them writes to the shared variable is visible to the other, whether either of them wants that or not.

Independent processes are not affected by others. They have their own memory, their own variables, their own registers. When it comes to process synchronization, we always think about the cooperating processes. Independent processes can be scheduled in any order without any risk, because there is nothing shared between them — no variable, no buffer, no device — so their interleaving cannot change their results.

When to pick which framing: when you are asked whether synchronization is needed, first ask whether any resource is shared. If yes — even one variable — the processes are cooperating, and synchronization is required.

One subtle point: the processes will never know the existence of the other processes. Many processes will be there in the middle, each will not know about the others. The only thing they know is that they are going to share the resources and compete for them. This is what makes the problem hard: there is no friendly handshake, no mutual awareness — each process simply issues instructions, and the system must keep those instructions from colliding. The synchronization mechanism is the only thing that knows about the whole crowd.

7.2.2 Competing for Resources: Deadlock, Mutual Exclusion, and Starvation

When processes compete for a resource, there are chances for any of three outcomes: deadlock, mutual exclusion, and starvation. These are the three classic problems of concurrency, and they will return repeatedly through this session and the next.

Notice what makes this picture a deadlock rather than an ordinary wait: the waiting processes cannot advance by themselves. Each one's progress depends on P4 — and P4 is not waiting for any of them, so once P4 finishes, the system unblocks. The blockage is temporary. (A stricter deadlock, which we will meet with semaphores in Section 7.6 and study fully in a later lecture, is a circle: every waiting process is blocked on a resource held by another waiting process, so nobody can ever release anything.) The essential lesson now: competition can park processes indefinitely if the system does not regulate who gets the resource and when.

Mutual exclusion means that at that time only one process can use the resource, while the other processes have to wait. It is not itself a failure — it is a requirement for correctness: if two processes updated the same file simultaneously, the file would end up containing a mixture of both writes. What the lecture flags is that mutual exclusion, once enforced, is exactly what makes the waiters wait: they are excluded, one at a time, by the process currently inside.

Starvation means that if a particular process is using the resource for a long time, then all the other processes have to wait indefinitely. Starvation should not occur. The difference between deadlock and starvation is who is stuck: in deadlock, the waiting processes can never proceed because the resource-holder can never proceed (or is a different one of them); in starvation, the holder is proceeding — it is just never finishing, or the scheduler keeps choosing others, so the waiters never get a turn. A starving process is not blocked forever by a rule; it is indefinitely postponed by events.

So these cooperating or competing processes can cause problems — and the problems occur when the processes try to execute concurrently. For that, we have to do some synchronization.

7.2.3 The Definition of Process Synchronization

If many processes try to access a particular data item, the value that is going to be stored in that variable is not going to be consistent. Recall the echo program from Section 7.1: the final value of out changed depending on timing. Process synchronization exists precisely to make that value consistent — whichever process writes last, the reader should see one well-defined value, and every process should agree on what that value is. If we want to minimize this inconsistency, we go for process synchronization.

The phrase "minimizing the chance of inconsistency" is deliberate: synchronization does not make processes friends, and it does not make them faster. It makes their access to shared data orderly, so that the outcome no longer depends on the accident of interleaving. In the next section we build the precise vocabulary for doing this — the critical section, the producer–consumer problem, and the race condition — which are the vocabulary in which every solution in this session is expressed.

Recap + bridge: Cooperating processes share data and so affect each other, while independent processes cannot collide. Competition between cooperating processes creates the three problems of concurrency — deadlock, mutual exclusion, and starvation — and process synchronization is the answer that keeps shared data consistent. Next, we look at exactly where inconsistency is born: the critical section and the race condition.

7.3 The Critical Section, the Producer–Consumer Problem, and the Race Condition

7.3.1 The Critical Section

Before any solution, we need the terminology. A critical section is a part of the code — a code segment — where the shared variable or shared resources are accessed and executed. When a process executes that particular code segment, the execution takes place as an atomic action: atomic means either all of it will be completed fully, or nothing will be done. If P1 has taken the resource and is going to use this code segment, the code segment will be completed fully; only then will P1 release it. Otherwise no process will use it. So whichever process uses the critical section uses it fully, or not at all. At any point of time, only one process must be executing in the critical section.

Atomic (from the Greek for "not cuttable") is the master word of this session: an atomic operation is one the system cannot slice in half. It runs completely, or not at all — no other process's instructions can be interleaved into its middle. The critical section is atomic by design: a process enters it, executes it all, and only then lets anyone else in.

Remember this — it is very, very important. We need to define which part of the code is the critical section, and we should not imagine that the critical section is some common place that P1 and P2 both access. The critical section is a code which is going to be shared, but that does not mean it is one common place; each and every process has its own critical section.

The point of the correction is subtle but examinable. There is not one physical "critical section room" that processes enter. Each process carries its own copy of the same code; P1's critical section is P1's instructions, P2's critical section is P2's instructions. What the processes share is the data those instructions touch. Mutual exclusion then means: while P1 is inside its own critical section, P2 must not enter its own — because the two code segments would be operating on the same shared data at the same time. One rule, two copies of code, one shared resource.

7.3.2 The Producer–Consumer Problem

The classic example is the producer–consumer problem. The producer is the one which produces items, and it keeps on producing items until the buffer size is full. If the buffer size is 10, only 10 items can be put into that buffer. Each time an item is produced, it is placed in the buffer and the buffer position is incremented to the next position. That is the work of the producer.

The consumer consumes items. There is a variable, the counter, which tells us, based on its value, whether we have items in the buffer or not. If the counter is zero, we do not have any item, and the consumer does nothing. If some items are there — suppose there are two items, so the counter value is two — the consumer can consume an item from the buffer. Think of the buffer like a stack: if you take an item out, only one item remains, so you have to decrement the counter as well. This process continues until the counter becomes zero. The buffer size is always limited.

The professor's stack picture is worth keeping: items enter at one end, and the counter counts how many are currently stacked inside. Pushing an item onto the stack adds 1 to the counter; popping an item removes 1. The counter is the single source of truth about the buffer — which is exactly why it must never lie, and exactly where the race condition will attack.

7.3.3 Race Condition: The Counter Walkthrough

Now the trouble. Where does the race condition come from? Suppose we are going to execute counter++. We cannot directly use the variable. What we do: we put the counter value in a register, increment the register, and then assign the register value back to the counter. Similarly for counter--: we place the value in a register, decrement it, and assign it back.

Why the register? For cached execution — that is the main reason. Otherwise we would have to bring the value from the memory every time and operate on it, which takes time. The CPU works on registers, not directly on memory: loading a value from memory into a register, changing the register, and storing it back is far faster than repeated memory traffic. But this speed has a price — the update is no longer a single step. What looks like one operation, counter++, is really three:

The operations, written out:

$${\text{register}}_1\leftarrow \text{counter};{\text{register}}_1\leftarrow {\text{register}}_1+1;\text{counter}\leftarrow {\text{register}}_1$$

$${\text{register}}_2\leftarrow \text{counter};{\text{register}}_2\leftarrow {\text{register}}_2-1;\text{counter}\leftarrow {\text{register}}_2$$

where ${\text{register}}_1$ is the producer's working register, ${\text{register}}_2$ is the consumer's working register, and the arrow $\leftarrow$ means "is assigned". Each line is one machine instruction, and any two lines from the two processes can be interleaved in any order.

Now imagine the producer and the consumer execute these lines concurrently — at the same time. Take the initial counter value as 5. Follow the interleaving step by step:

This type of situation — executing in a way that leads to inconsistent data — is the race condition. Once the data become inconsistent, both processes cannot execute correctly. The name comes from the race between the two updates: whichever one finishes last wins the value, and the winner is decided by timing alone, never by logic. The race is conditioned on the interleaving — that is why the failure is called a race condition.

7.3.4 The Critical Section Problem: Entry, Exit, and Remainder

How do we prevent the race condition? By using the critical section — we solve the critical section problem. The code which was given earlier, the section that both processes run, is the critical section. Suppose we have $n$ number of processes, from $P_0$ to $P_{n-1}$. Each process will have a critical section — that is the key point. The producer has this code, the consumer has this code: the producer tries to increment the counter, and before it assigns the value to the counter, the consumer starts and does its work — that is where the race condition comes from. The section of code present in each and every process is called the critical section. The process in the critical section may be changing a variable, updating a table, or writing a file — any of these counts.

When a process is in the critical section, no other process should be in its critical section. That is the problem we have to solve: we have to design a protocol. Whenever a process wants to enter the critical section, it has to ask permission to enter — the entry section. After completing the critical section execution, it has to exit that section — the exit section. Then the remainder sections follow.

The anatomy of a process that uses a critical section:

entry section       ← ask permission to enter the critical section
critical section    ← use the shared variable / resource (atomic)
exit section        ← announce that the critical section is free
remainder section   ← do all the work that touches nothing shared

Picture the structure: if P1 and P2 are there, P1 will try to enter. In the entry section a condition is checked: if no other process is using the critical section, P1 is allowed to enter and use it. Later it has to exit it, then the remainder sections are carried out. When it exits, the next process can check the condition and enter. The remainder section is deliberately outside the synchronization machinery: it touches no shared data, so processes may run it simultaneously and in any order — the exclusion applies only to the critical section itself.

This is especially challenging for the preemptive type of kernels. In real-time programming it will be very, very challenging. A preemptive kernel lets the scheduler pull a process off the CPU at any moment — including in the middle of its critical section. If the preempted process was holding a shared resource, every other process that wants that resource is stuck until the kernel reschedules the holder. In real-time systems, where deadlines are absolute, such an interruption can miss a deadline entirely — which is why real-time kernels use the priority mechanisms we meet in Section 7.6.

7.3.5 The Three Requirements: Mutual Exclusion, Progress, Bounded Waiting

In order to solve the critical section problem — that is, to synchronize the processes — we have three requirements, and any solution must achieve all three. Any protocol for entry and exit sections is judged against these three; a solution that fails any of them is not a solution.

The three requirements guard three different failures. Mutual exclusion guards correctness — without it, the counter corrupts. Progress guards liveliness of the system — without it, everyone starves together. Bounded waiting guards fairness to the individual — without it, a specific process can be skipped forever while the system keeps moving, which is exactly the starvation of Section 7.2. Note the hidden assumption in requirement 3: processes run at some non-zero speed. The requirements do not assume a fixed speed, only that no process is frozen — a process must eventually finish its critical section so the bound can actually be honored.

If all three are satisfied by any approach, then we can say this particular approach is suitable for process synchronization. Many approaches exist — hardware-based approaches and software-based approaches — and all three requirements must be satisfied by whichever one we use. The rest of this session is a tour of such approaches: Peterson's solution (software), test-and-set and swap (hardware), and semaphores (the tool built on top).

Recap + bridge: The critical section is the code that touches shared data, executed atomically; the producer–consumer problem gives it a concrete shape (the counter and the buffer), and the race condition shows the exact interleaving that corrupts the counter. Solving the critical section problem means building entry/exit protocols that satisfy mutual exclusion, progress, and bounded waiting. Next we see the first such solution — Peterson's, written entirely in software.

7.4 Peterson's Solution: The Software Approach

7.4.1 The Two Shared Variables: Turn and Flag

Peterson's solution is a two-process solution — it is applicable only if we have two processes. It assumes two atomic instructions, load and store: if we start a load or a store instruction, it will not be interrupted in any way; either it will be completed fully, or it will not be done. In other words, reading a variable into a register and writing a variable back to memory are each indivisible. That is the only assumption the algorithm needs — everything else is built from ordinary software.

The semantics to remember, and the difference you should understand between turn and flag: if flag[0] is set true, process 0 is ready to enter the critical section; if flag[1] is set true, process 1 is ready. Whichever process is ready, the turn points to the other: if flag[0] = true, the turn will be 1 — the next turn is for P1 to enter; if flag[1] = true, the turn will be 0. The turn should be alternating; only then can one process execute in the critical section at a time and mutual exclusion be achieved.

Note on flag semantics (reconciled): the session's spoken wording — "if the flag is set as zero, that particular process is ready to enter" — inverts the usual meaning. The standard reading, confirmed by the reference treatment, is flag true = ready to enter: flag[i] = true means $P_i$ wants to enter the critical section. Keep that direction: true is the raised hand, false is the lowered hand.

The two variables play different roles, and the difference matters on the exam. flag is intent: it says "I want in". turn is tie-breaking: when both want in at the same instant, turn decides which one actually goes. A process can set its own flag, and it can set turn — but it cannot set the other's flag. Each process can only lower its own raised hand.

7.4.2 Walking Through the Entry Condition

Start with $i=0$. P0 sets flag[0] = true, and since $j=1$, it sets turn = 1. Now the entry point of the critical section checks the condition:

do {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j)   /* spin while the other is ready and it is its turn */
        ;                          /* wait */
    /* critical section */
    flag[i] = false;
    /* remainder section */
} while (true);

Read the code in order. First P0 raises its own hand (flag[0] = true) — "I want in". Then it gives the turn to the other (turn = 1) — "after me, you may go". Then it checks the entry condition; the spin-wait is the whole entry section. Written as math, the entry condition is:

$$\text{spin while }\text{flag}[j]\wedge (\text{turn}=j),\text{enter when }\neg (\text{flag}[j]\wedge (\text{turn}=j))$$

where $j$ is the other process, $\wedge$ means "and", and $\neg$ means "not". So P0 spins only when both halves hold at once: the other process is ready and the turn belongs to it. As soon as either half becomes false — the other lowered its hand, or the turn is P0's — the conjunction is false and P0 walks in. After the critical section, P0 lowers its own hand in the exit section (flag[0] = false) and then runs its remainder section.

Note on the while-condition (reconciled): the verbal walkthrough in the session states the condition's polarity in both directions at different moments. The code is the authority, and it matches the standard treatment: spin while $\text{flag}[j]$ is true AND turn equals $j$; enter when the conjunction becomes false. The empty body with the semicolon is intentional — the process stays in place, repeatedly re-evaluating the condition, until it becomes false.

If the entry condition is true — meaning the other process is ready and it is its turn — the waiting loop keeps spinning (note the semicolon: the process remains in the same place) until flag[i] becomes false, which happens only after the other process finishes its critical section. Spinning here costs CPU cycles, but with only two processes and a short critical section, the wait is brief; later we will see why busy waiting must generally be avoided (Section 7.6.3).

7.4.3 Checking the Three Requirements

All three requirements hold for Peterson's solution.

Mutual exclusion is present. Suppose P0 has entered the critical section. The turn value is 1 (P0 set it), and flag[1] — with P0 inside — is false, or if P1 also wants in, the turn makes the condition false for P1. P1 cannot enter while P0 is in execution: here itself the condition becomes false for P1. When P0 completes, P1 can come; and if P0 wants to execute again after that, it has to wait in turn. The argument in one line: to enter, a process needs the other's flag false or the turn to be its own; when one process is inside, the other can satisfy neither.

Progress is satisfied. As soon as P0 completes and makes its flag false, immediately P1 can enter the critical section. The entry is not postponed indefinitely. If both are waiting at the entry at once, the turn variable has a definite value, so exactly one of the two enters; the section is never left idle while a process wants it.

Bounded waiting is met. There is a bound — a limit on how many processes are allowed to enter the critical section after the request is made and before it is granted. With two processes the bound is one, so bounded waiting is satisfied: once P1 requests entry, P0 can enter at most once more (the very entry that is in progress) before P1's turn is granted, because the moment P0 exits it must lower its flag and P1's condition fails.

All three conditions are satisfied, so Peterson's solution should be the best solution — but it is a software solution, and it is applicable only for two processes.

7.4.4 The Limitation: Two Processes Only

Recap + bridge: Peterson's solution proves that mutual exclusion, progress, and bounded waiting can be achieved in pure software — with two flags and one turn — but only for two processes and only under an atomicity assumption modern hardware may not honor. So the next step is to ask the hardware for help: atomic instructions that the CPU guarantees, starting with disabling interrupts, then test-and-set and swap.

7.5 Hardware-Based Solutions

7.5.1 Disabling Interrupts: Uniprocessor vs Multiprocessor

In a uniprocessor system, if an interrupt occurs, we can disable the interrupt — the interrupt can be a software-based interrupt or a hardware-based interrupt — and this can be handled efficiently. Why does disabling interrupts protect a critical section? Because on a single CPU, the only way another process can run is by an interrupt or a trap that hands control to the scheduler. If interrupts are switched off, nothing can preempt the running process, so its entry–critical–exit sequence runs as one uninterrupted unit. Nonpreemptive kernels use exactly this approach for their short internal critical sections.

But handling interrupts in a multiprocessor system is generally not efficient. Imagine P1, P2, P3 — three processors, not processes. We do not know when the interrupt will occur in each and every processor. At the time the interrupts occur, we have to disable all the interrupts immediately, and that takes some time — there is an overhead. Disabling the interrupts in each and every processor is very inefficient, and the system is not scalable either: we are just talking about three processors; imagine five processors or ten processors and what would happen.

So we go for some other type of approach: hardware instructions, which are again atomic instructions. The instructions are test-and-set and swap.

7.5.2 The Test-and-Set Instruction

Test-and-set works with the help of a lock. If a processor has acquired the lock, it can execute the test-and-set instruction, and using that, the critical section can be achieved: the processor can enter the critical section and use it, and later it can make the lock false and come out. We acquire the lock in order to enter the critical section; once the critical section is completed, we release the lock; then the remainder section is executed. The remainder section is not a problem, because it is not critical and it is not shareable.

The lock is initialized to false. We pass the address of the lock to the entry section — the entry section holds the hardware-based test-and-set instruction. Only the address is passed, not the value; even if something changes, when we pass the address it is reflected in the return value. Passing the address matters: the instruction must modify the original lock in memory, not a copy, so that every processor sees the same lock. Whatever the original value was, at the end the lock is true — because we are testing and setting it as true. The usage pattern:

while (TestAndSet(&lock))    /* spin while the lock is held */
    ;                        /* wait */
/* critical section */
lock = false;                /* release the lock */
/* remainder section */

Note on the entry polarity (reconciled): the session says "while the condition is true we can enter" in one place and "if this is false it cannot enter" in another. The code and the standard reference agree: spin while TestAndSet(&lock) returns true — the lock was already held — and enter the critical section when it returns false. The polarity of the return value is the whole mechanism: true means "busy", false means "free".

7.5.3 The Swap Instruction

If test-and-set alone is not enough for the hardware-based architectures, we can go for the swap instruction.

do {
    key = true;
    while (key == true)        /* spin while key is still true */
        swap(&lock, &key);
    /* critical section */
    lock = false;              /* release the lock */
    /* remainder section */
} while (true);

If after the swap the key is false, the condition is false, the process comes out of the spin and enters the critical section. Then it executes the critical section, and afterwards the lock is set to false — only when the lock is set to false can any other process compete for the critical section and execute. Then it can execute its remainder section.

We can use both test-and-set and swap, or test-and-set alone — but we have to check whether all three requirements of the critical section problem are solved.

7.5.4 Bounded Waiting with Test-and-Set

Using test-and-set, let us see how the bounded waiting problem is solved. Mutual exclusion is solved anyway: at a time only one process will be in the critical section — if P0 is in the critical section, P1 has to wait; if P1 is in the critical section, P0 has to wait. Progress is also achieved: whenever the lock is free, the first spinning process to win the instruction race enters, so the section is never idle while someone wants it. The remaining question is bounded waiting.

The plain test-and-set loop has no fairness: a slow or unlucky process could spin forever while others keep winning the race — that is starvation. To guarantee a bound, the algorithm adds a waiting array, one entry per process, and replaces blind racing with a polite hand-off. For that we need an array — a waiting array, one entry per process:

do {
    waiting[i] = true;
    key = true;
    while (waiting[i] && key)
        key = TestAndSet(&lock);
    waiting[i] = false;

    /* critical section */

    j = (i + 1) % n;
    while ((j != i) && !waiting[j])
        j = (j + 1) % n;
    if (j == i)
        lock = false;
    else
        waiting[j] = false;

    /* remainder section */
} while (true);

The idea in words: a process only races for the lock while it is actually waiting (waiting[i] true). Once it wins (key becomes false), it clears its waiting flag and enters. On exit, it does not just drop the lock for anyone — it scans the waiting array in cyclic order and hand-picks the next waiting process, granting it the turn; if nobody is waiting, it releases the lock directly.

Walk it through with $n=4$ processes and $i=0$. We set waiting[0] = true and key = true; both conditions are true, so we enter the inner line, execute TestAndSet — whatever the lock was, true or false, at last the returned value is going to be true, so key = true — and then waiting[0] = false. Since waiting[i] is now false, process 0 need not wait; it can enter the critical section.

Note on the scan (reconciled): the session's walkthrough says "we put waiting of two is equal to false" while describing the scan. The standard interpretation, confirmed by the reference code, is exactly that: once the scan finds a waiting process — here waiting[2] — it grants that process the turn by setting waiting[j] = false, which lets the designated process enter. The scan is a polite selection, not a race.

This is how long a particular process can wait after it has made the request and before the request is granted — that is exactly what the bounded waiting requirement checks, and here the bound is $n-1$ entries in the array. So test-and-set and swap, used together, give us hardware-based process synchronization.

Recap + bridge: Disabling interrupts works only on a single CPU; multiprocessors need atomic instructions instead. Test-and-set and swap both implement the lock, and the waiting-array version of test-and-set adds bounded waiting with a bound of $n-1$. The hardware works — but the instructions are complicated for application programmers to manage by hand, which is why the next step wraps them in a simple tool: the semaphore.

7.6 Semaphores

7.6.1 What a Semaphore Is

Even the hardware instructions leave us with too many variables to manage. Test-and-set needs a lock, swap needs a lock and a key, and bounded waiting needs a whole waiting array — every programmer would have to hand-build these every time. So what we can do is have a synchronization tool — a simple solution for process synchronization. That tool is the semaphore.

The mental model: think of $S$ as the number of free "passes" for the resource. A process that wants to enter must first take a pass (wait: if no pass is free — $S\le 0$ — it stands aside), and a process that leaves returns a pass (signal). With $S$ initialized to 1, there is exactly one pass, so only one process can be inside — mutual exclusion, with no explicit lock variable at all.

Two points to keep firmly in mind. First, each and every process must implement both operations — it should not be the wait operation alone; both wait and signal have to be implemented in every process. That is very important. A process that only waits but never signals steals a pass forever and permanently shrinks the semaphore; a process that only signals manufactures passes out of thin air. The pair is a contract: every entry is paid for by some exit.

Second, we must guarantee that no two processes can execute wait and signal at the same time. If a process is executing wait(S), the other processes should not execute the wait on the same semaphore variable. Example: if $P$ is a semaphore variable and P1 executes wait(P), P2 cannot do the same thing at the same time. So we place wait and signal both in the critical section; some process will be executing it, or waiting to enter the critical section — either way, the operations are protected. In other words, the semaphore's own implementation is protected by the very same mutual exclusion it provides to applications — the wait/signal code itself is short, so protecting it costs almost nothing.

7.6.2 Counting and Binary Semaphores

There are two types of semaphores: counting semaphore and binary semaphore.

A counting semaphore is an integer value which can range over any unrestricted value — there is no restricted value; it can hold any integer value. A binary semaphore can take only two values: either 0 or 1.

7.6.3 Avoiding Busy Waiting: Block and Wakeup

What is busy waiting? If some process is executing in the critical section and some other process is waiting for a long time, or executing a spin lock — spinning in the same place instead of going into the critical section and executing it — that is busy waiting. We have to always avoid busy waiting. A spinning process burns CPU cycles doing nothing but re-checking a condition — on a single CPU, it even steals cycles from the very process it is waiting for, which can stretch the wait indefinitely.

What we can do instead: each semaphore implements a waiting queue with two data items — value and pointer. The value is an integer; the pointer is an address that points to the next record present in the list. The queue supports two operations: block and wakeup.

The block operation blocks the process from entering the critical section and puts it in the waiting queue. If P1, P2, P3 are three processes and P1 is executing in the critical section, then when P2 and P3 come they will be blocked — placed in the queue. The wakeup operation removes one of the processes present in the queue — whichever came first, P2 or P3 — and places it in the ready queue so it can go for execution. Blocked processes consume no CPU: they are asleep on the queue, not spinning, and the scheduler simply does not pick them.

We implement wait and signal in terms of the value and the address:

$$\text{wait}(S):S.\text{value}\leftarrow S.\text{value}-1;\text{if }S.\text{value}<0\text{ then add process to the list and }\text{block()}$$

$$\text{signal}(S):S.\text{value}\leftarrow S.\text{value}+1;\text{if }S.\text{value}\le 0\text{ then remove a process from the list and }\text{wakeup()}$$

7.6.4 Deadlock with Semaphores

Because of this, there are chances for deadlock and starvation — as we said earlier. Deadlock happens when two or more processes are waiting indefinitely for an event that can be caused only by one of the waiting processes.

The general shape to recognize: deadlock is a circular dependency between resources. Section 7.2's example was a temporary wait (everyone waits on P4, who is outside the waiters); this semaphore example is the permanent kind (each waiter waits on another waiter). In a later lecture we study the four conditions that create such circles and the strategies to break them.

7.6.5 Starvation, Priority Inversion, and Priority Inheritance

Starvation with semaphores: sometimes a process may enter into the critical section and stay long in the same process. In that case we have to suspend it and remove it. If the same process is using the critical section for a long time, that is starvation. We can solve this starvation problem. On the semaphore side, the risk is built into the waiting list: if blocked processes are removed from the list in LIFO order (last in, first out), a process that arrived early can be overtaken forever — an indefinite wait. A FIFO queue avoids that, which is why the queue order is not a detail but a fairness decision.

Which process will take a long time? The most important starvation scenario is the one caused by priorities. Suppose we have priority-based processes: P0 has the lowest priority, call it L; P1 has medium priority; P2 has the highest priority, call it H. Suppose P0, the low-priority process, is currently holding the critical section. If P1 comes — P1 is runnable, which means it is ready to enter the critical section — then, since it is priority-based scheduling, P0 has to go out of the CPU. But what happens here is priority inversion: a low-priority process ends up blocking a higher-priority one.

Real-world: priority inheritance is exactly the mechanism real-time operating systems use to stop low-priority tasks from indefinitely blocking high-priority ones. The best-known case is the NASA Mars Pathfinder mission in 1997: shortly after the Sojourner rover started operating, a high-priority task was repeatedly blocked by a low-priority task holding a shared resource while medium-priority tasks preempted it — a textbook priority inversion that caused the spacecraft's computer to keep resetting. The fix was switching on VxWorks' priority inheritance flag, and the mission proceeded normally.

7.6.6 Why Semaphores Come Last

Putting it all together: the software-based solution, Peterson's solution, works only for two processes. So we went for hardware-based solutions using the test-and-set and swap instructions. But since those are based on hardware, they were very complicated for application programmers. We need some other tool which is very simple and effective — so we go for the semaphore.

The classical problems of synchronization — the bounded-buffer, the readers–writers problem, the dining philosophers, and the rest — which we will see in the next session, are built on top of these tools.

Exam Guidance Summary

• The mid-semester exam is on 16th March. Everything covered up to and including the 8th contact session (the next session) is in the syllabus: the portion taken in this session and the completion of process synchronization in the next session will be there for the mid-semester. The portion taken in the 9th contact session will not be included, even though the 9th session falls before the exam date.

• Process synchronization is a two-session topic: the requirements and solutions (software, hardware, semaphores) come in this session; the classical synchronization problems are completed in the next session. The syllabus for the mid-semester is still process synchronization. Plan your revision as one block: the tools from this session are the raw material of next session's problems.

• Quiz correction: one quiz question about "maximum CPU utilization by using..." was found to have two possible answers (the options about maximum turnaround time and maximum response time were both undesirable), but the quiz allowed only one answer. The instructor will add the marking mask for multiple answers later; it was pointed out by a majority of students. If you marked either of those two options, the corrected marking mask will credit the question once it is added.

Key Industry Applications

• Real-world: multiprocessor chips — a single chip with multiple cores, each core with many hardware threads — are how modern systems achieve concurrent execution; each thread is capable of executing a process. Every smartphone processor, desktop CPU, and cloud server CPU is built this way, and the operating system's scheduler and synchronization layer are what let thousands of threads share those cores safely.

• Real-world: priority inheritance protocol is used in real-time operating systems to prevent low-priority processes from indefinitely blocking high-priority ones (the priority inversion problem). The mechanism is a standard feature of real-time kernels (for example, VxWorks' priority inheritance flag, the very fix that saved NASA's Mars Pathfinder mission in 1997), and it is equally built into the mutexes of general-purpose systems.

• Real-world: printer sharing in a lab or office is a daily example of a non-shareable resource: two users cannot use the same printer at the same instant, while the memory and CPU of a machine are genuinely shared among many processes. The print spooler that queues jobs is the synchronization system at work, and the same pattern recurs in every exclusive device and every shared database row.

• Real-world: semaphores are the classic synchronization tool for producers and consumers, and the no-busy-waiting queue (block and wakeup) is the model behind modern blocking synchronization in operating systems — mutexes, condition variables, and the futex primitives of Linux all trace their design to the semaphore's waiting queue. When an application thread calls a lock that "sleeps" instead of burning CPU, it is using the block/wakeup idea from this lecture.