返回

[UCSD CSE120]同步-synchronization

本文是我在上UCSD的 CSE 120: Principles of Operating Systems (Winter 2020) 整理的笔记,这一课主要介绍了操作系统里面进程同步的算法,主要是信号量 (Semaphores) 的使用。

Problem introduction

  1. Introduction

    • synchronization: events happen at the same time
    • Process synchronization
      • Events in process that occur “at the same time”
      • one process have to wait for another
    • Usage
      • prevent race conditions
      • wait for resources to become available
  2. race condition

    • race condition: two process which should run sequently accidentally run at the same time (which cause a bug)
    • To avoid race conditions:
      • identify related critical sections
        • Section of code excuted by different processes
        • critical sections must run atomically w.r.t each other
      • Enforce mutual exclusion
        • only one process is allowed to be active in critical section
    • Atomic
      • atomic means “indivisible”
      • effective atomicity
        • interrupt may occur, but it shouldn’t has effect on that section caused by other processes
      • How to determine wether a critical section is atomic
        • Consider effect of critical section in isolation
        • Consider interruptions: if the result is same, then it is OK.
    • Mutual exclusion
      • Surrond critical section with entry/exit code
      • entry code act as a barrier
        • if another process is critical section, block current process till it exit
        • Otherwise, allow process to proceed
      • Exit code should release other entry barriers
  3. Requirements for good solution

    • Given
      • multiple cooperating process
      • each with related critical sections
    • At most one process in a critical section
    • Can’t prevent entry if no others in critical section
    • Should eventually be able to enter critical section
    • No assumptions about CPU speed or number.

Different approaches for mutual exclusion (workable)

  1. Peterson’s solution

    • implementation

      shared int turn;
      shared bool intent[2] = {false, false};
      
      // P0
      intent[0] = TRUE;
      turn = 1; turn = 0;
      while (intent[1] && turn==1);
      /*
      < critical section >
      */
      intent[0] = FALSE;
      
      // P1
      intent[1] = TRUE;
      while (intent[0] && turn==0);
      /*
      < critical section >
      */
      intent[1] = FALSE;
      
    • if competition occur, take turns, otherwise enter

    • for competing process number larger than 2, the solution will become more complex

  2. Test-and-Set Lock Instruction: TSL

    • requirement: TSL mem

      do atomically (i.e., locking the memory bus)
          [test if mem == 0 AND set mem = 1]
      
    • a possible C function implementation for TSL (it should be guaranteed atomic)

      TSL(int *lockptr) {
          int oldval;
          oldval = *lockptr
          *lockptr = 1;
          return ((oldval == 0) ? 1 : 0);
      }
      
    • mutual exclusion using TSL

      shared int lock = 0;
      // P0
      while (! TSL(&lock));
      /*
      < critical section >
      */
      lock = 0;
      
      // P1
      while (! TSL(&lock));
      /*
      < critical section >
      */
      lock = 0;
      
    • shared variable solution using TSL(int *)

      • test if lock == 0 (if so, will return 1; else 0)
      • before returning, sets lock to 1
    • simple, works for any number of threads

    • still suffering from busy waiting

  3. Semaphores

    • Synchronization varaible

      • takes on integer values (non-negative)
      • can cause a process to block/unblock
    • wait and signal operations (must be atomic, use a lower-level mechanism)

      • wait(s) block if zero, else decrement
      • signal(s) unblock a process if any, else increment
    • no other operations allowed (cannot change/test value of semaphore)

    • simple, works for n processes

    • busy-waiting still exist, but it lies inside semephore, which last shorter

    • Implementation

      wait(sem s) {
          s.n = s.n  1;
          if (s.n < 0) {
              addProc (me, s.L); // add process to waiting list
              block (me);
          }
      }
      
      signal(sem s) {
          s.n = s.n + 1;
          if (!empty (s.L)) {
              p = removeProc (s.L); // select a process from waiting list to release
              unblock (p);
          }
      }
      
    • Only synchronization, no information transfer

      • no way for a process to tell it blocked
  4. Usage of semaphore

    • basic usage example

      sem mutex = 1;
      //P0
      wait(mutex);
      /*
      < critical section >
      */
      signal(mutex);
      
      //P1
      wait(mutex);
      /*
      < critical section >
      */
      signal(mutex)
      
    • order how processes execute

      sem cond = 0;
      
      // P0
      /*
      < to be done before P1 >
      */
      signal(cond);
      
      // P1
      wait(cond);
      /*
      < to be done after P0 >
      */
      
Built with Hugo
Theme Stack designed by Jimmy