Process Synchronization and Virtual Machines

Process Synchronization and Virtual Machines

Course Learning Outcomes (CLOS)

• a. Describe the structure and key functions of an operating system: Relates to Program Learning Outcome (PLO) #1 for BSDA, BSIS, and BSIT.

• b. Use operating system software tools for process and thread synchronization: Relates to PLO#2 for BSDA, BSIS, and BSIT.

• c. Implement and evaluate different scheduling algorithms and policies.

• d. Characterize a deadlock and take corrective action: Relates to PLO#2 for BSDA, BSIS, and BSIT.

• e. Compare and contrast different techniques of memory management: Relates to PLO#1 for BSDA, BSIS, and BSIT.

• f. Manage input-output, file systems, storage systems, and directories through functions and system calls: Relates to PLO#1 for BSDA, BSIS, and BSIT.

• g. Use protection and security features of an operating system: Relates to PLO#7 for BSDA and BSIS, and PLO#2 for BSIT.

/

Producer Consumer Problem (Code)

• Code snippet demonstrates the producer-consumer problem.

• Producer:

  • Produces an item in next_produced.

  • Waits if the buffer is full (counter == BUFFER_SIZE).

  • Adds the item to the buffer at index in.

  • Updates in using modulo arithmetic (in = (in + 1) % BUFFER_SIZE).

  • Increments the counter (counter++).

• Consumer:

  • Waits if the buffer is empty (counter == 0).

  • Consumes the item from the buffer at index out into next_consumed.

  • Updates out using modulo arithmetic (out = (out + 1) % BUFFER_SIZE).

  • Decrements the counter (counter--).

• Relevant code:

  while (true) {
  /* produce an item in next produced */
  while (counter == BUFFER_SIZE) ;
  /* do nothing */
  buffer[in] = next_produced;
  in = (in + 1) % BUFFER_SIZE;
  counter++;
  }
  
  while (true) {
  while (counter == 0) ;
  /* do nothing */
  next_consumed = buffer[out];
  out = (out + 1) % BUFFER_SIZE;
  counter--;
  /* consume the item in next consumed */
  }
  

Problem with Counter Increment/Decrement

• The issue arises from the non-atomic nature of counter++ and counter-- operations.

• counter++ is implemented as:

  1. register1 = counter

  2. register1 = register1 + 1

  3. counter = register1

• counter-- is implemented as:

  1. register2 = counter

  2. register2 = register2 - 1

  3. counter = register2

• Example of Execution Interleaving (initial count = 5):

  • S0: Producer executes register1 = counter {register1 = 5}

  • S1: Producer executes register1 = register1 + 1 {register1 = 6}

  • S2: Consumer executes register2 = counter {register2 = 5}

  • S3: Consumer executes register2 = register2 - 1 {register2 = 4}

  • S4: Producer executes counter = register1 {counter = 6}

  • S5: Consumer executes counter = register2 {counter = 4}

• The final value of the counter is incorrect due to the interleaved execution.

Critical Section Problem

• Consider a system of $n$ processes ${{p<em>0, p</em>1, …, p_{n-1}}}$.

• Each process has a critical section, which is a segment of code.

• Processes may be changing common variables, updating tables, writing files, etc., within their critical sections.

• When one process is in its critical section, no other process may be in its critical section (mutual exclusion).

• Each process must request permission to enter its critical section in the entry section.

• After the critical section, a process executes an exit section, followed by the remainder section.

Critical Section Structure

• General structure of a process $P_i$:

Algorithm for Process $P<em>i$ and $P</em>j$

• Code for process $P_i$:

  do {
    while (turn == j);
    critical section
    turn = j;
    remainder section
  } while (true);
  

• Code for process $P_j$:

  do {
    while (turn == i);
    critical section
    turn = i;
    remainder section
  } while (true);
  

• The initial value of turn is