COS3701
Assignment 2
Chapters 6, 7, 8, 9, 10, & 18
Due 2025
,COS3701
Assignment 2: Operating Systems and Architecture (COS3721)
Due 2025
Chapter 6: Synchronization
3.1.1 Question 1: Race Conditions in Stack Operations
The provided pseudocode for push() and pop() operations on an array-based stack, despite
containing acquire() and release() calls, remains susceptible to race conditions in a
concurrent environment.
a) Data with Race Conditions: The primary data structure prone to race conditions is
the top variable, which acts as the stack pointer. Both push() and pop() operations
modify this shared variable (incrementing and decrementing, respectively), and its
value dictates array indexing within the stack array. Without atomic operations or
more granular locking, interleaved execution could lead to:
Inconsistent top value: Multiple threads attempting to push or pop concurrently
might read the same top value before one of them updates it, leading to incorrect
calculations for the next available slot or element to retrieve. For example, two
threads executing push() could both read top as N, then both write to stack[N],
causing one write to be lost. Similarly, two pop() operations could decrement top
twice, potentially leading to an underflow or reading incorrect data.
Corruption of stack array: The stack array elements themselves are vulnerable to
race conditions because their access (reading or writing) is predicated on the
potentially erroneous top value. Data could be overwritten or read from an invalid
location.
b) Fixing the Race Condition: The presence of acquire() and release() suggests an
underlying locking mechanism. To effectively prevent race conditions, these
functions must implement a robust mutual exclusion primitive, such as a mutex. The
critical sections that require protection are:
1
, For push(): The sequence involving the capacity check (if (top < SIZE)), the data
assignment (stack[top] = item;), and the increment (top++;).
For pop(): The sequence involving the emptiness check (if (!is empty())), the
decrement (top--;), and the data retrieval (item = stack[top];).
By enclosing these critical sections within acquire() and release() calls that guarantee only
one thread can execute them at any given time, the atomicity of stack operations is ensured.
This approach adheres to the fundamental principle of mutual exclusion, crucial for
maintaining data consistency in concurrent systems dijkstra1965solution.
2
, 3.1.2 Question 2: Dekker’s Algorithm for Critical Section Problem
Dekker’s algorithm is a seminal software solution for the critical-section problem involving
two processes, P0 and P1, utilizing shared boolean flags (flag[2], initially false) and an
integer turn variable. It demonstrably satisfies the three requirements for a robust critical-
section solution:
Mutual Exclusion: This property ensures that only one process can execute its critical
section at any given moment. In Dekker’s algorithm, if Pi wishes to enter its
critical section, it first signals its intent by setting flag[i] = true. It then checks flag[j] (the
other process’s flag). If flag[j] is also true, indicating contention, Pi enters a loop where it
yields its claim (flag[i] = false) if it’s not its turn (turn == j). It waits until turn changes.
When turn == i, Pi can proceed. Upon exiting its critical section, Pi sets turn = j and then
flag[i] = false. This mechanism ensures that if both processes simultaneously attempt to
enter their critical sections, only the process whose turn it is will succeed, while the other
temporarily withdraws, thus strictly preventing simultaneous entry.
Progress: Progress dictates that if no process is in its critical section, and some processes
desire to enter, then only those processes not in their remainder sections may participate in
the decision of which process enters next, and this decision cannot be indefinitely
postponed. Dekker’s algorithm satisfies this by ensuring that if Pi wants to enter and Pj does
not (flag[j] is false), Pi will immediately enter its critical section. If both desire entry, the
turn variable breaks the tie, allowing one to proceed. The waiting process eventually
receives its turn, preventing indefinite blocking. No process is arbitrarily delayed when no
other process is in its critical section.
Bounded Waiting: Bounded waiting guarantees that there’s a finite limit on the number of
times other processes can enter their critical sections after a process requests entry, but
before its request is granted. In Dekker’s algorithm, if Pi is waiting for its turn, say because
turn == j, when Pj exits its critical section, it explicitly sets turn = i. This guarantee ensures
that Pi will eventually have its turn to proceed. Each process gets at most one opportunity to
enter its critical section before a waiting process gets its chance, thereby preventing
3
Assignment 2
Chapters 6, 7, 8, 9, 10, & 18
Due 2025
,COS3701
Assignment 2: Operating Systems and Architecture (COS3721)
Due 2025
Chapter 6: Synchronization
3.1.1 Question 1: Race Conditions in Stack Operations
The provided pseudocode for push() and pop() operations on an array-based stack, despite
containing acquire() and release() calls, remains susceptible to race conditions in a
concurrent environment.
a) Data with Race Conditions: The primary data structure prone to race conditions is
the top variable, which acts as the stack pointer. Both push() and pop() operations
modify this shared variable (incrementing and decrementing, respectively), and its
value dictates array indexing within the stack array. Without atomic operations or
more granular locking, interleaved execution could lead to:
Inconsistent top value: Multiple threads attempting to push or pop concurrently
might read the same top value before one of them updates it, leading to incorrect
calculations for the next available slot or element to retrieve. For example, two
threads executing push() could both read top as N, then both write to stack[N],
causing one write to be lost. Similarly, two pop() operations could decrement top
twice, potentially leading to an underflow or reading incorrect data.
Corruption of stack array: The stack array elements themselves are vulnerable to
race conditions because their access (reading or writing) is predicated on the
potentially erroneous top value. Data could be overwritten or read from an invalid
location.
b) Fixing the Race Condition: The presence of acquire() and release() suggests an
underlying locking mechanism. To effectively prevent race conditions, these
functions must implement a robust mutual exclusion primitive, such as a mutex. The
critical sections that require protection are:
1
, For push(): The sequence involving the capacity check (if (top < SIZE)), the data
assignment (stack[top] = item;), and the increment (top++;).
For pop(): The sequence involving the emptiness check (if (!is empty())), the
decrement (top--;), and the data retrieval (item = stack[top];).
By enclosing these critical sections within acquire() and release() calls that guarantee only
one thread can execute them at any given time, the atomicity of stack operations is ensured.
This approach adheres to the fundamental principle of mutual exclusion, crucial for
maintaining data consistency in concurrent systems dijkstra1965solution.
2
, 3.1.2 Question 2: Dekker’s Algorithm for Critical Section Problem
Dekker’s algorithm is a seminal software solution for the critical-section problem involving
two processes, P0 and P1, utilizing shared boolean flags (flag[2], initially false) and an
integer turn variable. It demonstrably satisfies the three requirements for a robust critical-
section solution:
Mutual Exclusion: This property ensures that only one process can execute its critical
section at any given moment. In Dekker’s algorithm, if Pi wishes to enter its
critical section, it first signals its intent by setting flag[i] = true. It then checks flag[j] (the
other process’s flag). If flag[j] is also true, indicating contention, Pi enters a loop where it
yields its claim (flag[i] = false) if it’s not its turn (turn == j). It waits until turn changes.
When turn == i, Pi can proceed. Upon exiting its critical section, Pi sets turn = j and then
flag[i] = false. This mechanism ensures that if both processes simultaneously attempt to
enter their critical sections, only the process whose turn it is will succeed, while the other
temporarily withdraws, thus strictly preventing simultaneous entry.
Progress: Progress dictates that if no process is in its critical section, and some processes
desire to enter, then only those processes not in their remainder sections may participate in
the decision of which process enters next, and this decision cannot be indefinitely
postponed. Dekker’s algorithm satisfies this by ensuring that if Pi wants to enter and Pj does
not (flag[j] is false), Pi will immediately enter its critical section. If both desire entry, the
turn variable breaks the tie, allowing one to proceed. The waiting process eventually
receives its turn, preventing indefinite blocking. No process is arbitrarily delayed when no
other process is in its critical section.
Bounded Waiting: Bounded waiting guarantees that there’s a finite limit on the number of
times other processes can enter their critical sections after a process requests entry, but
before its request is granted. In Dekker’s algorithm, if Pi is waiting for its turn, say because
turn == j, when Pj exits its critical section, it explicitly sets turn = i. This guarantee ensures
that Pi will eventually have its turn to proceed. Each process gets at most one opportunity to
enter its critical section before a waiting process gets its chance, thereby preventing
3
