먼저 cygwin을 실행시켜서 os161 소스의 위치로 이동 후 ASST1의 환경을 만들어 줍니다.
여기 까지 진행했으면 이제 Eclipse의 환경도 수정합니다.
메뉴의 [Project] → [Properties] 를 눌러서 위의 화면을 띄운다음, Build directory 부분의 ASST0을 ASST1로 바꿔줍니다.
그리고 위의 오른쪽 화면처럼 make 부분들을 추가해 줍니다. (방법은 앞선 #0의 설명과 동일합니다.)
● Semaphore 분석
우리의 첫 과제는 os161에 동기화 관련 메서드를 추가하는 것입니다.
kern/include/synch.h 와 kern/thread/synch.c 를 살펴보면, 이미 세마포어는 구현되어 있음을 알 수 있습니다.
이것을 참고하여 Lock과 CV(Condition Variable)를 구현하는것이 목표입니다.
그럼 세마포어를 분석해 보겠습니다.
25 struct semaphore {
26 char *name;
27 volatile int count;
28 };
29
30 struct semaphore *sem_create(const char *name, int initial_count);
31 void P(struct semaphore *);
32 void V(struct semaphore *);
33 void sem_destroy(struct semaphore *);
위의 코드는 synch.h 에 정의된 세마포어의 선언입니다.
간단히 집고 넘어가면, sem_create( )를 이용하여 세마포어를 생성하고,
P( )를 통해서 공유자원에 접근을 제한(제한된 수의 스레드만 접근)하고,
V( )로 다음 스레드가 공유자원에 접근할 수 있도록 설정합니다.
마지막으로, sem_destroy( )를 사용하여 사용한 메모리를 해제합니다.
당연하지만, volatile int count; 로 선언한 이유는 이 변수가 레지스터에 존재하게 되면,
문맥교환(Context Switching)시 레지스터셋 교환이 일어나면서, 원하지 않은 값이 될 수 있기 때문입니다.
62 void
63 P(struct semaphore *sem)
64 {
65 int spl;
66 assert(sem != NULL);
67
68 /*
69 * May not block in an interrupt handler.
70 *
71 * For robustness, always check, even if we can actually
72 * complete the P without blocking.
73 */
74 assert(in_interrupt==0);
75
76 spl = splhigh();
77 while (sem->count==0) {
78 thread_sleep(sem);
79 }
80 assert(sem->count>0);
81 sem->count--;
82 splx(spl);
83 }
전체적인 코드는 세마포어의 개념이라 건너뛰고, 중요한 부분만 집고 넘어가겠습니다. 이 코드는 synch.c 에 있는 P( ) 연산 입니다.
코드에서 붉은색으로 표시한 부분을 눈여겨 봐야 합니다. 붉은 부분이 하는 역할은 인터럽트를 on/off 시키는 역할을 합니다.
splhigh( )를 통해서 spl값을 최고(15)로 세팅하게 되면, cpu의 인터럽트 플레그를 수정하여 인터럽트 불가 상태로 만들게 됩니다.
이렇게 되면 타이머 인터럽트가 무시되면서, 문맥교환(Context Switching)이 일어나지 않게 되고,
결과적으로 인터럽트 허용 상태가 될때 까지, 현재 스레드만 실행됨을 보장합니다.
다른 스레드가 실행되지 못하게 하여 변수에 접근조차 할 수 없기 때문에, 공유자원 접근을 제한할 수있습니다.
(위의 코드에서 공유되는 변수는 sem->count(접근가능한 스레드의 수) 가 됩니다.)
● Lock 설계
먼저 어떤 형태의 Lock을 구현할지 정해야 합니다. 우리는 Spin Lock 과 Mutex Lock 두가지에 대해서 생각해 보겠습니다.
먼저 Mutex Lock입니다. 핵심은 이미 누군가가 Lock을 사용중이면 sleep 상태로 들어가는 것입니다.
이것은 세마포어를 이용해서 쉽게 구현가능합니다.
Spin Lock 방식은 Lock 변수를 체크해서 다른 스레드가 소유중이면 무시하고, 아무도 사용중이지 않다면 획득하는 방식입니다.
이때, 다른 스레드가 Lock을 소유중이면 thread_yeild( )등을 사용하여, 다른 스레드로 CPU를 넘기면 됩니다.
그리고 다시 자신의 차례가 되었을때 위의 과정을 반복하며 Lock을 획득할 때 까지 진행합니다.
147 void
148 lock_acquire(struct lock *lock)
149 {
150 int s;
151 assert(lock != NULL);
152 assert(in_interrupt == 0);
153
154 restart:
155 s = splhigh();
156 if (lock->owner != NULL) { // Lock을소유한 스레드가 있다면..
157 splx(s); // spl을 복원하고 yeild 수행
158 thread_yield(); // (yield가 내부적으로 spl을 변경)
159 goto restart; // while 대용 goto 루프
160 }
161
162 assert(lock->owner == NULL); // 소유주가 없을때만 자신이 획득
163 lock->owner = curthread; // 스레드포인터로 소유를 구분
164
165 splx(s); // 종료전에 인터럽트 허용모드로 전환
166 }
167
168 void
169 lock_release(struct lock *lock)
170 {
171 assert(lock_do_i_hold(lock) != 0); // 소유한 스레드만이 풀기 가능
172 lock->owner = NULL; // 아무나 획득가능한 상태로 변경
173 }
174
175 int
176 lock_do_i_hold(struct lock *lock)
177 {
178 return lock->owner == curthread; // Lock 소유주가 자신인지 테스트
179 }
위와 같은 모양으로 만든 다음 컴파일하여 실행시키면 아래와 같은 결과가 나온다.
걸린 시간에 연연해 할 필요 없다. 지금의 sys161 환경이 특수(?)하게 잡혀 있어서 느릴 뿐, 다음 ASST2 이후부터는 빠르게 수행된다.
중요한건 spin lock의 작동 원리이다.
sleep 상태가 아닌, 계속된 체크를 통한 Lock 획득임을 반드시 기억해야 한다.
잘못된 구현 예..
● Condition Variable 설계
다음은 윈도우의 Event / 리눅스의 pthread_cond_xxxxxx( ) 시리즈 들이다.
cv_wait( ) 의 주된 역할은 잠시 Lock을 풀고, sleep 한 다음, 다시 Lock을 획득하는 것이다.
내부에 잠깐의 unlock구간을 두어서, 다른 thread가 해당 lock으로 다른 작업을 수행할 틈을 주는것이다.
이것이 왜 필요한 것일까?
공유변수를 사용하는 두 thread (T1, T2)가 있다 가정하자.
그런데 T2는 T1의 계산결과를 가지고 작업을 해야할때 cv_wait를 사용한다면, T1이 신호(cv_signal)를 보낼때 까지 T2가 대기하고,
T1이 cv_signal을 사용하면 T2가 깨어나서 마저 작업을 하는 등으로 동기화를 시킬 수 있을 것이다.
(물론 위의 방법 이외에도 해법이 있으나 위의 방식으로도 가능하다는 뜻이다.)
구현하는 방법에는 여러가지가 있을 것이다.
thread 배열을 유지하여 하나씩 또는 모두 깨우는 방법도 있을 것이고, 세마포어처럼 숫자만 유지하는 방법도 있다.
그럼 두 방식을 모두 살펴보자.
먼저 세마포어처럼 기다리고 있는 스레드의 숫자만 유지하는 방식이다.
synch.h
98 struct cv {
99 char *name;
100 // add what you need here
101 // (don't forget to mark things volatile as needed)
102 volatile int sleeper; // 대기중인 thread의 수
103 volatile int wakeup; // 일어날 thread의 수
104 };
synch.c
313 struct cv *
314 cv_create(const char *name)
315 {
316 struct cv *cv;
317
318 cv = kmalloc(sizeof(struct cv));
319 if (cv == NULL) {
320 return NULL;
321 }
322
323 cv->name = kstrdup(name);
324 if (cv->name==NULL) {
325 kfree(cv);
326 return NULL;
327 }
328
329 // add stuff here as needed
330 cv->sleeper = 0;
331 cv->wakeup = 0;
332
333 return cv;
334 }
335
336 void
337 cv_destroy(struct cv *cv)
338 {
339 assert(cv != NULL);
340
341 // add stuff here as needed
342 assert(cv->sleeper == 0);
343 assert(cv->wakeup == 0);
344
345 kfree(cv->name);
346 kfree(cv);
347 }
348
349 void
350 cv_wait(struct cv *cv, struct lock *lock)
351 {
352 int s = splhigh();
353
354 lock_release(lock);
355 cv->sleeper++;
356
357 sleep:
358 thread_sleep(cv);
359 if (cv->wakeup == 0) // 같은 주소로 sleep하기 때문에 별도로
360 goto sleep; // 실제 깨어날 숫자를 카운트 해야한다.
361
362 cv->wakeup--;
363 cv->sleeper--;
364 splx(s);
365
366 lock_acquire(lock);
367 }
368
369 void
370 cv_signal(struct cv *cv, struct lock *lock)
371 {
372 int s;
373 assert(lock_do_i_hold(lock) != 0);
374
375 s = splhigh();
376 cv->wakeup = 1; // 하나의 thread만 깨움
377 thread_wakeup(cv);
378 splx(s);
379 }
380
381 void
382 cv_broadcast(struct cv *cv, struct lock *lock)
383 {
384 int s;
385 assert(lock_do_i_hold(lock) != 0);
386
387 s = splhigh();
388 cv->wakeup = cv->sleeper; // 모든 thread를 깨움
389 thread_wakeup(cv);
390 splx(s);
391 }
잠들어 있는 숫자를 유지하는 방식을 사용하였다.
Queue를 사용한 방식..
os161은 시뮬레이터를 떠나서 실제 mips 환경에서 작동하기엔 무리가 있다.
os 내부의 구현에 대해서 탐구하는것이 주 목적이라 생각하여 과도하게 성능에 집착하진 않았다.
위에서 구현한 Lock과 wakeup을 유지하는 cv의 코드는 옆에 파일을 첨부하였다.
synch.h