Prethreaded Concurrent Server

2. Putting It All Together: Prethreaded

Prethreaded Concurrent Server

---

Worker thread routine:

---

echo_cnt initialization routine:

---

Worker thread service routine:

3. Crucial concept: Thread Safety

• Functions called from a thread must be thread-safe

스레드로부터 호출되는 함수들은 thread-safe해야 한다는 개념이다.

• Def: A function is thread-safe iff it will always produce correct results when called repeatedly from multiple concurrent threads

어떤 함수가 thread-safe하다는 것은 여러 concurrent thread로 부터 함수를 반복적으로 호출하더라도 항상 correct한 결과가 나온다.

• Classes of thread-unsafe functions:
  • Class 1: Functions that do not protect shared variables
  • Class 2: Functions that keep state across multiple invocations
  • Class 3: Functions that return a pointer to a static variable
  • Class 4: Functions that call thread-unsafe functions

스레드 unsafe 한 함수를 4단계로 나누었다.
class1 : shared variable을 protect 하지 않는 변수(공유변수를 같이 sharing할때 mutex lock으로 잡아주지 않는 경우)
class2 : 스레드들이 함수를 계속 호출하는데 호출할때마다 상태를 계속 기억해야 하는 함수들을 이야기 한다.
class3 : return value가 static variable이다. 그래서 스레드들이 static variable의 pointer을 반환하는 경우이다.
class4 : thread-unsafe 함수를 호출하는 경우이다.

Thread-Unsafe Functions (Class 1)

• Failing to protect shared variables
  • Fix: Use P and V semaphore operations
  • Example: goodcnt.c
  • Issue: Synchronization operations will slow down code

shared variable을 protect를 하지 않는 경우이다. P,V 뮤택스락으로 잡은거을 앞에서 볼 수 있었다.

Thread-Unsafe Functions (Class 2)

• Relying on persistent state across multiple function invocations
  • Example: Random number generator that relies on static state
    

두번째 class는 pseudo-random함수는 이 함수를 iteration을 돌면서 random number가 생성된다. pseudo-random함수가 게속 호출된다.
이 함수 invocation을 할때마다 state를 기록하지 않으면 문제가 생긴다. correct한 result가 나오지 않기 때문이다.

Thread-Safe Random Number Generator

• Pass state as part of argument
  • and, thereby, eliminate global state
    
• Consequence: programmer using rand_r must maintain seed

rand함수를 새롭게 만들어야 한다. nextp라는 past argument값을 넘기어준다. 그럼으로써 값을 계속 기억하게 하는 것이다.

Thread-Unsafe Functions (Class 3)

• Returning a pointer to a static variable

• Fix 1. Rewrite function so caller passes address of variable to store result

  • Requires changes in caller and callee

• Fix 2. Lock-and-copy

  • Requires simple changes in caller (and none in callee)
  • However, caller must free memory.
    

세번째는 static variable의 pointer을 반환하는 경우이다.
ctime이라는 함수는 time_t를 인자로 넘기어 준다. 반환값은 time과 date에 대한 정보를 반환한다.

ctime이라는 함수는 time_t의 변수값을 인자로 넘기어 주면 ctime함수에서 sharedp로 string으로 변환된 timep의 값의 주소값을 반환해준다.

timep는 global variable이기 때문에 다른 스레드가 ctime을 호출하면 그 사이에 공유된 메모리의 값이 변경될 수 있다. 그래서 ctime은 thread-unsafe한 함수이다.

첫번째는 ctime이라는 함수를 아예 바꾸는 방법이 존재한다. thread의 local stack variable의 주소값을 반환하는 방법이다. 하지만 조금 어려운 방법이다.

두번째 방법은 Lock-and-copy이다. ctime함수를 누구도 호출할 수 없게하는 것이다. 그래서 이 부분을 뮤택스락으로 잡아놓고 privatep에 값을 넘기어 주어서 copy를 하는 것이다.

왜 ctime은 thread-safe하게 만들지 않았는가? 당시에는 멀티스레딩 개념이 없어서 그렇게 안만들었다.

Thread-Unsafe Functions (Class 4)

• Calling thread-unsafe functions
  • Calling one thread-unsafe function makes the entire function that calls it thread-unsafe
  • Fix: Modify the function so it calls only thread-safe functions

네번째 class는 thread unsafe한 함수를 호출하는 경우를 이야기 한다.

4. Reentrant Functions

• Def: A function is reentrant iff it accesses no shared variables when called by multiple threads.
  • Important subset of thread-safe functions
    - Require no synchronization operations
    - Only way to make a Class 2 function thread-safe is to make it reetnrant (e.g., rand_r )
    

thread-safe한 함수중에 reentrant한 함수를 정의한다. 재진입이 가능하다 = 여러 스레드가 이 함수를 호출하는데 스레드간의 shared variable이 전혀 없는 것을 reentrant하다고 부른다.

Reentrant function과 같은 경우는 synchronize가 필요하지 않다. 왜냐하면 shield variable이 전혀없기 때문이다.

예를 들어 앞에서 rand_r 함수 같은 경우 nextp를 내가 가지고 있음으로 상태를 keep하고 global variable의 문제를 해결했다. rand_r은 reentrant한 함수이다.

이걸 제외한 모든 함수들은 unsafe하다.

Thread-Safe Library Functions

• All functions in the Standard C Library (at the back of your K&R text) are thread-safe
  • Examples: malloc, free, printf, scanf
• Most Unix system calls are thread-safe, with a few exceptions:
  

thread-safe한 Library가 존재한다. stdio.h에 있는 함수들은 모두 thread-safe하다. 하지만 예외적인 몇가지가 존재한다. 위에 보이는 함수들이 대표적인데 이외에도 몇가지 존재한다. 이들은 thread-safe하지 않다.

5. One worry: Races

• A race occurs when correctness of the program depends on one thread reaching point x before another thread reaches point y
  

어떤 스레드가 다른 스레드가 도달하기 전에 누가 언제 어떤 순서로 접근하는지에 따라서 순서를 보장할 수 없기 때문에 correctness를 보장할 수 없다. 이런경우를 보고 race가 발생한다고 이야기 한다.

결국 어떤 프로세스 안에 멀티프로세스를 했다면 그 안의 실행순서에 dependent한 경우 race가 발생했다고 이야기 한다.

위의 코드에서 i는 shield variable이다. Pthread_create에서 i의 주소를 넘기어서 스레드별로 i에 접근이 가능해진다. thread함수로 돌아와서 vargp를 myid에 복제한다.

그래서 결국에 모든 스레드의 id는 unique하게 화면에 출력하는 것을 기대한다. 하지만 레이스가 발생한다.

Race Illustration

• Race between increment of i in main thread and deref of vargp in peer thread:
  • If deref happens while i = 0, then OK
  • Otherwise, peer thread gets wrong id value

메인 스레드가 i = 0 일때는 peer thread 0을 만들고 main thread는 i=1로 바꾸어 놓았다. 그런데 스레드0 번에서 접근하려는 i와 main thread의 i가 동일하다. 결국 레이스가 발생하게 된다. 그럼 문제가 발생했다고 보게 된다.

Could this race really occur?

그래서 100개의 스레드를 만들고 각 스레드마다 i를 저장하는지 확인해보자. 정상적이면 중복되는 값이 없어야 한다.

• Race Test
  • If no race, then each thread would get different value of i
  • Set of saved values would consist of one copy each of 0
    through 99

Experimental Results

우리의 기대는 No Race상태처럼되는 것이다.
하지만 single core laptop에서 그렇지 않다.
또한 multicore에서는 더 심각해진다.

Race Elimination

이를 해결하기 위해 main thread에서 malloc을 해서 heap space을 사용하는 것이다. 그리고 ptr의 값을 넘기는 것이다.

6. Another worry: Deadlock

• Def: A process is deadlocked iff it is waiting for a condition that will never be true

Deadlock이 생기었다는 건 여러스레드가 이 프로그램을 실행하고 있는 것이다. 스레드가 조건을 만족못해서 진행못하는 경우이다.

• Typical Scenario
  • Processes 1 and 2 needs two resources (A and B) to proceed
  • Process 1 acquires A, waits for B
  • Process 2 acquires B, waits for A
  • Both will wait forever!

스레드 1이 B를 갖고 싶고 스레드 2는 A를 갖고 싶은 상황이 이어지는 것을 이야기 한다.

Deadlocking With Semaphores

위 코드에 따르면 스레드 0번은 세마포어 0번을 잡고 스레드 1번도 세마포어 1번을 잡은 상태이기에 스레드 0번이 1번을 잡아야 진행되는데 스레드 1번떄문에 도저히 진행할 수 없는 상황이 만들어져 있다.

Deadlock Visualized in Progress Graph

Locking introduces the potential for deadlock: waiting for a condition that will never be true

Any trajectory that enters the deadlock region will eventually reach the deadlock state, waiting for either s0 or s1 to become nonzero

Other trajectories luck out and skirt the deadlock region

Unfortunate fact: deadlock is often nondeterministic (race)

스레드0의 세마포어 0과 스레드1의 세마포어 1번을 차지하여 다른 스레드가 접근하면 안되는 상황이다. 하지만 위의 그래프를 보면 진행방향에 이미 deadlock이 있어서 접근이 불가능하게 된다.

즉 locking이 deadlock을 발생시킬 수 있다는 것이다.

Avoiding Deadlock

그래서 해결하는 방법이 thread의 P함수를 쓰는 부분의 순서만 바꾸었다.

Avoided Deadlock in Progress Graph

No way for trajectory to get stuck

Processes acquire locks in same order

Order in which locks released immaterial

결과적으로 위와 같이 생서되어 deadlock에 접근하지 않고 진행하게 된다.