8. Threads and Race condition

Multi-processing vs. Multi-threading

Multi-processing

• 하나 이상의 task를 처리하기 위하여 각각의 독립적인 process들이 동시에 실행된다.(병렬처리!) 
• 각각의 process가 독립적인 메모리주소를 가져야할 때 사용된다.

장점

• 독립된 구조로 인한 안정성. 하나의 process가 죽어도 나머지 process에는 영향이 없다.

단점

• context-switching이 자주 일어나면, 그로 인한 overhead가 크다.
• process간의 통신이 필요한 경우, 그 방법이 어렵고 overhead가 크다.

Multi-threading

• 다수의 thread들이 하나의 process를 동시에 실행한다.
• 각각의 thread들은 서로 다른 process처럼 동작하지만 동일한 메모리 주소를 사용한다.(하나의 process)
• Thread간의 context switching은 PCB가 아님, Thread control block(TCB)을 이용한다.

장점

• 프로세스 할당에 따른 시스템 자원 감소
• 스레드 간의 통신이 비교적 쉽고, overhead가 적다.
• process간의 context switching보다 thread 간의 context switching의 overhead가 더 적어, context switching이 많이 일어나는 task에서 유리하다

단점

• memory address를 공유하는 점에서, race condition, dead lock과 같은 경우가 생길 수 있다. 섬세한 메모리 관리가 필요하다.
• 하나의 thread가 죽으면 나머지 thread에도 영향이 간다.
• 단일 process인 task의 경우 성능 효과를 보기 힘들다.(라고 적혀있는데 강의에서 다루었던 과제는 단일 process로 thread의 개수를 늘려 성능을 향상시키는 과제였다. 상황에 따라 다르지 않을까 싶다.)

Multi-Threaded Address Space Layout

multi-threaded address

• Multi-thread 환경에서는 각각의 thread는 독립된 stack을 갖는다.
• Thread들은 heap과 code의 address를 공유한다.

Hardware Threads vs. Softwate Threads

• Hardware thread : 각각의 CPU 코어에 실제로 존재하는 Thread이다.(ex. 1 core 2 thread) Thread는 이곳에서 실행된다. 제한된 수를 갖는다. 물리적인 core는 한개로 완전히 동시에 실행되는 것은 아니고, 하이퍼 스레딩을 통해 2개의 논리적인 core로 인식되는 것이다.
• Software thread : Hardware thread의 개수 제한에 구애받지 않고 얼마든지 만들어질 수 있다. 다만, 실행은 hardware thread에서 되기 때문에, 100개의 software thread가 존재해도 hardware thread가 4개라면, 100개의 thread들은 동시에 실행될 수 없고 4개씩 순차적으로 실행된다. 

Thread Creation & Completion (pthread)

#include <pthread.h> //thread에서 실행할 function void *func(void *arg){     //just return argument     return (void*) arg; } void main(){     //threads들의 array 와 threads id를 담을 unsigned array 선언 및 할당     phtread_t *threads = (pthread_t*)malloc(num_thread * sizeof(pthread_t));     unsigned *thread_id = (unsigned*)malloc(num_thread * sizeof(unsigned));          for(unsigned t = 0; t < num_thread; t++){         thread_id[t] = t;         //thread creation         assert(!pthread_create(&threads[t], NULL, &func, (void*)&thread_id[t]));     }     for(unsigned t = 0; t < num_thread; t++){         int *result         //thread completion         assert(!pthread_join(threads[t], (void**)%result));     } free(threads); free(thread_id); return0; }

간단한 pthread의 생성과 종료에 대한 c 코드이다.

pthread_create으로 thread가 생성되고,(미리 할당한 pthread struct에 생성한다.)

실행할 함수(func)와 attribute, 매개변수를 thread에 전해준다.

각 thread는 함수를 실행하고, pthread_join에서 함수에서의 return 값을 전달하며, pthread_join의 리턴값을 통해 thread에서의 작업 상황을 알 수 있게 된다.(정상적인 종료는 0 리턴, 그 외에는 에러코드 리턴)

Race Condition

• race condition이란, 코드의 실행 순서에 따라, 그 결과가 달라지는경우를 말한다.
  • Thread 내부에서의 code 실행은 program된 순서에 따라 실행됨으로, deterministic하다. 반면, thread 간의 실행 순서는, non-deterministic하다. 

Race condition example. 2개의 thread가 전역변수 count를 각각 1씩 1000회 더한다.
이때, CPU에서 count에 1을 더하기 위해 실행되는 instruction은 다음과 같다 ld     x2, 0(x8)     //count 값을 x2 레지스터로 가져온다.  addi  x2, x2, 1     //x2 레지스터의 값에 1을 더한다. sd     x2, 0(x8)    //x2 레지스터의 값을  count에 저장한다. (x8은 count의 주소값을 가지고 있다.)
OS	Thread #0	Thread #1	pc	x2	count
	ld     x2, 0(x8)		100	0	0
	addi  x2, x2, 1		104	1	0
Context switch from thread #0 to thread #1
		ld     x2, 0(x8)	100	0	0
		addi  x2, x2, 1	104	1	0
		sd     x2, 0(x8)	108	1	1
Context switch from thread #1 to thread #2
	sd     x2, 0(x8)		108	1	1

• 분명 thread #0 thread #1 모두 각각 count에 1을 더하기 위한 3개의 instruction을 수행하였지만, count는 1 밖에 더해지지 않았다. thread #0가 레지스터에서 더해놓은 값을 count에 다시 저장하기 전에 context switching이 일어나면서 결과가 제대로 나타나지 않은 것이다.
• Thread간의 context switching은 undeterministic하게 일어나고, 프로그래머는 thread들이 어떠한 순서대로 실행되는지 알 수 었다. Context switching 타이밍에 따라서 결과가 달라지는 위와 같은 경우를 race condition이라고 한다. 
• Thread들이 공통으로 사용하는 데이터를 다루는 부분을 critical section이라고 한다. 하나의 thread가 critical section을 실행하는 동안, 다른 thread들은 critical section을 실행하지 않아야한다. 위의 예시와 같은 경우에는, 
  ld     x2, 0(x8)
  addi  x2, x2, 1
  sd     x2, 0(x8)
  위 세개의 instruction들이 critical section이다. 이 세개의 instruction만 연속해서 실행된다면,(= 다른 스레드가 중간에 context switching되지 않는다면) 프로그램은 의도한대로 원하는 결과를 얻을 수 있다.

 How to solve race condition?

• Race condition을 해결하기 위한 첫번째 방법은, load-add-store이 합쳐진 atomic instruction을 사용하는 것이다. CISC instuction set을 사용한다면, atomic instruction을 사용할 수 있다.
• 두번째 방법은, 여러개의 thread 중 하나의 thread만이 critical section에 접근할 수 있게 해주는 synchronization primitives(동기화 요소(?))를 이용하는 것이다.

Dead Lock

• 멀티 프로세스 / 스레드 환경에서, 한정된 자원(ex. CPU)을 공유하는 상황에서, 다른 프로세스/스레드가 해당 자원을 사용하고 있다면, 새로 해당 자원을 요청한 프로세스 / 스레드는 해당 자원을 기다리면서 대기상태로 들어가게 된다.
• 이때, 프로세스 / 스레드가 대기 상태에서 실행 상태로 되돌아오지 못하게 된다면, dead lock이라고 부른다.
• Dead lock을 다음과 같은 네가지 조건이 만족되면 발생한다. 따라서 이 중 하나의 조건이라도 충족되지 않으면, dead lock을 막을 수 있다.
  • Mutual exclusion : 자원을 한번에 하나의 프로세스 / 스레드만이 이용할 수 있는 것. 여러 개의 프로세스 / 스레드가 동시에 자원을 공유한다면, dead lock은 발생하지 않는다. 하지만 위에서 보았듯이, race condition과 같은 이유로 mutual exclusion이 필요하다. 다음 장에 자세히 다룬다.
  • Hold and wait : 여러개의 자원을 사용하는 프로세스 / 스레드가 일부의 자원을 할당 받은채, 나머지 자원들을 할당 받기 위해 대기하는 것.
  • No preemption : 다른 프로세스 / 스레드가 사용중인 자원을 강제로 빼앗을 수 없는 것.
  • Circular wait : 프로세스 / 스레드 P0, P1, P2, ... Pn이 있을 때, P1은 P0가 갖고 있는 자원을 기다리고, P2는 P1이 갖고 있는 자원을 기다리고, ... Pn은 Pn-1이 갖고 있는 자원을 기다리고, Pn은 P0가 갖고 있는 자원을 기다리는, 꼬리에 꼬리를 물고 자원을 기다리고 있는 상황.

 

 

 

 

출처 - https://wooody92.github.io/os/%EB%A9%80%ED%8B%B0-%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4%EC%99%80-%EB%A9%80%ED%8B%B0-%EC%8A%A4%EB%A0%88%EB%93%9C/

멀티 프로세스(Multi Process)와 멀티 스레드(Multi Thread)

https://www.intel.co.kr/content/www/kr/ko/gaming/resources/hyper-threading.html

하이퍼 스레딩이란 무엇입니까? - 인텔

https://jwprogramming.tistory.com/12

Deadlock 개념이란? 그에 대한 해결책/회피책

https://namu.wiki/w/%EB%8D%B0%EB%93%9C%EB%9D%BD?from=Deadlock