Synchronization (2)

Critical Section Problem

  • A protocol solving this must ensure:

    • Mutual Exclusion: Only one process in the critical section.

    • Progress: Processes outside the critical section cannot block entry and processes inside the critical section remain for a finite time.

    • Bounded Waiting: Guaranteed entry in a limited time; the scheduling algorithm ensures eventual scheduling.

Strict Alternation

  • Busy-waiting Strategy: Processes wait for their turn using spin locks.

  • Involves two processes, P0 and P1, and a shared lock variable.

    • lock indicates which process can enter the critical section; previous process sets it.

    • Operates like a token transferred between processes.

  • Issues:

    • Doesn't reliably ensure mutual exclusion; both processes can enter the critical section simultaneously.

Use an Array of Flags

  • Employs an array of flags (one per process) instead of a single turn variable.

    • Announcement: Processes announce intent by setting their flag to TRUE.

    • Check: Processes check other's flag.

  • Principle:

    • "Read the other’s flag"

    • "Write own flag only"

  • Issues:

    • Can lead to deadlock due to context switching.

Peterson’s Algorithm

  • Non-atomic locking for two processes using turn variable and flag array.

boolean flag[2];
int turn;

// Process i
while (TRUE) {
    flag[i] = TRUE;
    turn = j; //or i
    while (flag[j] == TRUE && turn == j) { // wait }
    Critical_Section
    flag[i] = FALSE;
    Non_Critical_Section
}

  • Operation:

    • Processes set their flag to TRUE and indicate the other process's turn.

    • They wait while the other process is ready and it's their turn.

  • Properties:

    • Mutual Exclusion: Preserved even with simultaneous readiness; turn ensures only one enters.

    • Progress and Bounded Waiting: Guaranteed since a process will eventually gain access.

  • Issues:

    • Limited to two processes.

    • A busy-waiting solution, wasting CPU time.

Question

  • Starvation can occur if a process is continuously blocked by the other process manipulating the turn variable.