[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 >
     */