An Introduction
각 프로세스마다 virtual memory를 주고 address space라는 개념을 이용해 하나의 physical CPU를 여러 개의 virtual CPU처럼 사용할 수 있었다.
앞으로 thread를 다룰 것이다. multi-threaded program은 PC register가 여러 개고, 같은 address space를 공유하며 같은 데이터에 접근할 수 있다.
하나의 스레드는 프로세스와 유사하다. 스레드는 자기 고유의 PC와 register를 가지고 있다.
한 프로세스에 두 개의 스레드가 있다면 TCB(Thread Control Block)을 이용해 T1에서 T2로 context switching한다. (TCB에 state와 context가 있다.)
context switch에서 스레드는 address space가 그대로 남아있다는 점이 프로세스와 다르다.(i.e., there is no need to switch which page table we are using)
또 아래 그림처럼 stack도 다르다.
- Single-Threaded And Multi-Threaded Address Spaces
오른쪽 그림처럼 thread 개수만큼 address space에 stack이 추가로 필요하다.
변수, 인자, return 값 등 스레드를 위해 할당된 스택을 thread-local storage라고 한다.
(fork는 process를 생성해서 별도의 STACK, DATA, HEAP, CODE, PCB, FD table 등을 가지지만, thread는 TCB와 STACK을 제외한 나머지를 공유한다.)
An Example: Thread Creation
Code: Simple Thread Creation Code (t0.c)
#include <stdio.h> #include <assert.h> #include <pthread.h> void* mythread(void* arg) { printf("s\n", (char *) arg); return NULL;") } int main(int argc, char *argv[]) { pthread_t p1, p2; int rc; printf("main: begin\n"); rc = pthread_create(&p1, NULL, mythread, "A"); assert(rc == 0); rc = pthread_create(&p2, NULL, mythread, "B"); assert(rc == 0); // join waits for the threads to finish rc = pthread_join(p1, NULL); assert(rc == 0); rc = pthread_join(p2, NULL); assert(rc == 0); printf("main: end\n"); return 0; }
위 코드는 여러가지 경우로 실행될 수 있다.
Thread Trace (1)
T1 생성 → T2 생성 → waits for T1 → T1 실행 → T1 종료 → waits for T2 → T2 실행 → T2 종료 → main 실행
main()은 Run 상태이다가 "
waits for T1"에서Blocked된다.T1은 생성되자마자 Ready였다가 T1 실행부터 Run이 된다.
T1이 끝나면 main은 block에서
Ready로 바뀌고, 이후 바로 run해서 "waits for T2"를 실행한 뒤Blcok된다.T2는 생성되자마나 Ready였다가 T2 실행부터 Run.
T2가 끝나면 main은
Block→Ready→Run상태가 된다.
Thread Trace (2)
T1과 T2는 생성 직후 Ready였다가 실행되면 Run으로 바뀐다.
main()은 T1이 실행될 때 Run → Ready, T1이 끝나면 Ready → Run이 된다.
이후 T2가 실행될 때 Run → Ready, T2가 끝나면 Ready → Run이 된다.
T2 return 이후 "
waits for T1"으로 돌아올 때 main은 blocked 되지 않고,Ready→Run이 된다."waits for T2"를 수행할 때도 마찬가지로
계속 Run상태를 유지한다.
Thread Trace (3)
main → T2 실행 → T2 return → waits for T1 → T1 실행 동안 main은 Run →
Ready→Run→Blocked상태로 변화 한다.T1이 끝나고 return 하면 main은
Blocked→Ready→Run으로 변화한다.이후 waits for T2를 호출할 때는 그냥
Run상태를 유지한다.
이 세가지 상황 외에도 다른 방법으로 실행될 수 있다.
Why It Gets Worse: Shared Data
아래 코드를 살펴보자.
- Sharing Data: Uh Oh (t1.c)
#include <stdio.h>
#include <pthread.h>
#include "mythreads.h"
static volatile int counter = 0;
// Simply adds 1 to counter repeatedly, in a loop
// No, this is not how you would add 10,000,000 to
// a counter, but it shows the problem nicely.
void * mythread(void *arg)
{
printf("%s: begin\n", (char *) arg);
int i;
for (i = 0; i < 1e7; i++) {
counter = counter + 1;
}
printf("%s: done\n", (char *) arg);
return NULL;
}
// Just launches two threads (pthread_create)
// and then waits for them (pthread_join)
int main(int argc, char *argv[])
{
pthread_t p1, p2;
printf("main: begin (counter = %d)\n", counter);
Pthread_create(&p1, NULL, mythread, "A");
Pthread_create(&p2, NULL, mythread, "B");
// join waits for the threads to finish
Pthread_join(p1, NULL);
Pthread_join(p2, NULL);
printf("main: done with both (counter = %d)\n", counter);
return 0;
}main() 함수는 위와 같고, mythread()에서 for loop을 돌면서 전역 변수 counter를 1씩 증가시킨다.
T1과 T2가 같이 counter를 1천만씩 증가시키므로 2천만이 되길 기대할 수 있지만, 실제로는 그렇지 않다.
- t1.c output
$ gcc -o main main.c -Wall -pthread
$ ./main
main: begin (counter = 0)
A: begin
B: begin
A: done
B: done
main: done with both (counter = 20000000)게다가 결과가 매번 달라진다.(undeterministic)
The Heart Of The Problem: Uncontrolled Scheduling
count를 증가시키는 state는 여러 어셈블리의 instuction들로 나눌 수 있다.
// counter = counter + 1;
100 mov 0x8049a1c, %eax
105 add $0x1, %eax
108 mov %eax, 0x8049a1c실제로는 LD, ADD, ST를 순서대로 실행하면서 counter에 1을 더한다.
T1과 T2는 자신의 TCB에 eax와 같은 고유한 register들을 가지고 있다.
counter가 50인 상태에서 위 instruction들을 수행한다고 가정해보자.
- The Problem: Up Close and Personal
T1이 50을 가져와 1을 더해서 51로 만들고 ST 하기 전에 interrupt가 발생했다고 가정하자.(T1의 PC는 108을 저장)
그러면 T1 → T2로 context switch가 일어나고 T2가 instruction들을 실행한다.(T2의 PC는 100부터 시작)
T2도 저장된 counter(= 50)을 LD 해서 ADD 한 뒤, ST까지 했다고 하자.(T2의 PC는 113을 저장)
이때 interrupt가 발생해서 T2 → T1으로 실행 흐름이 넘어가고 아까 저장해둔 PC(108)와 eax(51)를 가져온다.
이후 T1의 PC가 가리키던 108을 수행하면 51을 shared data인 counter에 쓴다.
위 instruction들이 두 번 실행되었지만 counter는 1만 증가해 51이다.
이런 상황을 race condition이라고 한다. 연산은 deterministic하지만 결과는 indeterminate하다
이렇게 shared variable에 접근하는 코드(instruction 3개)를 critical section이라고 한다.
이런 문제를 막기 위한 mutual exclusion code를 원한다.
- A
critical sectionis a piece of code that accesses a share resource, usually a variable or data structure.(공유 자원을 사용하는 코드 조각)
- A
race conditionarises if multiple threads of execution enter the critical section at roughly the same time; both attempt to update the shared data structure, leading to a surprising (and perhaps undesirable) outcome.(여러 개의 스레드가 같은 critical section에 접근해서 비결정적인 결과를 가져오는 현상.)
- An
indeterminate program consists of one or more race conditions; the output of the program varies from run to run, depending on which threads ran when. The outcome is thus not deterministic, something we usually expect from computer systems.
- To avoid these problems, threads should use some kind of
mutual exclusionprimitives; doing so guarantees that only a single thread ever enters a critical section, thus avoiding races, and resulting in deterministic program outputs.(한 순간에 한 thread만 critical section을 실행할 수 있도록 하는 것)
The Wish For Atomicity
위 세 instruction을 하나로 합치면 어떨까?
아래와 같은 명령어가 있다면 HW가 atomic한 수행을 보장해서, 위와 같은 문제가 발생하지 않을 것이다.
memory-add 0x8049a1c, $0x1또는 세 instruction을 atomic하게 수행할 수 있다면 좋겠다.
synchronization primitives라는 set을 HW에 요청하는 것도 좋은 방법이다.
One More Problem: Waiting For Another
이런 상황에 I/O 요청까지 있다면 어떨까?
다음장에서는 synchronization primitives 뿐만 아니라 sleeping/waking interaction도 다루기 위해 condition variables을 이용할 것이다.
Interlude: Thread API
Thread Creation
- pthread_create() 인자
#include <pthread.h>
int pthread_create(
pthread_t * thread,
const pthread_attr_t * attr,
void * (*start_routine)(void*),
void * arg
);thread: pthread_t type의 포인터. pthread create()의 인자로 전달해 줌
attr: 스레드의 속성. 보통 NULL 전달
start_routine: 함수 포인터. 스레드가 실행할 함수의 주소
arg: start_routine 함수의 인자
#include <pthread.h>
typedef struct __myarg_t {
int a;
int b;
} myarg_t;
void *mythread(void *arg) {
myarg_t *m = (myarg_t *) arg;
printf("%d %d\n", m->a, m->b);
return NULL;
}
int main(int argc, char *argv[]) {
pthread_t p;
int rc;
myarg_t args;
args.a = 10;
args.b = 20;
rc = pthread_create(&p, NULL, mythread, &args);
...
}- Waiting for Thread Completion
#include <stdio.h>
#include <pthread.h>
#include <assert.h>
#include <stdlib.h>
typedef struct __myarg_t {
int a;
int b;
} myarg_t;
typedef struct __myret_t {
int x;
int y;
} myret_t;
void *mythread(void *arg) {
myarg_t *m = (myarg_t *) arg;
printf("%d %d\n", m->a, m->b);
myret_t *r = Malloc(sizeof(myret_t));
r->x = 1;
r->y = 2;
return (void *) r;
}
int main(int argc, char *argv[])
{
int rc;
pthread_t p;
myret_t *m;
myarg_t args;
args.a = 10;
args.b = 20;
Pthread_create(&p, NULL, mythread, &args);
Pthread_join(p, (void **) &m); // return myret_t
printf("returned %d %d\n", m->x, m->y);
return 0;
}main() 함수에서 myarg_t 구조체 args를 선언하고 Pthread_create() 함수의 인자로 전달한다.
또 Pthread_join() 함수를 이용해 return할 수 있고, 위 코드에서myret_t을 이용한다.
Uploaded by Notion2Tistory v1.1.0