When multiple processes are blocked on the same semaphore, which one wakes up first? The answer is not always the one that waited longest. This file explains the ordering rules the kernel uses to unblock waiting processes and how starvation can happen in poorly designed applications.
When blocked processes waiting on a semaphore are finally unblocked, the kernel follows different rules depending on whether they are all waiting for the same decrement amount or different amounts.
The kernel picks one process to unblock, but which one is indeterminate. The choice depends on the kernel’s scheduling algorithm. You cannot rely on FIFO (first-in, first-out) order. Any of the waiting processes may get to go first.
Requests are served in the order in which they become satisfiable. The process whose required decrement amount can be satisfied by the current semaphore value is unblocked first — even if it submitted its request later than other waiting processes.
Consider a semaphore with an initial value of 0. The following sequence leads to starvation:
Process A requests -2
→ BLOCKS (needs 2, only 0 available)
→ BLOCKS (needs 1, only 0 available)
Now: A and B both waiting
Semaphore value = 1
B needs 1 → B unblocks!
A still blocked (needs 2)
Process A starves forever.
Process B unblocked ahead of Process A because B’s required amount (1) became satisfiable first, even though A submitted its request earlier.
Starvation can also occur when a process is waiting to atomically operate on multiple semaphores. The kernel only unblocks a process when all conditions can be satisfied simultaneously.
- Process A requests: subtract 1 from sem[0] AND subtract 1 from sem[1] → blocks
- Process B requests: subtract 1 from sem[0] only → blocks
- Process C adds 1 to sem[0]
- Process B unblocks (needs only sem[0]). Process A remains blocked (still needs sem[1]).
- This can repeat indefinitely if sem[1] is never raised enough simultaneously with sem[0].
The key insight is that requiring multiple conditions to be satisfied simultaneously is harder to satisfy than requiring a single condition. In busy systems, the chance of both conditions being true at the same time may be very low.
This example shows that when Process A is waiting to subtract 2 and Process B is waiting to subtract 1, adding 1 satisfies B first even though A arrived earlier.
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/sem.h>
#include <sys/wait.h>
#include <time.h>
static void ts_print(const char *label) {
struct timespec ts;
clock_gettime(CLOCK_REALTIME, &ts);
printf("[%ld.%03ld] %s\n", (long)ts.tv_sec % 1000, ts.tv_nsec / 1000000L, label);
}
int main(void)
{
int semid = semget(IPC_PRIVATE, 1, IPC_CREAT | 0600);
if (semid == -1) { perror("semget"); return 1; }
/* Start at 0 */
semctl(semid, 0, SETVAL, 0);
printf("Semaphore created, value = 0\n\n");
/* Fork Process A: wants to subtract 2 (blocks until semaphore >= 2) */
pid_t pidA = fork();
if (pidA == 0) {
struct sembuf sop = {0, -2, 0};
ts_print("Process A: requesting -2 (will need semaphore >= 2)");
semop(semid, &sop, 1);
ts_print("Process A: UNBLOCKED, decremented by 2");
exit(0);
}
usleep(10000); /* tiny delay so A registers first */
/* Fork Process B: wants to subtract 1 (blocks until semaphore >= 1) */
pid_t pidB = fork();
if (pidB == 0) {
struct sembuf sop = {0, -1, 0};
ts_print("Process B: requesting -1 (will need semaphore >= 1)");
semop(semid, &sop, 1);
ts_print("Process B: UNBLOCKED, decremented by 1");
exit(0);
}
usleep(10000); /* let both A and B block */
/* Check who is waiting */
int ncnt = semctl(semid, 0, GETNCNT);
printf("Both processes now waiting. semncnt = %d\n\n", ncnt);
/* Add 1: only Process B can proceed (needs 1), Process A still needs 2 */
ts_print("Parent: adding +1 to semaphore");
struct sembuf add1 = {0, +1, 0};
semop(semid, &add1, 1);
sleep(1);
printf("\nAfter adding 1:\n");
printf(" semval = %d\n", semctl(semid, 0, GETVAL));
printf(" semncnt = %d (Process A still waiting)\n\n", semctl(semid, 0, GETNCNT));
/* Now add 1 more so Process A can proceed */
ts_print("Parent: adding +1 more to allow Process A");
semop(semid, &add1, 1);
wait(NULL);
wait(NULL);
semctl(semid, 0, IPC_RMID);
printf("\nDone.\n");
return 0;
}Key observation from output: Process B will print “UNBLOCKED” before Process A even though A requested the operation first. B’s smaller requirement (1) was satisfied when the parent added the first +1; A needed a second +1 before it could proceed.
System V semaphores provide no built-in starvation prevention. Developers must design their applications carefully:
| Strategy | How It Helps | Limitation |
|---|---|---|
| Use only unit decrements (-1) | All requests become equal; kernel picks fairly | Not always applicable |
| Use POSIX semaphores (sem_wait) | POSIX guarantees FIFO unblocking (priority-based) | Only single semaphore per call |
| Use mutex + condition variable (pthreads) | Fine-grained control over ordering | Only within one process |
| Avoid holding multiple semaphores | Reduces chance of circular dependency | May limit throughput |
Using only -1 and +1 operations ensures all requestors compete equally (though still not strictly FIFO in System V). This is the safest pattern.
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/sem.h>
#include <sys/wait.h>
#define NUM_WORKERS 4
/* Acquire semaphore (subtract 1) – blocks if busy */
void sem_lock(int semid) {
struct sembuf sop = {0, -1, 0};
semop(semid, &sop, 1);
}
/* Release semaphore (add 1) */
void sem_unlock(int semid) {
struct sembuf sop = {0, +1, 0};
semop(semid, &sop, 1);
}
int main(void)
{
/* Create binary semaphore (initial value 1 = unlocked) */
int semid = semget(IPC_PRIVATE, 1, IPC_CREAT | 0600);
semctl(semid, 0, SETVAL, 1);
printf("Spawning %d workers...\n", NUM_WORKERS);
for (int i = 0; i < NUM_WORKERS; i++) {
pid_t pid = fork();
if (pid == 0) {
printf("Worker %d: trying to acquire lock...\n", i);
sem_lock(semid);
printf("Worker %d: LOCKED - doing critical work\n", i);
sleep(1); /* simulate work */
printf("Worker %d: releasing lock\n", i);
sem_unlock(semid);
exit(0);
}
}
/* Wait for all workers */
for (int i = 0; i < NUM_WORKERS; i++)
wait(NULL);
semctl(semid, 0, IPC_RMID);
printf("All workers done.\n");
return 0;
}With value initialized to 1 and only unit operations, at most one worker holds the lock at a time. Workers alternate access without any single process monopolizing the semaphore.
Q1: Is the wake-up order of blocked semaphore processes guaranteed to be FIFO?
No. System V semaphores make no guarantee about FIFO order. When multiple processes are waiting to subtract the same amount, the kernel picks one based on its scheduling algorithm — the result is indeterminate from the application’s perspective.
Q2: When multiple processes block on a semaphore with different decrement amounts, how does the kernel decide who to wake?
The kernel unblocks the process whose required amount can first be satisfied by the current semaphore value. If semaphore = 1, a process wanting -1 runs even if a process wanting -2 arrived earlier.
Q3: Describe a scenario where starvation occurs with System V semaphores.
Process A waits to subtract 2. Multiple other processes repeatedly add 1 and subtract 1, keeping the semaphore fluctuating between 0 and 1. Since the value never reaches 2, Process A is starved indefinitely even though it was first to request the operation.
Q4: How can multi-semaphore atomic operations lead to starvation?
A process waiting to atomically decrement semaphores 0 and 1 requires both conditions to be satisfiable at the same instant. Other processes that need only one of the semaphores can repeatedly satisfy their partial requirements, preventing the multi-semaphore process from ever proceeding.
Q5: Which IPC mechanism is preferable over System V semaphores when strict ordering is needed?
POSIX semaphores (sem_wait() / sem_post()) provide more predictable priority-based unblocking. Within a single process, POSIX mutexes with condition variables give even finer control via pthread_cond_timedwait().