3. Progress Graphs

• A progress graph depictsthe discrete execution state space of concurrentthreads.

• Each axis corresponds to the sequential order of instructions in a thread.

• Each point corresponds to a possible execution state (Inst1, Inst2).

• E.g., (L1, S2) denotes state where thread 1 has completed L1 and thread 2 has completed S2

프로세스 그래프 : 스레드 1,2 번이 동시에 실행될때(concurrent) execution state space를 discrete해서 설명하는 공간을 이야기 한다.

위의 그래프를 보면 thread1, 2가 실행중이다. HLUST라는 것은 cnt++를 하기 위한 순차적인 순서이다. 이 각각의 포인트는 우리가 어떤 가능한 execution state를 만든다. 그래서 위의 L1, S2는 Thread1, 2가 각각 현재의 state를 이야기 한다.

Trajectories in Progress Graphs

• A trajectory is a sequence of legal state transitions that describes one possible concurrent execution of the threads.

• Example:
  H1, L1, U1, H2, L2, S1, T1, U2, S2, T2

trajectory : concurrent하게 스레드들이 실행될때 가능한 상태 transition의 sequence를 보고 trajectory라고 부른다.

예시로든 H1, L1, U1, H2, L2, S1, T1, U2, S2, T2에 따라서 실행된다고 해보자

그럼 우리는 이 그림을 보고 어떤 순으로 scheduling이 발생했을때 이 sequence들이 발동하는지를 표현할 수 있다. trajectory는 미사일의 궤적쯤으로 생각하면 좋다.

H1,L1,U1까지 실행되고 time interrupt로 scheduling이 되어서 H2, L2가 실행되다가 time interrupt, S1, T1 -> U2,S2,T2 순으로 처리된다.

Critical Sections and Unsafe Regions

• L, U, and S form a critical section with respect to the shared variable cnt

• Instructions in critical sections (wrt some shared variable) should not be interleaved

• Sets of states where such interleaving occurs form unsafe regions
  

그런데 우리가 보는 이것은 0,0 에서 시작해서 T1,T2로 가는 방법은 수십가지가 존재한다.

하지만 이중에서도 unsafe한 영역이 존재한다. unsafe한 영역은 cnt++ 결과값이 각각 스레드들이 0->1로 나올 수 있는 영역이라고 보면된다. 그 영역을 보고 Unsafe하다 혹은 critical section이라고 부른다.

critical section은 cnt++ 하는 영역을 이야기 하고 unsafe는 이 궤적에서 지나면 안되는 영역을 이야기 한다. 여기에서는 cnt가 critical section이다. 우리가 progress 그래프를 그릴때 절때 지나면 안되는 지역을 unsafe region이라고 한다.

그래서 critical section에 있는 명령어는 interleaving 되면 안된다. 그 interleaving이 발생할 수 있는 영역을 unsafe region이라고 부른다.

---

• Def: A trajectory is safe iff it does not enter any unsafe region
• Claim: A trajectory is correct (wrt cnt) iff it is safe
  

끝과 끝을 갈때 스레드1, 2번이 언제 스케쥴링될지는 알 방법이 없다. hardware interrupt timer에 따라서 처리되는 것이기 때문에 프로그래머가 처리할 수 없다. unsafe region에 들어가지 않는다면 이 trajectory는 safe하다고 부른다.

만약에 빨간색처럼 지나간다면 unsafe하다고 볼 수 있다.

Enforcing Mutual Exclusion

• Question: How can we guarantee a safe trajectory?

앞에 있었던 괘적을 어떻게 보장할것인가? thread1, thread2번이 cnt = 0으로 초기화 했을때 어떻게 cnt = 2가 된다는 것을 보장하는가?

• Answer: We must synchronize the execution of the threads so that they can never have an unsafe trajectory.
  • i.e., need to guarantee mutually exclusive access for each critical section.

synchronize하는 것이다. 프로그래머가 강조하는 것이다. 이 critical section은 다른 thread와 공유될 수 있기 때문에 이 critical section에 있는 instruction들은 interleaving이 되지 않도록 동기화하는 것이다. 그래서 mutually exclusive access를 보장해주는 것을 synchronize 하는 것이다.

• Classic solution:
  • Semaphores (Edsger Dijkstra)

가장 많이 사용하는 것이 세마포어이다.

• Other approaches (out of our scope)
  • Mutex and condition variables (Pthreads)
  • Monitors (Java)

4. Semaphores

• Semaphore: non-negative global integer synchronization variable. Manipulated by P and V operations.

세마포어는 항상 0보다 크거나 같은 global integer 변수값이다. 이것을 조작할 수 있는 operation은 P(wait, sleep)와 V(signal, wake up)이다.

세마포어는 사용자 입장에서는 그냥 변수값이지만 이값은 P,V로 값을 바꿀 수 있다.

• P(s)
  • If s is nonzero, then decrement s by 1 and return immediately.
    • Test and decrement operations occur atomically (indivisibly)
  • If s is zero, then suspend thread until s becomes nonzero and the thread is restarted by a V operation.
  • After restarting, the P operation decrements s and returns control to the caller.

P는 s라는 변수가 1이라면 우선 s값을 체크한다. 만약 0이 아니라면 값을 줄이고 return한다. 이 동작은 atomic하게 작동한다. 하드웨어적으로 support한다고 생각하면 좋다.

P(s)는 모든 스레드가 부를 수 있기 때문에 내가 보았을때 s가 0일 수 있다. 그럼 P를 호출한 함수는 suspend한다. 스레드가 이 cpu를 점유하지 못하고 잠자고 있게 된다. V라는 operation을 통해서 s라는 값을 증가시켜 주기전까지 계속 잠자고 있는다.

그래서 깨어난 다음에는 P함수를 통해서 s값을 줄이고 caller에게 제어권을 돌려준다.

• V(s):
  • Increment s by 1.
    • Increment operation occurs atomically
  • If there are any threads blocked in a P operation waiting for s to become non- zero, then restart exactly one of those threads, which then completes its P
    operation by decrementing s.

s값을 증가시킨다.(atomic 하게 실행) 만약 P operation에서 block 된 스레드가 있다면 그 중에 한명을 깨우고 P operation을 실행해서 s를 dec한다.

• Semaphore invariant: (s >= 0)

C Semaphore Operations

sem_init : sem_t를 val로 초기화한다.
sem_wait, sem_post를 사용해서 스레드를 suspend하고 깨우면 된다.
csapp.h에는 P,V도 존재한다.

badcnt.c: Improper Synchronization

앞에 있었던 코드인데 문제를 어떻게 고칠거인가? thread 함수의 cnt++ 부분을 세마포어로 묶어주면 된다.

Using Semaphores for Mutual Exclusion

• Basic idea:
  • Associate a unique semaphore mutex, initially 1, with each shared variable (or related set of shared variables).
  • Surround corresponding critical sections with P(mutex) and V(mutex) operations.

기본적인 아이디어는 세마포어를 사용하되(mutex) 1로 초기화한다.

크리티컬 섹션에 해당하는 부분을 P,V로 묶어준다. Critical Section에 들어가기 전에 acquire lock하고 나와서 release lock한다.

• Terminology:
  • Binary semaphore: semaphore whose value is always 0 or 1
  • Mutex: binary semaphore used for mutual exclusion
    • P operation: “locking” the mutex
    • V operation: “unlocking” or “releasing” the mutex
    • “Holding” a mutex: locked and not yet unlocked.
  • Counting semaphore: used as a counter for set of available resources.

세마포어 값이 0 또는 1이 될때 Binary semaphore라고 한다.

mutual exclusion을 구현하기 위해 세마포어를 사용하는데 binary 세마포어를 사용하면 MUTEX라고 부른다. 그래서 P는 lock이고 V는 unlock한다고 한다. 뮤택스를 holding하고 있단는 것을 lock을 아직 풀어주지 않은 상황이다.

세마포어를 가지고 0또는 1이 아니고 여러개의 값을 가지고 있다면 Counting semaphore라고 부른다.

goodcnt.c: Proper Synchronization

• Define and initialize a mutex for the shared variable cnt:
  

처음에는 mutex를 선언하고 1로 초기화한다.

• Surround critical section with P and V:
  

들어갈때 뮤택스락을 걸고 나올때 풀어준다. 그래서 항상 결과는 불변하다.

Why Mutexes Work

Provide mutually exclusive access to shared variable by surrounding critical section with P and V operations on semaphore s (initially set to 1)

Semaphore invariant creates a forbidden regionthat encloses unsafe region and that cannot be entered by any trajectory.

뮤택스를 쓰게 되면 크리티컬 섹션으로 묶여져있는 공유변수, 자료구조는 mutualy exclusive하게 사용된다.
그래서 unsafe 공간을 무조건 피해가게 하는 장치가 된다.

Summary

• Programmers need a clear model of how variables are shared by threads.
• Variables shared by multiple threads must be protected to ensure mutually exclusive access.
• Semaphores are a fundamental mechanism for enforcing mutual exclusion.

어떤 변수가 공유되는지 알아야 하고 이게 mutually exclusive하게 되도록 해야 한다.