Pintos Project1. Threads

include/threads/synch.h

핀토스에는 이미 threads 시스템의 기본 기능은 구현이 되어있음.

과제에서는 이를 확장시켜 크게 세 가지를 추가 구현하는 것

 

- threads 디렉토리(compile in here)/ devices 디렉토리에서 working

 

Background Concepts

1. Thread

process 내에서 작업을 수행하는 단위. process내에서 여러개의 thread가 존재하며. 동시에 실행된다.

thread들은 process와 다르게 임의의 메모리 공간을 공유한다.

sturct thread; //declared in threads/thread.h

- thread or user process를 나타낸다.

 

                      4 kB +---------------------------------+
                           |         kernel stack            |
                           |               |                 |
                           |               |                 |
                           |               V                 |
                           |        grows downward           |
                           |                                 |
                           |                                 |
                           |                                 |
                           |                                 |
                           |                                 |
                           |                                 |
                           |                                 |
                           |                                 |
    sizeof (struct thread) +---------------------------------+
                           |             magic               |
                           |          intr_frame             |
                           |               :                 |
                           |               :                 |
                           |             status              |
                           |              tid                |
                      0 kB +---------------------------------+

- 구조상 thread의 사이즈는 제한되어 있는데(under 1KB), thread가 너무 크면 stack 공간이 부족하기 때문.

- 반대의 경우도 마찬가지. stack size가 너무 크다면 thread를 corrupt할 것

- 그러므로 kernel function들은 array나 non-static local variable을 사용하지 않는 것이 좋다.

 

2. Syncronization

Thread간의 메모리 공유로 인해, shared resources 관리가 매우 중요하다.

원하는 순서로 thread를 실행하기 위해서 Syncronization을 한다.

 

2-1.Disabling Interrupts

Timer, I/O, Hardware interrupt(고장이나 명령어 오류 등) 등의 이유로 CPU에 발생하는 예외.

include/threads/interrupt.h

-thread preemption이 보통 timer interrupt로 일어나기 때문에 아예 막아버리면 다른 thread가 preemption할 수 없음.

* non-maskable-interrupts(NMIs)도 존재하지만 핀토스에서는 고려가 필요 없음. 다만, interrupt를 비활성화 하면

특정 신호들을 감지할 수 없기 때문에 주의해야한다.

 

2-2. Semaphore

Nonnegative integer that two threads can manipulate. initial value는 0 or positive value.

//example code. include/threads/synch.h

struct semaphore sema;

/* Thread A */
void threadA (void) {
    sema_down (&sema); // b가 up하길 waiting한다.
}

/* 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);
}

 

- Down(P) 값이 양수가 되길 기다렸다가 decrement한다.

- Up(V) 값을 increment한다. waiting하는 thread가 존재한다면 wake up됨 

*Down 과 Up은 atomic operation이어야 하기 때문에 Interrupt가 disable되어야 함.

*Up 이후 Preempt(thread_yield)가 수행되는 데, 이 때 Interrupt handler가 Up을 호출할 수 있음

  --> 과제 2를 시작했을 때 에러의 원인이 되었던 녀석. Gitbook 혹은 핀토스 document를 보면, 다른 sync primitives와는 다르게 sema_up은 external interrupt handler 내에서도 실행될 수 있다. 따라서 sema_up 에서 external interrupt handling 여부를 체크해주어야 한다.

 

 https://web.stanford.edu/class/cs140/projects/pintos/pintos_6.html#SEC110 

 

 

2-3. Locks(Mutex)

semaphore와 비슷. Binary mutex라고도 한다. initialized with 1

include/threads/synch.h
struct lock;

 

- Down: release , Up: acquire 라고 부른다.

- Lock을 가진 사람을 Owner라고 하고, owner만 release가능하다.

 

* pintos의 lock은 recursive하지 않다. 즉, owner가 또 acquire하는 것은 에러임

* 이 프로젝트에서는 Semaphore의 ownership을 위해 사용한다 (아뭔모)

 

-- Semaphore 와 Lock의 차이?

1. 공유 자원에 접근 가능한 요소의 개수. Lock의 경우 1개의 스레드(프로세스)만이 공유 자원에 접근할 수 있지만, semaphore는 여러개도 가능하다.

2. 세마포어는 보통 커널 단위로 관리되어 공유 자원을 사용중이지 않은 스레드 혹은 프로세스도 해제가 가능하지만, lock의 경우 공유자원을 가진 사람만 해제 가능하다.

 

2-4. Monitors

더 고차원적인 방법. Signal을 이용한다

Data being syncronized / Lock / Condition variables 로 구성되어 있음 

include/threads/synch.h

1. Thread가 monitor lock을 acquire. (in the monitor라고도 함)

2. In the monitor, thread는 보호되는 데이터에 control을 갖게 됨

3. 데이터 접근이 끝났으면 lock을 release한다. 

 

- 모니터에서 cond variable들은 여러 상태들과 연관이 되어있으며, 특정 상태 변수를 wait할 수 있다.

(lock을 release하고 특정 상태 신호를 기다림. -> true가 되면 wake up)

* 이 프로젝트에서는 Cond라는 test에서 사용됨

    //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 (&not_full, &lock);
      buf[head++ % BUF_SIZE] = ch;    /* Add ch to buf. */
      n++;
      cond_signal (&not_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 (&not_empty, &lock);
      ch = buf[tail++ % BUF_SIZE];    /* Get ch from buf. */
      n--;
      cond_signal (&not_full, &lock);    /* buf can't be full anymore. */
      lock_release (&lock);
    }

 

2-5.Optimization Barriers

컴파일러 최적화를 막아준다. 즉, 컴파일러가 변수의 읽고쓰기를 reorder 할 수 없음. (단 local var은 예외)

데이터가 asynchronously하게 바뀔 수 있는 상황(다른 thread 혹은 interrupt handler에 의해)에 필요하다.

include/threads/synch.h

 

//example1- too_many_loops() in devices/timer.c
/* Wait for a timer tick. busy waiting*/
int64_t start = ticks;
while (ticks == start)
    barrier();

-example code1: 베리어가 없다면 컴파일러는 루프가 영원히 안바뀐다고 생각하고 최적화를 해버릴 것. 

//example2-busy_wait() in devices/timer.c
while (loops-- > 0)
      barrier ();

-example code2: 루프에 side effect가 없기 때문에 최적화 될 수 있음.

//sol 1
timer_put_char = 'x';
barrier ();
timer_do_put = true;

//sol 2 - reordering을 막진 않으나 interrupt를 막는다.
enum intr_level old_level = intr_disable ();
timer_put_char = 'x';
timer_do_put = true;
intr_set_level (old_level);

//sol 3- volatile 키워드 사용.(not good)

//not a sol - interrupt나 최적화 모두 안막음
lock_acquire (&timer_lock);        /* INCORRECT CODE */
timer_put_char = 'x';
timer_do_put = true;
lock_release (&timer_lock);

- example code3: timer interrupt가 발생할 때 마다, timer_do_put이 true일 경우 timer_put_char에 있는 char이 출력된다고 하자. 베리어가 없다면, 컴파일러가 statement들의 순서를 보장할 수 없다.

 

Implementation

 

1. Alarm Clock 구현

특정 시간이 지나면 OS가 스레드를 깨우는데, 이를 Alarm Clock이라 한다.

핀토스에 Busy waiting 방식으로 구현되어 있는 것을 reimplement해야한다.

void timer_sleep (int64_t ticks); //in devices/timer.c

/* Suspends execution for approximately TICKS timer ticks. */
void
timer_sleep (int64_t ticks) {
	int64_t start = timer_ticks ();

	ASSERT (intr_get_level () == INTR_ON);
	while (timer_elapsed (start) < ticks)
		thread_yield ();
}

 

thread 상태 변화 그림

thread_create() (timer_sleep() 넘긴다)-> thread 실행 -> 시간 확인 -> (지나지 않았을 경우) ready list에 넣는다 -> ready list에서 가장 우선인 것 실행 -> 반복한다.

 

Busy waiting이란?

특정 tick이 지날 때까지 while문을 돌면서 직접 지난 시간 값을 확인하는 방법을 말한다.

즉, thread를 직접 실행하여 tick의 값을 확인하므로, thread가 running state와 ready state를 반복하게 된다.

여기서 tick이란 핀토스 내부의 시간 단위로, 특정 시간 마다 1씩 증가한다. (timer.h에서 설정 가능)

 

구현 방법

sleep thread를 넣는 sleep list를 따로 만들어 관리하여, sleep 상태에 있는 thread는 실행되지 않도록 한다.

1. sleep thread를 sleep list에 넣고, 상태를 block state로 만들어 준다.

2. sleep list를 돌면서 시간이 지난 스레드를 깨워주는 작업을 한다.

( 단, idle thread는 sleep 되면 안되는 것을 주의해야한다.)

 

결과

User ticks : user program 수행 시간

Kernel ticks : kernel thread 수행 시간

Idle ticks : idle thread 수행 시간

이전 busy waiting에서는 idle thread가 실행되지 않아서 마지막 값이 0이었는데 증가한 것을 볼 수 있다.

 

2.Priority scheduling 구현

thread에는 priority라는 정보가 있어서, 우선 순위에 따라 yield 되어야 한다.

//Sets the current thread's priority to new priority. 
If the current thread no longer has the highest priority, yields.
void thread_set_priority (int new_priority);

//Returns the current thread's priority. 
In the presence of priority donation, returns the higher (donated) priority.
int thread_get_priority (void);

 

PRI_MIN(0) ~ PRI_MAX(63)까지의 범위를 가지며 높을 수록 높은 우선순위를 가진다.

thread_create 할때 인자로 전달된다. (threads/thread.h 에 PRI_ 매크로들이 정의되어 있음.)

 

Priority donation이란?

priority가 낮은 스레드가 lock을 점유하고 있을 경우, lock을 기다리는 thread보다 priority가 낮은 스레드가 우선 실행될 수 있다. 이런 상황을 막기 위해  높은 priority를 일시적으로 다른 스레드에 부여하는 것이다.

 

-Priority scheduling 구현 방법

현재 pintos는 priority에 상관 없이 ready_list 앞에서 pop하고 ,맨뒤에 push한다.

1. 새로 생성된 thread가 현재 thread보다 priority를 높게 가질 경우 먼저 실행되어야 한다.

따라서 thread_create() 함수를 수정한다.

2. thread_unblock(), thread_yield() 에서 ready_list에 넣는 방식을 수정한다. 

(이 과정에서 list_insert_ordered()함수를 사용, 이 때 priority를 비교하는 함수가 필요하다.)

 

-Syncronization 구현 방법

/* thread/synch.h */
struct semaphore 
  {
    unsigned value;             /* Current value. */
    struct list waiters;        /* List of waiting threads. */
  };
  
struct lock 
  {
    struct thread *holder;      /* Thread holding lock (for debugging). */
    struct semaphore semaphore; /* Binary semaphore controlling access. */
  };
  
struct condition 
  {
    struct list waiters;        /* List of waiting threads. */
  };

현재 pintos는 sema를 대기하는 waiters 리스트가 FIFO로 구현되어 있다.

1. Sema_down 과 Sema_up 에서 waiters list를 변경하므로, 이 함수들에서 변경시 priority에 따라 정렬하도록 코드를 수정한다.

2. Conditional variable에서 waiters list를 변경하므로, 이 함수들에서 변경시 priority에 따라 정렬하도록 코드를 수정한다.

 

- Priority Donation 구현 방법.

 추후 작성한다.( 플메가 짰음 ^__^)

 

3. Advanced scheduler 구현 

핀토스 도큐먼트의 4.4BSD scheduler 와 비슷한 multi-level feedback queue scheduler 를 구현해라.

1. priority로 구분된 여러개의 ready queue가 있다. (각 queue에선 round-robin 방식을 사용한다.)

2. priority 값은 고정된 게 아닌, 특정 시간 단위 혹은 필요에 따라 조절된다. (즉, 실시간임.)

2번 특징에 의해 이 part에서는 priority donation을 사용하지 않는다.

 

why ? 1. thread들의 different scheduling needs를 충족시키기 위해서

- I/O bound한 thread들은 빠른 response time을 필요로 하나 cpu time은 거의 필요 없다.

- compute-bound한 thread들은 a lot of CPU time을 필요로 하나, 빠른 response는 필요 없다.

 

2. 현재 priority에만 의존하는 스레드 방식은 매우 큰 문제점을 가지고 있다.

priority가 매우 낮은 스레드의 경우, 만약 donation을 받지 못한다면 우선 순위가 높은 스레드들에 CPU 점유를 밀려 반응 시간이 매우 느려질 수 있다. 이렇게 되면 모든 스레드의 평균 반응 시간 또한 매우 커질 것이다.

 

그렇다면 구현을 어떻게 할 것인가? 구현을 하기 전에 알아야 할 내용들을 먼저 살펴보자.

 

Concept 1. niceness

// in threads/thread.c
int thread_get_nice (void);
int thread_set_nice (int nice);

 

각 스레드가 다른 스레드에 양보를 하는 정도를 나타내는 수치이다. 

NICE_MIN(-20) ~ NICE_MAX(20) 

* 0일 경우 priority에 영향을 주지 않는다, inital thread는 0, 다른 스레드는 부모 스레드의 값을 상속받는다.

 

Concept 2. priority

priority = PRI_MAX - (recent_cpu / 4) - (nice * 2)

PRI_MIN(0) ~ PRI_MAX(63), PRI_DEFAULT(31)

이전 구현 방법과는 다르게 매 4ticks 마다 priority를 재계산 해야한다.

* recently cpu time을 받았던 스레드는 낮은 priority를 갖게 된다.(to avoid starvation) 

 

Concept 3. recent_cpu

int thread_get_recent_cpu (void);

recent_cpu = (2 * load_avg)/(2 * load_avg + 1) * recent_cpu + nice

RECENT_CPU_DEFAULT(0)

각 스레드가 최근에 CPU를 얼마나 사용했는지 나타내는 수치이다. *실수 값을 가진다.

- timer interrupt가 발생할 때마다 running thread의 경우 1씩 증가한다. idle 스레드는 제외시킨다.

- 1초마다 모든 스레드의 RC값이 (running, block, ready 상관 없이) 위의 공식을 사용하여 재 계산된다.

   이 때, 1초는 timer_ticks() % TIMER_FREQ ==0 으로 구분함.

- load_avg 값에 의해 rate of decay가 CPU를 사용하려는 스레드의 개수에 반비례 한다.

-만약 nice 값이 음수라면 RC값도 음수가 될 수 있음.

 

Concept 4. load_avg

int thread_get_load_avg (void)
//Returns 100 times the current system load average, rounded to the nearest integer.

load_avg = (59/60) * load_avg + (1/60) * ready_threads

LOAD_AVG_DEFAULT(0)

시스템의 평균적인 load, 즉 최근 1분동안의 ready thread(실행 가능한 스레드)의 개수를 나타낸다. *실수 값을 가진다.

- RC와 마찬가지로. exponentially weighted moving average

- priority나 recent_cpu와는 다르게 thread-specific하지 않다.

- 1초마다 위의 공식을 사용하여 재 계산된다.

   이 때, 1초는 timer_ticks() % TIMER_FREQ ==0 으로 구분함.

- 여기서의 ready_threads는 실행중이거나 준비 상태에 있는 스레드들을 의미함.

 

- Fixed_point arithmetic

load_avg와 recent_cpu는 실수 값을 가진다. 그러나 floatint point arithmetic의 경우 커널을 복잡하고 느리게 만들기 때문에 핀토스에선 지원하지 않는다. 따라서 정수를 사용하여 연산해야 한다.

여기서 17.14 fixed-point representation을 사용한다. ---> 1 sign bit | 17  bits | 14 fractional bits 

 

 

- 구현시 주의할 점

floating point연산시 float, int를 헷갈리지 않고 함수를 잘 쓰는 것이 중요하다. 또한 연산할 때 오버플로우가 날 수 있는 부분이 있으니 주의해서 연산합시당..

잘 짜놓고 이상한 부분에서 틀려서 test가 일부만 통과가 안됐다. 이런 경우 디버깅이 매우매우매우 어렵다는 것을 깨달았는데, 이럴 땐 gdb보다 테스트 파일에 printf를 써서 디버깅 하는 것도 도움이 되는 것 같다. 다음 과제 시작 전에 디버그 매크로를 만들어 놓는 것도 좋을 듯

 

- 핀토스 옵션들 관해서

-v: no VGA display or keyboard. 

-k: test 실패 혹은 user panic, or triple fault의 경우 몇 초후 pintos 를 kill한다.

-T: CPU time이 N만큼 지나거나, N*load_avg 초의 wall clock time이 지났을 때 pintos를 kill한다.

이러한 옵션들을 넣어주지 않으면 실행이 끝나도 qemu의 메모리가 남아서 제대로 종료되지 않는 것 같다.