Lecture Notes for Operating Systems Concepts

13 June 2002 - Peterson's Algorithm

Peterson's Algorithm

• Establish exclusive access to shared resources.

  • No starvation.

  • No unnecessary delays.

• The basic ideas.

  • Each process seeks the other's permission

  • Unless there's no conflict over the shared resource.

• The algorithm depends on the number of processes.

  • Two processes, named 0 and 1.

Algorithm Parts

• Shared variables

  static bool wants_in[2]
  static int turn
  

• Establish mutual exclusion.

  void peterson_in(int me)
  
    const int other = me == 1 ? 0 : 1
  
    wants_in[me] = true
    turn = other
  
    while (wants_in[other] && (turn == other))
      yield()
    
    // caller now has the stone.
  

• Release mutual exclusion.

  void peterson_out(int me)
  
    // Caller releases the stone.
  
    wants_in[me] = false
  

Using the Algorithm

• Defining the threads.

  static int in_critical_region
  
  void proc(int myid)
  
    for (int i = 0; i < 1000; i++)
  
      peterson_in(myid)
  
        assert(in_critical_region == 0)
        in_critical_region++
  
        yield()
  
        assert(in_critical_region == 1)
        in_critical_region--
  
      peterson_out(myid)
  

• Running the threads.

  int main()
  
    wants_in[0] = wants_in[1] = false
    in_critical_region = 0
  
    thread_create(proc, 0)
    thread_create(proc, 1)
  

This page last modified on 25 June 2002.