[TIL] Pintos Project1 - Threads 정리

※ git book 기준으로 이해한 내용 정리 ※

0. 개념 및 코드 정리

1. thread

CPU 이용의 기본 단위, 동일 프로세스의 스레드들은 코드 영역, 데이터 영역, 운영체제 자원들을 공유

핀토스에서는 단일 스레드 프로세스(Single thread process)를 구현!

그러므로 프로세스의 상태변화가 스레드의 상태변화와 동일하다고 생각하고 구현함

프로세스 상태 변화 + thread.c 함수

이러한 멀티 프로그래밍의 목적은 CPU 사용률을 최대화하기 위함이며, 어떤 프로세스든 항상 실행 중이게 한다.

• time sharing(시분할 시스템) : 여러 프로세스 사이에서 CPU를 자주 전환함으로써 여러 사용자 프로그램이 수행되는 동안 각 프로그램과 상호작용할 수 있도록 한다.
• Process scheduler : CPU에서 프로그램 실행을 위해 실행 가능한 프로세스를 선택
  
  • Round Robin(RR) : 순서대로 시간단위(Time Quantum)로 CPU를 할당하는 방식
  • Priority : 우선순위가 높은 순서대로 CPU 할당
    • 핀토스에서는 Preemptive(선점형) 우선순위 스케줄링을 구현함

---

2. Synchronization(동기화)

임계 영역에 대해 원자적으로 동작하는 것처럼 보이게 한다.
2개 이상의 프로세스(Process) 또는 쓰레드(Thread)가 공유 메모리에서 어떠한 작업을 수행할 때 각자의 작업을 시기에 맞게 수행

• 기본적으로 핀토스에서는 busy waiting으로 동기화를 하고 있다.
  • CPU가 요청한 자원에 대한 권한을 얻을 때까지 대기하는 방식
  • 대기하는 동안 CPU의 자원을 낭비하게 된다.
  • 이는 Context switching 비용보다 기다리는게 더 효율적일 경우 사용
• 위에서 말했다시피 CPU가 노는 시간이 있으면 안된다. 그러므로 sleeping 방식으로 바꾸어 준다.
  • 현재 실행 중인 Thread가 권한을 얻기 위해 기다리는 시간이 존재하면 sleep_list(sleep queue)에 실행 중인 Thread 정보를 담고 다른 Thread에게 CPU를 양보하는 방식
  • 커널은 권한 이벤트가 발생하면 sleep_list에 담긴 Thread 정보를 깨워 CPU를 할당 → Alarm Clock 구현 이유
  • sleep_list에 넣는 비용 + context switching 비용이 발생
  • 기다리는 시간을 예측할 수 없을 경우 사용하면 좋다.
    •  

---

🛠️ 사용할 도구

1️⃣ semaphore : 두 개의 원자적 함수로 조작되는 정수 변수 → 핀토스에서는 이진 세마포어 사용

/* A counting semaphore. */
struct semaphore {
	unsigned value;             /* 현재 세마포어 값 */
	struct list waiters;        /* 세마포어를 기다리는 스레드의 리스트 */
};

함수 1. sema_down() → semaphore--

void sema_down (struct semaphore *sema) {
    enum intr_level old_level;

    ASSERT (sema != NULL);
    ASSERT (!intr_context ());

    old_level = intr_disable (); //인터럽트 불가능하도록 한다. -> 원자적으로 실행되어야 하므로
    while (sema->value == 0) { //값이 0이면 기다려야한다.
    	//semaphore의 waiters 리스트에 삽입한다. -> sleeping 방식으로 구현
        list_insert_ordered (&sema->waiters, &thread_current ()->elem, ready_sort, NULL);
        thread_block (); //스레드를 재운다.
    }
    sema->value--;
    intr_set_level (old_level); //원래 인터럽트 상태로 돌아온다.
}

함수2. sema_up() → semaphore++

void sema_up (struct semaphore *sema) {
    enum intr_level old_level;

    ASSERT (sema != NULL);

    old_level = intr_disable (); //인터럽트를 불가능하도록 설정
    if (!list_empty (&sema->waiters)) { //semaphore를 기다리는 스레드가 존재하면
    	//우선순위가 높은 스레드를 위해 정렬 -> 후에 우선순위 스케줄링을 위해 구현
        list_sort(&sema->waiters, ready_sort, NULL);
        //우선순위가 가장 높은 스레드를 깨운다.
        thread_unblock (list_entry (list_pop_front (&sema->waiters), struct thread, elem));
    }
    sema->value++;
    preemptive(); //선점형 우선순위 스케줄링 구현
    intr_set_level (old_level);
}

 

2️⃣ lock

: 한 프로세스가 임계 영역에 해당하는 코드를 실행하고 있을 때 다른 프로세스가 임계영역으로 진입하지 못하도록 하는 것

/* Lock. */
struct lock {
	struct thread *holder;      /* lock을 잡고있는 스레드 */
	struct semaphore semaphore; /* 위에서 구현한 이진 세마포어 자료구조 */
};

 

위와 같은 도구를 사용하여 동기화를 하면 발생하는 문제 중 하나가 priority inversion 이다.

Kaist Pintos ppt

💡 즉, 우선 순위가 높은 태스크가 READY상태 (실행 가능)로 바뀌었지만 더 낮은 우선순위의 태스크가 CPU를 점유하고 있어서 실행되지 못하는 상태를 우선순위 역전이라고 한다.

 

이를 해결하기 위해 사용하는 기법이 priority donation 이다.

Kaist Pintos ppt

 

함수 1. lock_aquire() : lock을 요청한다.

• 우선순위 donation을 적용하여 구현
• 2가지 구현 방법
  • 현재 스레드가 가진 lock들의 모든 waiters를 비교
  • 현재 스레드가 가진 lock들의 우선순위가 가장 높은 것들만 비교
  • 자세한 내용은 https://soo-note.tistory.com/83

함수 2. lock_release() : lock을 해제한다.

void lock_release (struct lock *lock) {
    ASSERT (lock != NULL);
    ASSERT (lock_held_by_current_thread (lock));

    //현재 스레드가 요청한 엔트리 제거
    //donation_list에서 제거하려는 lock에 관한 요소 삭제
    remove_with_lock(lock);

    //우선순위 업데이트
    //현재 lock을 가진 스레드의 우선순위를 donation_list 중 가장 높은 우선순위로 변경
    update_priority();

    lock->holder = NULL;
    sema_up (&lock->semaphore);
}

void remove_with_lock(struct lock *lock) {
    //현재 스레드의 donations
    struct list *donation_list = &(thread_current()->donations);
    if(list_empty(donation_list)) {
        return;
    }

    struct list_elem *don_elem = list_front(donation_list);
    struct thread *donation_thread;

    while(don_elem != list_tail(donation_list)) {
        donation_thread = list_entry(don_elem, struct thread, donation_elem);
        if(donation_thread->wait_on_lock == lock) { //현재 스레드에서 요청한 엔트리이면
            list_remove(&donation_thread->donation_elem);
        }
        don_elem = list_next(don_elem);
    }
}

void update_priority() {
    struct thread *curr = thread_current();
    struct list *donations = &(curr->donations);
    if(list_empty(donations)) { //donation이 없으면 원래 우선순위로 set
        curr->priority = curr->origin_priority;
        return;
    }
    //donation 중 우선순위가 가장 높은 값으로 set
    list_sort(donations, donation_sort, NULL);
    curr->priority = list_entry(list_front(donations), struct thread, donation_elem)->priority;
}

---

1. Alarm Clock

1. 기본적으로 주어진 코드(timer.c)

    : 만약 우선순위가 높은 스레드가 기다리고 있는 상황이라면 계속해서 기다리기만 한다.

void timer_sleep(int64_t ticks) {
	int64_t start = timer_ticks();

	ASSERT (intr_get_level () == INTR_ON);
    //timer_elapsed() : 타이머가 시작된 이후로 경과한 시간을 측정하는 함수
	while (timer_elapsed (start) < ticks)
		thread_yield (); //ready_list에 넣는다.
}

⏰ 스레드를 재우는 함수

2. 변경한 코드

    : 현재 기다려야 하는 스레드일 경우 sleep_list에 재우고 다음으로 우선순위가 높은 스레드를 실행하도록 한다.

void timer_sleep(int64_t ticks) {
	int64_t start = timer_ticks();
	if (timer_elapsed(start) < ticks) {
		thread_sleep(start + ticks); //sleep_list에 넣는다.
	}
}

void thread_sleep(int64_t ticks) {
	struct thread *curr = thread_current();
	enum intr_level old_level;

	ASSERT(!intr_context());

	old_level = intr_disable();
	if (curr != idle_thread) {
		curr->wakeup_tick = ticks; // store the local tick to wake up
		list_insert_ordered(&sleep_list, &curr->elem, sleep_sort, NULL);
	}

	thread_block();
	intr_set_level(old_level);
}

---

⏰ 재운 스레드를 깨우는 함수 (thread.c)

void wake_up(int64_t ticks) {
	// sleep list가 비어있지 않은 경우에만 돌아간다.
	enum intr_level old_level;
	struct thread *curr;
	old_level = intr_disable();
	while (!list_empty(&sleep_list)) {
		curr = list_entry(list_front(&sleep_list), struct thread, elem);
		if (curr->wakeup_tick <= ticks) {
			list_pop_front(&sleep_list);
			thread_unblock(curr);
			preemptive();
		}
        //sleep_list 경우 tick 순으로 정렬하므로 조건이 한번 만족하지 않으면 중지
		else {
			break;
		}
	}
	intr_set_level(old_level);
}

---

2. Priority Scheduling

ready_list, waiters 모두 우선순위 순으로 정렬하여 우선순위가 높은 것이 앞에 있도록 한다.

선점형 우선순위 스케줄링으로 구현

void preemptive()
{
	if (thread_current() == idle_thread)
		return;
	if (list_empty(&ready_list))
		return;

	struct thread *curr = thread_current();
	struct thread *ready = list_entry(list_front(&ready_list), struct thread, elem);
	//현재 스레드보다 우선순위가 높은 스레드가 준비중이라면
    if (curr->priority < ready->priority) {
		thread_yield();
	}
}

❗️ 사용해야할 부분

• 스레드 생성시 : 현재 실행 중인 스레드보다 우선순위가 높은 스레드가 생성될 수 있다.
• 스레드 우선순위 변경시 : 변경된 우선순위가 높을 수 있다.
• 스레드 깨울때 : 깨운 스레드의 우선순위가 높을 수 있다.