Pintos Project #2 : Alarm Clock의 개선

1.     프로젝트 개요

• pintos 커널의 timer_sleep()함수를 개선한다.  

---

2.    문제의 정의

• devices/timer.c에 정의되어 있는 timer_sleep()함수는 기능적으로는 작동하지만, 현재 busy-waiting방식으로 구현되어 있다.
• Busy-waiting방식은 cpu 자원의 낭비를 초래한다. 

---

3.    문제의 분석

• timer_sleep()함수는 현재의 thread를 ticks 시간동안 잠재우는 함수이다. 
• 기존의 timer_sleep()함수는 다음과 같다. 

• while문을 살펴보면, scheduling에 의해 자신의 순서가 될 때마다 이 while문이 실행되고 timer_elapsed(start)를 호출한다.
• Timer_elapsed()함수는 start로부터 tick이 얼마나 경과하였는지 return하는 함수이다. 
• 이 return값이 ticks보다 작으면 thread_yield()함수를 호출하고, ready queue에 들어가서 자신의 순서를 기다린다.
• ready queue에서 자신의 순서가 되기를 기다리면서 계속 check하는 과정(busy waiting)을 해소하기 위해, thread를 block시킨 후 alarm_list에 넣어둔다. 
• 자신의 차례가 된다면 unblock한다. 이러한 방식을 이용함으로써 busy-waiting을 해소할 수 있다. 

---

 4.   문제의 해결 과정

1)      threads/thread.h → struct thread

줄 번호	코드	설명
83	struct thread	thread의 구조체이다. 이 곳에는 thread의 tcb 자료구조에 대한 정보가 들어있다.
103	int64_t expr	각 thread의 만료 시각(언제 깨어날지)을 나타내는 변수를 추가한다.

---

2)     threads/thread.c → thread_init

줄 번호	코드	설명
26	extern	alarm_list는 timer.c에서 선언된 변수이다.  때문에 thread.c의 초기에 extern을 이용하여 선언하였다.
95	list_init(&alarm_list)	alarm_list를 list_init()함수를 이용해 초기화한다.

---

3)     devices/timer.c → struct list alarm_list

줄 번호	코드	설명
26	alarm_list_ordered()	alarm list를 오름차순으로 정렬하는 함수이다.  이 함수는 다음 표에 자세히 설명되어있다.
27	struct list alarm_list	block된 thread들이 대기하는 list를 만든다.

---

4)     devices/timer.c → bool alarm_list_ordered

줄 번호	코드	설명
98	bool	true 또는 false를 return하기 위해 boolean으로 선언한다.
99	alarm_list_ordered()	alarm_list에 있는 각각의 thread의 만료 시간(expr)을 기준으로 오름차순하는 함수이다. 즉, expr이 가장 작은 thread를 list의 맨 앞으로 위치시키기 위한 함수이다.  이 함수는 timer_sleep()함수에서 사용된다. ※ 함수 정의 이유 : list 내에 있는 여러개의 thread의 expr를 매번 비교하는 것은 비효율적이다. list를 expr기준 오름차순으로 정렬 해둔다면, 첫 번째 요소만 비교하여 원하는 답을 얻을 수 있기 때문에 효율성을 높일 수 있다.
101, 102	thread *t1, *t2	각 thread의 구조체에 접근하기 위한 포인터 변수이다.
104	return	해당 thread의 expr이 비교 대상 thread의 expr보다 작으면 true를, 아니라면 false를 return한다.

---

5)     devices/timer.c → timer_sleep

줄 번호	코드	설명
108	timer_sleep()	기존에 있던 timer_sleep()함수를 호출한 thread를 현재 시각 기준으로 ticks시간이 경과할 때까지 block되도록 수정하였다.
112	struct thread *t	현재 thread를 가리키는 포인터 변수이다.
113	old_intr_level	interrupt의 control을 위한 변수이다.
115	INTR_ON	INTR_OFF이면 interrupt가 off가 되고, off가 되면 timer_interrupt()를 실행할 수 없다.  따라서 ON상태이어야 한다.
117, 118	if(ticks<=0), return	ticks가 0이하이면 block할 필요가 없으므로 return한다.
120	intr_disable()	현재의 interrupt level을 old_intr_level에 저장한 후, thread_block()함수의 실행을 위해 interrupt를 disable한다.
123	start+ticks	현재 thread의 expr은 start(함수 호출 순간의 ticks)에 해당 thread의 만료tick을 더한 값으로 한다.
125	list_insert_ordered()	list_insert_ordered()함수는 pintos에 있는 list operation 중 하나이다. 이 함수의 기본 구조는 다음과 같다.  timer_sleep()함수를 호출한 thread를 alarm_list에 삽입한다.  삽입할 때 앞서 선언한 alarm_list_ordered()에 의해 정렬되도록 삽입한다.  삽입 된 후의 list는 만료 시간의 오름차순 순서대로 정렬된다.
128	intr_set_level	interrupt의 block전의 level로 복구한다.

---

6)     devices/timer.c → timer_interrupt

줄 번호	코드	설명
206	timer_interrupt()	timer interrupt의 발생 시 이 함수가 실행되어 alarm_list를 check한다.
213	while()	alarm_list가 비어있지 않다는 조건하에 실행된다.
215	t=list_entry(list_front())	alarm_list의 첫 번째 thread를 t thread로 한다.
216 ~ 220	if(t->expr<=ticks)	expr이 ticks이하라는 의미는 thread의 만료시각이 되었거나 지났다는 뜻이다.  이러한 thread는 list_pop_front()를 통해 pop하고 unblock한다.
221	else	if문의 조건을 만족하지 않는다면, 아직 unblock할 순서가 되지 않았다는 의미이다. alarm_list는 만료시각 기준으로 오름차순으로 정렬되어 있기 때문에, 첫 번째 요소만 비교하면 된다.

---

5.    결과 및 테스트

1)      code의 수정 전과 후를 idle ticks의 변화를 통해 비교해본다. (pintos -q run alarm-multiple 실행)

 

결과 : idle ticks는 cpu가 할 일이 없을 때 idle thread를 실행하는 횟수이다. 수정 전 code는 busy-waiting으로 인해 계속해서 cpu가 점유되고 있기 때문에 idle thread가 실행될 일이 없다. 수정 후 code는 busy-waiting을 해소했기 때문에 cpu의 idle thread 방문이 가능하다. 따라서 code의 수정이 성공됨을 알 수 있다. 

---

2)     timer_sleep()함수를 사용하는 테스트 프로그램인 ‘alarm-single, alarm-multiple, alarm-simultaneous, alarm-priority, alarm-zero, alarm-negative’를 테스트 해본다. 그 결과, busy-waiting일 때의 테스팅 결과와 동일함을 알 수 있다. 테스팅 화면은 다음과 같다. 

 

          (1)    alarm-single

 

          (2)   alarm-multiple

 

          (3)   alarm-simultaneous

 

          (4)   alarm-priority

 

          (5)    alarm-zero

 

          (6)   alarm-negative