Process는 운영체제에서 자원을 독립적으로 할당받아 실행되는 프로그램의 단위이며, 각 프로세스는 고유의 주소 공간을 가진다. 반면,Thread는 하나의 프로세스 내에서 실행되는 작업 단위로, 같은 주소 공간(코드, 데이터, 힙)을 공유하면서 개별적인 스택을 가진다. 이 때문에 스레드는 경량화된 병렬 실행이 가능하지만, 자원 공유로 인해 동기화 문제가 발생하기 쉬우며, race condition이나 데드락 방지를 위한 설계가 필요하다.
struct thread
struct thread;
모든 struct thread는 각자의 메모리 페이지의 시작 부분을 차지한다. 페이지의 나머지는 페이지의 끝쪽에서 부터 아래쪽으로 성장하는 thread의 스택을 위해 사용된다.
struct thread는 너무 크게 성장하도록 허용되면 안 된다.
kernel stack을 위한 공간도 부족해진다.
1KB 이하 정도로 하면 된다.
커널 스택 역시 너무 크게 성장하도록 허용되면 안된다.
스택 오버플로우 시 thread 상태가 망가진다.
커널 함수들은 non-static 지역 변수로서 큰 구조체나 배열을 할당하면 안 된다.
대신malloc()이나palloc_get_page()으로 동적 할당해야 한다.
tid_t tid;
모든 Threads는 각각 서로 다른 thread identifier(tid)를 가진다.
tid_t는 기본적으로int로typedef되어있고, 새로운 thread는 더 큰 수의 tid를 받는다.
프로세스 초기에는 1부터 시작한다.
enum thread_status status;
THREAD_RUNNING: 한 번에 정확히 하나의 쓰레드만 실행되어야 한다.thread_current()는 실행중인 thread를 리턴한다.
THREAD_READY: 준비 상태의 threads는ready_list라는 이중 연결 리스트로 관리되고, 스케줄러에 의해 그 중에 하나가 다음에 실행되도록 선택될 수 있다.
THREAD_BLOCKED: lock이나 인터럽션 등을 위해 기다리고 있다.thread_unblock()을 호출해서THREAD_READY상태가 되기 전까지는 스케쥴되지 않는다. 하단에 설명되는 Pintos synchronization 프리미티브에 의해 자동으로 block/unblock할 수 있다.
THREAD_DYING: 다른 thread로 전환 후 스케줄러에 의해 파괴된다.
char name[16]; // thread 이름
struct intr_frame tf; // 레지스터, 스택 포인터 등 context switching 정보 저장
int priority;
PRI_MIN(0) ~PRI_MAX(63)의 범위를 가지는 thread 우선순위 값
높은 숫자를 가질수록 우선순위가 높다.
제공되는 pintos는 thread 우선순위를 무시하지만, 이번 프로젝트에서 구현은 해야 한다.
struct list_elem elem;
list element: thread를 두 가지 이중 연결 리스트 중 하나에 넣기 위해 사용하는 구조체
ready_list: 실행될 준비가 된 ready 상태의 threads의 리스트
sema_down(): 세마포어에서 대기중인 threads의 리스트
waiting on semaphore와 ready는 한 thread에서 양립할 수 없는 상태이기 때문에 위 두 가지 역할을 할 수 있다.
uint64_t *pml4; // 다음 프로젝트 이후에 사용됨
unsigned magic
임의의 수인THREAD_MAGIC으로 세트되어 스택 오버플로우를 감지하는데 사용됨
thread_current()는 실행 중인 thread의struct thread의magic이THREAD_MAGIC으로 세트되었는지 확인한다.
스택 오버플로우가 발생하면 이 값이 바뀌는 경향이 있다.
struct thread의 맨 뒤에 만들면 편하다.
Thread Functions
void thread_init (void);
thread 시스템을 초기화하기 위해main()에 의해 호출된다.
Pintos의 초기 thread의struct thread를 생성한다.
이 함수를 실행하기 전에는thread_current()는 실행 중인 thread의magic값이 부정확해서 실패할 것이다.
void thread_start (void);
스케줄러를 시작하기 위해main()에서 호출된다.
idle thread 생성: 다른 read하는 thread가 없을 때 스케쥴되는 thread
스케줄러가 timer interrupt의 리턴값을 사용하기 때문에 인터럽트도 가능하게 한다.
void thread_tick (void);
매 timer tick마다 timer interrupt에 의해 호출된다. thread 통계를 추적하고 타임 슬라이스가 만료될 때 스케줄러를 작동시킨다.
주어진 이름과 우선순위를 가진 새로운 thread를 생성하고 실행해서 그 tid를 리턴한다. thread는 func를 실행하고, 그 함수의 단일 매개 변수로 aux를 전달한다.
thread_create()는 thread의struct thread와 스택을 위해 페이지를 할당하고 그 멤버를 초기화하고, 가짜 스택 프레임 집합을 설정한다. Thread는 blocked 상태로 초기화되며, 그 새로운 thread가 스케쥴되기를 허용하는 return 직전에 unblocked된다.
void thread_func (void *aux);
thread_create()에서 전달되는 함수의 종류다. 매개 변수 aux도 역시 전달받는다.
void thread_block (void);
Blocked 상태인 thread를 실행 상태로 재개하기 위해 ready 상태로 전환한다.
thread가 기다리는 lock이 사용 가능해 질 때 등의 상황에서 호출된다.
struct thread *thread_current (void);
실행 중인 thread를 리턴한다.
tid_t thread_tid (void);
실행 중인 thread의 tid를 리턴한다.thread_current()->tid와 동일함
const char *thread_name (void);
실행 중인 thread의 이름을 리턴한다.thread_current()->name과 동일함
void thread_exit (void) NO_RETURN;
현재 thread에서 나온다. 리턴값 없음
void thread_yield (void);
CPU를 실행할 새 thread를 고르는 스케줄러에 양보한다.
새로운 thread는 현재 thread가 될 것이기 때문에, 이 함수가 이 thread를 어느 특정 길이의 시간동안 유지하는것에 의존하도록 할 수 없다.
int thread_get_priority (void);
void thread_set_priority (int new_priority);
int thread_get_nice (void);
void thread_set_nice (int new_nice);
int thread_get_recent_cpu (void);
int thread_get_load_avg (void);
동기화를 수행하는 가장 간단한 방법은 인터럽트를 비활성화하는 것이다. 즉, CPU가 인터럽트에 응답하지 않도록 일시적으로 막는 것이다. 인터럽트가 꺼져 있으면 다른 thread가 실행 중인 스레드를 선점하지 않는다.thread선점은 타이머 인터럽트에 의해 제어되기 때문이다. 인터럽트가 정상적으로 켜져 있으면, 실행 중인thread는 두 C 명령문 사이 또는 실행 중일 때 언제든지 다른thread에 의해 선점될 수 있다.
인터럽트 상태를 직접 설정할 필요는 거의 없다. 대부분의 경우 다음 섹션에 설명된 다른 동기화 기본 요소를 사용해야 한다. 인터럽트를 비활성화하는 주된 이유는 커널 thread를 외부 인터럽트 핸들러와 동기화하기 위한 것이다. 외부 인터럽트 핸들러는 sleep 모드에 들어갈 수 없으므로 대부분의 다른 동기화 방식을 사용할 수 없다.
일부 외부 인터럽트는 (심지어 인터럽트 비활성화를 통해서도) 연기할 수 없다. non-maskable interrupts (NMIs)라고 불리는 이런 입터럽트들은 (컴퓨터에 불이 났다거나 등의) 긴급한 상황에서만 사용될 수 있다.
enum intr_level; // INTR_OFF (disabled) 또는 INTR_ON (enabled)
enum intr_level intr_get_level (void) // 현재 인터럽트 상태 리턴
enum intr_level intr_set_level (enum intr_level level); // 인터럽트 상태를 level로 바꾸고 이전 상태를 리턴
enum intr_level intr_enable (void); // 인터럽트를 on시키고 이전 상태 리턴
enum intr_level intr_disable (void); // 인터럽트를 off시키고 이전 상태 리턴
Semaphore
세마포어는 음이 아닌 정수와 그것을 자동으로 조작하는 두 가지 연산으로 이루어져있다.
Down (P) : 값이 양수가 될 때까지 기다렸다가 1 감소시킨다.
Up (V) : 값을 1 증가시킨다. (그리고 하나의 대기 중인 thread를 깨운다)
0으로 초기화된 세마포어는 정확히 한 번 발생할 이벤트를 대기하는 데 사용될 것이다.
thread A가 thread B를 시작하고 B로부터 어떤 활동을 끝냈다는 신호를 기다리고 있다고 가정하자.
A는 0으로 초기화된 세마포어를 만들어 B가 시작할 때 전달해 세마포어를 down시킬 수 있다.
B가 활동을 끝내면 세마포어를 up한다.
이는 A의 down이나 B의 up 중 어느 것이 먼저 일어나는지와는 상관없다.
struct semaphore sema;
/* Thread A */
void threadA (void) {
sema_down (&sema);
}
/* Thread B */
void threadB (void) {
sema_up (&sema);
}
/* main function */
void main (void) {
sema_init (&sema, 0);
thread_create ("threadA", PRI_MIN, threadA, NULL);
thread_create ("threadB", PRI_MIN, threadB, NULL);
}
이 예제에서 threadA는 threadB가 sema_up()을 호출할 때까지 sema_down()에서 실행을 멈춘다.
1로 초기화된 세마포어는 일반적으로 자원에 대한 접근을 제어하는 데 사용된다.
코드 블록이 자원을 쓰기 시작하기 전 세마포어를 down시키고, 그 자원을 사용을 다 했으면 그 리소스를 up한다.
struct semaphore;
void sema_init (struct semaphore *sema, unsigned value); // sema를 새로운 세마포어로 초기화
void sema_down (struct semaphore *sema); // sema에 down(P) 연산을 실행
bool sema_try_down (struct semaphore *sema); // 대기 없이 down 연산을 실행해 1 감소되면 true 반환
void sema_up (struct semaphore *sema); // sema에 up(V) 연산을 실행
Locks
Lock은 1로 초기화된 세마포어와 같다. Lock의 up을 release, down을 acquire라고 부른다.
세마포어와 비교했을 때, Lock은 추가적인 제한을 가지는데, lock을 acquire한 thread(owner)만이 그것을 release할 수 있다. 이 제한이 문제가 되는 경우에는 그냥 세마포어를 쓰면 된다.
struct lock;
void lock_init (struct lock *lock); //lock을 새 록으로 초기화
void lock_acquire (struct lock *lock); // 현재 thread에서 lock을 acquire하고, 필요한 경우 현재 owner가 release하기를 기다림
bool lock_try_acquire (struct lock *lock); // 대기 없이 현재 thread에서 lock을 시도하고, 성공한 경우 true 리턴함
void lock_release (struct lock *lock); // 현재 thread가 소유한 lock을 release함
bool lock_held_by_current_thread (const struct lock *lock); // 실행중인 thread가 lock을 가지고 있으면 true 리턴함
Monitors
Monitor는 세마포어나 lock보다 더 높은 레벨의 동기화 폼이다. Monitor는 동기화된 데이터 + monitor lock + 하나 이상의 조건 변수로 구성된다.
보호된 데이터에 접근하기 전에, 먼저 thread는 monitor lock을 acquire한다. 이 상태를 모니터 안에 있다in the monitor고 한다.
모니터 안에 있는 동안 thread는 모든 보호된 데이터에 읽고 쓸 수 있도록 컨트롤을 가진다.
보호된 데이터에 대한 접근이 완료되면 monitor lock을 release한다.
조건 변수는 모니터 안에 있는 코드가 어떤 조건이 true가 될 때까지 기다리도록 한다. 이 때 그 코드는 조건과 연관된 조건 변수(lock을 release하고 조건이 signal되기를 기다림)를 기다린다. 반대로 조건들 중 하나가 참이 된 경우에는, 그 조건이 그것을 기다리는 것 하나를 깨우도록 신호를 보내거나 아니면 전부를 깨우도록 브로드캐스트하게 할 수 있다.
struct condition;
void cond_init (struct condition *cond); // cond를 새 조건 변수로 초기화
void cond_wait (struct condition *cond, struct lock *lock);
// monitor lock을 release하고 cond가 다른 코드에 의해 signal되기를 기다림
// cond가 signal된 후에 리턴하기 전에 다시 acquire함
// 일반적으로 cond_wait의 호출자는 대기 상태가 끝난 후 condition을 다시 확인해야함
void cond_signal (struct condition *cond, struct lock *lock); // cond를 기다리는 threads 중 하나를 깨움
void cond_broadcast (struct condition *cond, struct lock *lock); // cond를 기다리는 모든 threads를 깨움
/* Monitor Example */
char buf[BUF_SIZE]; /* Buffer. */
size_t n = 0; /* 0 <= n <= BUF SIZE: # of characters in buffer. */
size_t head = 0; /* buf index of next char to write (mod BUF SIZE). */
size_t tail = 0; /* buf index of next char to read (mod BUF SIZE). */
struct lock lock; /* Monitor lock. */
struct condition not_empty; /* Signaled when the buffer is not empty. */
struct condition not_full; /* Signaled when the buffer is not full. */
...initialize the locks and condition variables...
void put (char ch) {
lock_acquire (&lock);
while (n == BUF_SIZE) /* Can't add to buf as long as it's full. */
cond_wait (¬_full, &lock);
buf[head++ % BUF_SIZE] = ch; /* Add ch to buf. */
n++;
cond_signal (¬_empty, &lock); /* buf can't be empty anymore. */
lock_release (&lock);
}
char get (void) {
char ch;
lock_acquire (&lock);
while (n == 0) /* Can't read buf as long as it's empty. */
cond_wait (¬_empty, &lock);
ch = buf[tail++ % BUF_SIZE]; /* Get ch from buf. */
n--;
cond_signal (¬_full, &lock); /* buf can't be full anymore. */
lock_release (&lock);
}
Optimization Barriers
최적화 배리어는 컴파일러가 배리어를 가로지는 메모리의 상태를 추정하지 못하게 막는 특별한 구문이다. 이는 컴파일러가 멋대로 처리 순서를 바꾸거나 최적화하는 실수를 하지 못하도록 막는 기능을 한다.(참고)
/* Wait for a timer tick. */
int64_t start = ticks;
while (ticks == start)
barrier();
