Pintos Project 1: THREADS

Project 1 demonstration을 위해 플젝 1을 복습해보자.

 

Project 1의 과제는 세 가지: Alarm Clock, Priority Scheduling, Advanced Scheduler이다.

플젝1이 나머지랑 비교도 안되게 쉬운거였다니 ㅜㅜ

1. Alarm Clock

Alarm Clock 과제의 목적은 Busy Waiting 문제를 해결하는 것.

timer_sleep은 ticks 동안 해당 스레드를 잠재우는 역할을 한다.

가장 이상적인 방법은 잠든 스레드를 블락하고, 잠든 시간 동안 CPU를 주지 않는 것이다.

하지만 기존 코드에서는 스레드를 블락하지 않고 계속 CPU가 할당되며,

while문으로 시간을 체크하고 다시 yield하는 방식을 사용한다.

 

해결책: while문 대신 thread_sleep 함수로 block하자.

 

void thread_sleep (기상시각 ticks):

1. disable interrupt (커널 스레드와 외부 인터럽트 핸들러 동기화중이기 때문)-> 안하면 timer_sleep에서 assertion error

2. idle 스레드일 경우 나가라. idle 스레드는 sleep 하면 안됨;

   idle 스레드는 ready list에 아무 스레드가 없을 때 실행. idle 스레드가 sleep 하면 아무 스레드도 실행되지 않음

3. 언제 일어날 지(ticks) struct thread에 저장

4. sleep list에 insert; 이때, ticks 순서대로 insert. 가장 먼저 일어나야 하는게 앞에 오도록

5. thread_block()

6. interrupt 상태 복원

 

잠든 스레드는 언제 일어날까. 매 tick마다 실행되는 timer_interrupt 함수에서 thread_wakeup을 해주자.

 

void thread_wakeup(void):

반복문을 이용해 sleep list를 iterate.

각 t->ticks를 현 시각 timer_ticks()와 비교해 적을 경우 sleep_list에서 빼고 unblock

 

 

2. Priority Scheduling

말그대로 priority scheduling. ready list와 wait list(sema)를 정렬하자.

sema_down, cond_wait, thread_unblock, thread_yield: list_insert_ordered로 수정.

sema_up, cond_signal, thread_set_priority: list_sort 추가; priority가 바뀌었(을 수 있)기 때문

 

thread_preempt: 현재 스레드의 priority보다 높은 스레드가 있는지 확인

ready_list 가장 앞에 있는 스레드의 priority와 현재 priority를 비교

더 높을 경우 thread_yield

 

언제 preemption이 발생할까.

- thread_set_priority: priority가 바뀌는 경우... 쫓겨날 수도 있음

- sema_up: unblock된 함수가 priority 높을 수도 있으니까

- thread_create할 때도 현재 스레드의 priority와 비교해 yield함 

 

2-1. Priority Donation

2번 과제의 핵심인 priority donation. Multiple donation과 nested donation 주의.

 

1. 우선 struct thread에

- initial_priority: 원래 priority 저장해둘 곳

- donators list: 자기한테 donate 한 스레드의 리스트 (for multiple donation)

- lock_waiting: 자기가 waiting 하고 있는 lock (for nested donation)

추가하자.

 

2. lock_acquire

만약 lock에 이미 holder가 있는 경우, priority donation 진행.

우선 t->lock_waiting에 lock 저장 후 holder의 donators list에 t 추가.

holder의 priority가 더 낮을 경우, priority를 현 스레드의 priority로 바꿈(donation)

그 후 nested donation 진행; holder의 lock_waiting의 holder에게 donation, ... (while문으로 반복)

 

3. lock_release

donators list에서 해당 lock(지금 release 되는)을 기다리는 애들은 다 빼준다.

그 후 남은 애들 priority로 priority setting. (다 낮으면 initial priority로)

 

cf. thread_set_priority에서 바꾼 priority와 donated priority 비교 

 

3. Advanced Scheduler 

 

nice: 착하니까 양보할게...

recent_cpu: 얼마나 최근에, 많이 CPU를 썼는지

cf. load_avg: system-wise; global variable

priority = PRI_MAX - (recent_cpu / 4) - (nice * 2) -> 4 tick마다 계산.

 

// functions for advanced scheduler
void calculate_thread_priority(struct thread *t);
void calculate_load_avg(void);
void increase_recent_cpu(void);
void calculate_recent_cpu(struct thread *t);
void recalculate_thread_priorities(void);
void recalculate_recent_cpu(void);

 

* recent_cpu

- timer interrupt마다 running_thread의 recent_cpu 1 증가

- 1초마다 한 번씩 모든 스레드의 recent_cpu recalculate; -> all_list 필요! 

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

load_avg = moving avg of ready + running threads ; 시스템이 바쁜 정도 

load_avg가 클수록 decay -> 1, 작으면 decay -> 0 

recent와 load_avg는 1초에 한 번씩 계산

 

3-1. Fixed Point Arithmetic

priority, nice, ready_threads: int지만 recent_cpu, load_avg는 float. 어떻게 연산?

17.14 fixed-point number representation 사용; 32bit중 앞 17bit는 정수 부분, 14bit은 소수부분, 마지막은 sign bit

즉 x 는 이 representation에서 x / (2^14)로 interpret 됨.

이것만 알면 모든게 이해 된다. f = 2^14라고 했을 때

n to fp: n * f (14칸 왼쪽으로 shift)

x to int: x / f (14칸 오른쪽으로 shift) ...

cf. fp*fp 혹은 fp/fp 일 때는 overflow 고려해 (int64_t) 사용, f로 shift해줌