헷갈렸던 struct 개념 정리
semaphore
struct semaphore {
unsigned value;
struct list waiters;
}- value: 세마포어의 현재 값, 공유 자원에 접근할 수 있는 쓰레드의 수
- waiters: value가 0이면 더 이상 쓰레드가 자원에 접근할 수 없을 때, 접근을 시도하는 쓰레드들이 추가됨
condition
struct condition {
struct list waiters;
}- waiters: 조건 변수의 waiter list. 특정 조건을 만족할 때까지 기다리는 쓰레드들이 포함됨.
대기중인 쓰레드들은 semaphore_elem 구조체를 사용하여 관리됨.
semaphore_elem
struct semaphore_elem {
struct list_elem elem;
struct semaphore semaphore;
}- elem : list_elem 타입, condition variable의 waiters 리스트에 연결하기 위한 list element
- semaphore: 쓰레드가 condition variable에 대기할 때 사용되는 세마포어. 조건이 만족될 때 쓰레드를 깨우는데 사용
왜 semaphore_elem 안에 Semaphore가 포함되어 있는가?
- semaphore: 특정 자원에 대한 접근을 제어할 때 사용 - 동시에 여러 쓰레드가 같은 자원에 접근하는 것을 방지
- semaphore_elem : 조건 변수의 waiters 리스트에 추가될 때 사용됨!
semaphore와 condition variable
세마포어 - 동시에 리소스에 접근할 수 있는 쓰레드의 수 제어
condition variable - 특정 조건이 만족될 때까지 쓰레드 대기
세마포어의 Waiters list: 세마포어의 값이 0이하일 때 추가되는, 특정 자원을 얻기 위해 대기하는 쓰레드 list.
세마포어가 관리하는 자원을 획득하기 위해 기다리는 쓰레드들
sema_up연산을 통해 세마포어 값 증가하면 이 리스트에서 쓰레드 하나가 깨어나고 깨어난 쓰레드는 해당 자원을 사용할 수 있게 된다.condition variable의 waiters list:
semaphore_elem 구조체들이 우선순위 순으로 정렬됨.
condition variable에 대한signal이 발생했을 때, 가장 높은 우선순위를 가진 semaphore_elem 구조체 => 내부의 세마포어의 대기 중인 쓰레드 중 가장 우선순위가 높은 쓰레드가 먼저 깨워지게 된다.
condition variable에서의 wait
T1, T2, T3가 하나의 condition variable에 대해서 wait
- 대기 중인 각 쓰레드 (T1, T2, T3 등)은 0으로 초기화된 자신만의 세마포어 생성
- 각 쓰레드는 조건 변수의 Waiters 리스트에 자신을 등록한 다음, 자신의 세마포어를 사용하여 sema_down 연산을 수행하여 대기 상태
- 이때 조건 변수의 waiters 리스트에는 T1 -> T2 -> T3 순으로 쓰레드 등록, 각 쓰레드의 세마포어 waiters 리스트에는 해당 쓰레드 자신만이 존재.
T1의 semaphore의 waiting list: T1
T2의 semaphore의 waiting list: T2
T3의 semaphore의 waitling list: T3
조건 변수의 signal, broadcast 연산을 통해 조건이 만족되었을 때 조건변수의 waiters list에 있는 쓰레드 중 하나 또는 전부가 깨어나게 된다. 이때 각 쓰레드의 세마포어를 통해 대기 상태에서 벗어나게 됨.
구현하기
sema_up
: 세마포어 value를 증가시키고, 해당 세마포어가 관리하는 자원을 기다리는 쓰레드가 있다면 이를 깨우는 역할.
void
sema_up (struct semaphore *sema) {
enum intr_level old_level;
ASSERT (sema != NULL);
old_level = intr_disable ();
//세마포어의 대기자 목록이 비어있지 않다면, 대기 중인 쓰레드가 있다면
if (!list_empty (&sema->waiters)) {
//sema->waiters - 기다리고 있는 쓰레드 리스트 : 우선순위 순서로 정렬 =>
//thread_unblock할 때 가장 높은 우선순위를 가진 쓰레드가 먼저 깨어나게끔
list_sort(&sema->waiters, compare_thread_priority, NULL);
thread_unblock (list_entry (list_pop_front (&sema->waiters),
struct thread, elem));
}
sema->value++; //세마포어의 값 1 증가 / 깨울 수 있는 쓰레드의 수 증가 ->
preempt_thread(); //현재 쓰레드와 ready_list에 있는 쓰레드의 우선순위 비교 - 우선순위가 더 높은 쓰레드로 전환
intr_set_level (old_level);
}list_sort(&sema->waiters, compare_thread_priority, NULL);
sema->waiters를 확인해서 이 세마포어가 관리하는 자원을 기다리는 쓰레드들을 우선순위 기준으로 정렬하는 코드를 추가해준다. 정렬해준 다음에 thread_unblock을 해주면 우선순위가 가장 높은 쓰레드가 해당 자원을 획득할 수 있게 된다!
sema->waiters에서 세마포어를 기다리고 있는 쓰레드들은 이미sema_down함수에 의해blocked된 상태이다. 따라서thread_unblock을 해주면ready상태가 되어 우선순위로 정렬되어ready_list에 삽입된다.
=> 따라서preempt_thread()를 호출하여 현재 실행 중인 쓰레드와 ready_list에 있는 쓰레드의 우선순위를 비교하여 context switch가 필요한지 판단한다.
sema_down
: 세마포어의 값이 양수면(사용 가능한 자원이 있으면), 해당 값을 감소시킴, buit 세마포어의 값이 0이라면(자원이 모두 사용중이면) 쓰레드를 해당 자원이 사용가능해질 때까지 대기, block 시킴!
//세마포어의 값이 양수가 될 때까지 대기 -> 양수 되면 그 값을 감소시킴.
void
sema_down (struct semaphore *sema) {
enum intr_level old_level;
ASSERT (sema != NULL);
ASSERT (!intr_context ());
old_level = intr_disable (); //인터럽트 비활성화. 세마포어 연산 중에 다른 인터럽트가 발생하지 않도록.
/*세마포어의 값이 0(세마포어가 사용중이면) - 기다리는 쓰레드 Waiters목록에 정렬하여 삽입 ,
현재 쓰레드를 block 상태로 전환. => 세마포어의 값이 양수가 될 때까지 대기 */
while (sema->value == 0) {
list_insert_ordered(&sema->waiters, &thread_current()->elem, compare_thread_priority, NULL); // 현재 쓰레드를 우선순위 순으로 waiters 리스트에 삽입 => 높은 우선순위의 스레드가 가장 먼저 공유 자원에 접근할 수 있도록
thread_block ();
}
//세마포어의 값이 양수가 되면 -1. => 자원에 대한 접근 권한 획득
sema->value--;
intr_set_level (old_level); //원래의 인터럽트 레벨로 복원
}
while (sema->value == 0)를 사용하여 양수가 되는지 확인
-> 0이라면 sema->waiters리스트에 우선순위 순으로 정렬하여 insert하고 해당 쓰레드를 thread_block.
=> 나중에 세마포어 자원이 사용가능하게 되면 가장 높은 우선순위를 가진 쓰레드가 자원을 먼저 점유할 수 있도록.
세마포어의 값이 양수가 되면, sema->value--를 통해 자원 점유.
의문>
while을 -> if문으로 바꿔도 테스트는 통과된다.
But) While문은 sema->value가 0인지 반복적으로 검사한다.
멀티 쓰레드 환경에서 다른 쓰레드가 세마포어의 값을 변경한 후에도 현재 쓰레드가 올바르게 blocked 상태가 되어 대기할 수 있게끔 할 수 있다. While문이 더 권장될 것
cond_wait
특정 조건이 만족될 때까지 쓰레드가 대기하게 하고, 조건이 만족되면 대기 중인 쓰레드를 깨우는 함수.
void
cond_wait (struct condition *cond, struct lock *lock) {
struct semaphore_elem waiter;
ASSERT (cond != NULL);
ASSERT (lock != NULL);
ASSERT (!intr_context ());
ASSERT (lock_held_by_current_thread (lock));
sema_init (&waiter.semaphore, 0);
/*condition -> waiters: 특정 조건이 충족되기를 기다리고 있는 쓰레드의 리스트
waiters 리스트에 추가되는 각 semaphore_elem이 대표하는 가장 우선순위가 높은 쓰레드의 우선순위를 기준으로 정렬
*/
list_insert_ordered(&cond->waiters, &waiter.elem, compare_sema_priority, NULL);
lock_release (lock); //현재 쓰레드가 보유하고 있는 락 해제 -> 다른 쓰레드들이 공유 자원에 접근 가능
//현재 semaphore의 Value = 0 이니까 sema_down() => Blocked 상태가 됨.
sema_down (&waiter.semaphore);
// waiter 세마포어의 값 0 이상이 될 때까지 현재 쓰레드 대기(cond_signal, cond_broadcast)
lock_acquire (lock);
}
sema_init (&waiter.semaphore, 0);: semaphore_elem 구조체인 waiter의 semaphore 값을 0으로 설정한다. -> 세마포어에 대해 sema_down 호출할 때 즉시 대기 상태가 됨
list_insert_ordered(&cond->waiters, &waiter.elem, compare_sema_priority, NULL); : cond->waiters 리스트에 대기 중인 쓰레드를, 우선순위에 따라 정렬해서 insert한다.
lock_release(lock) 현재 쓰레드가 보유하고 있는 락이 해제되면 다른 쓰레드들이 공유 자원에 접근할 수 있게 된다.
sema_down(&waiter.semaphore) => 현재 세마포어의 값이 0이상 될 때까지 waiter의 세마포어는 blocked상태가 된다.
lock_acquire(lock): cond_signal, cond_broadcast의 호출이 되면 세마포어의 값이 0이상이 되고 해당 쓰레드는 공유 자원에 대한 접근이 가능해진다. 그래서 깨어난 쓰레드는 공유 자원에 대한 lock을 안전하게 획득할 수 있게 된다.
cond_signal
: 조건 변수의 대기열에 있는 쓰레드 중 하나를 깨움.
void
cond_signal (struct condition *cond, struct lock *lock UNUSED) {
ASSERT (cond != NULL);
ASSERT (lock != NULL);
ASSERT (!intr_context ());
ASSERT (lock_held_by_current_thread (lock));
if (!list_empty (&cond->waiters)){
list_sort(&cond->waiters, compare_sema_priority, NULL);
sema_up (&list_entry (list_pop_front (&cond->waiters),
struct semaphore_elem, elem)->semaphore);
}
}cond->waiters에 있는 세마포어 엘리먼트들의 맨 앞에 있는 쓰레들끼리의 우선순위를 비교해서 정렬을 해주고,
sema_up을 호출해서 세마포어 값을 증가시켜 대기 상태에 있는 우선순위가 가장 높은 쓰레드를 깨워준다. 그러면 해당 쓰레드는 실행이 가능해진다.
