정글 64일차

윤종성·2024년 9월 2일
0

핀토스

목록 보기
2/7

PintOS(핀토스)는 교육 목적으로 설계된 운영 체제(OS) 커널이다.
정글 8주차부터는 핀토스에서 필요한 기능을 구현하며 운영 체제의 핵심 개념을 학습한다.

키워드

1. 프로세스와 스레드

[[CSAPP# 1-7. 운영체제는 하드웨어를 관리한다|참고]]

2. CPU 스케줄링 알고리즘

출처: https://eun-jeong.tistory.com/17 [흔들리며 피는 꽃:티스토리]
스케줄러는 성능과 공정성으로 평가할 수 있다.
성능은 요청이 작업을 끝내고 반환될 때까지 걸리는 반환 시간 turnaround time과 작업이 처음 도착했을 때부터 처음 스케줄될 때까지의 시간인 응답 시간 response time으로 측정할 수 있다.
공정성은 특정 요청이 불공평하게 더 많은 자원을 차지하거나 오랫동안 자원을 배정받지 못하는 상황(기아 starvation)을 방지하는 것을 의미한다.

2-1. 비선점형 스케줄링

  • 한 프로세스가 CPU를 할당받으면 작업 종료 후 CPU 반환 시까지 다른 프로세스는 CPU 점유가 불가능한 스케줄링 방식
  • 모든 프로세스에 대한 요구를 공정하게 처리할 수 있지만, 짧은 작업을 수행하는 프로세스가 긴 작업 종료 시까지 대기해야할 수도 있다. (콘베이 현상)

2-1-1. FCFS/FIFO (First Come First Served/First In First Out)

선착순으로 요청이 먼저 온 작업을 할당한다.
작업이 다 끝난 다음에 다음 요청을 할당한다.

2-1-2. SJF(Shortest Job First)

작업시간이 짧은 요청을 먼저 할당한다.
작업시간을 사전에 알 수 있어야 한다.

2-2 선점형 스케줄링

  • 하나의 프로세스가 CPU를 차지하고 있을 때, 현재 프로세스를 중단시키고 CPU를 점유할 수 있는 스케줄링 방식
  • 비교적 응답이 빠르다는 장점이 있지만, 처리 완료 시간을 예측하기 힘들고 높은 우선순위 프로세스들이 계속 들어오는 경우 오버헤드를 초래
  • 일괄처리 시스템(한 번에 하나의 프로그램만 처리) 이후 현대의 모든 스케줄러는 선점형이다.

2-2-1. SRT/STCF (Shortest Remaining Time First/Shortest Time-to-Completion First)

가장 짧은 시간이 소요되는 작업을 먼저 수행한다.
SJF와 다르게 남은 시간이 더 짧다고 판단되는 작업이 준비 큐에 생기면 더 짧은 작업에 점유를 넘겨준다.

  • 장점
    - 반환 시간이 짧다.
  • 단점
    - 작업시간을 사전에 알 수 있어야 한다.
    - 응답 시간이 길다.

2-2-2. 라운드 로빈 (Round Robin/ RR)

스레드마다 공평하게 돌아가면서 CPU를 점유하는 방식
정해진 시간이 넘어가면 CPU 점유를 다음 프로세스로 넘겨준다.
응답 시간을 개선하였으나 반환시간이 늦어지는 단점이 있다.

  • 장점
    - 응답 시간이 짧다.
  • 단점
    - 반환 시간이 길다.

2-2-3. MQS(Multilevel Queue Scheduling)

작업 시간을 사용하는 스케줄러의 경우 현실적으로는 작업 시간을 미리 알기 힘들다는 점 때문에 구현이 불가능한 경우가 많다.
멀티레벨 큐는 큐를 우선순위 별로 나눈 것으로 작업 시간 대신 우선순위를 사용한다.

1. 구조 및 동작 방식:

  • 프로세스들은 고정된 여러 개의 큐로 나뉩니다.
  • 각 큐는 별도의 스케줄링 알고리즘을 사용하며, 큐 간의 스케줄링 순서도 고정되어 있습니다. 예를 들어, 상위 큐가 하위 큐보다 높은 우선순위를 가질 수 있습니다.
  • 큐 간의 이동은 허용되지 않습니다. 즉, 한 번 특정 큐에 배정된 프로세스는 그 큐 내에서만 스케줄링됩니다.

2. 큐의 예시:

  • 시스템 프로세스 큐, 대화형 프로세스 큐, 배치 프로세스 큐 등으로 나뉠 수 있습니다.
  • 상위 큐의 프로세스가 모두 처리된 후에야 하위 큐의 프로세스가 처리됩니다.

3. 장점:

  • 간단한 구현과 명확한 우선순위 관리가 가능합니다.
  • 다양한 유형의 프로세스를 효율적으로 관리할 수 있습니다.

4. 단점:

  • 한 큐에 속하는 프로세스가 다른 큐로 이동할 수 없기 때문에 유연성이 부족합니다.
  • 하위 큐에 속한 프로세스가 기아(starvation)에 빠질 수 있습니다.

2-2-4. MFQS(Multilevel Feedback Queue Scheduling)

우선순위가 고정된 MQS와 달리 우선순위를 변경하면서(feedback) 스케줄링한다.
1. 구조 및 동작 방식:

  • 프로세스들은 여러 개의 큐로 나뉘지만, 큐 간의 이동이 가능합니다.
  • 일반적으로 첫 번째 큐가 가장 높은 우선순위를 가지며, 높은 우선순위 큐에서 시간이 다 되면 하위 우선순위 큐로 이동합니다.
  • 프로세스가 CPU를 오래 사용하거나 특정 조건을 만족할 때 하위 큐로 이동시키며, 반대로 하위 큐에서 상위 큐로 이동할 수 있는 경우도 있습니다.

2. 큐의 예시:

  • 첫 번째 큐는 짧은 CPU 타임 슬라이스를 가진 프로세스들을 위한 라운드 로빈 스케줄링을, 두 번째 큐는 더 긴 CPU 타임 슬라이스를 가진 프로세스들을 위한 FCFS(First-Come, First-Served) 스케줄링을 사용하는 식으로 설정할 수 있습니다.
  • 프로세스가 CPU 시간을 많이 사용하면 점차 하위 큐로 내려가, CPU 시간이 적게 필요한 다른 프로세스들에게 기회를 양보하도록 유도합니다.

3. 장점:

  • 유연성이 높고, 다양한 프로세스 특성에 적응할 수 있습니다.
  • 프로세스의 우선순위가 동적으로 조정되므로 공정성이 높아지고, 기아(starvation) 현상을 방지할 수 있습니다.

4. 단점:

  • 구현이 복잡하며, 각 큐의 스케줄링 정책과 큐 간 이동 규칙을 잘 설계해야 합니다.
  • 시스템의 성능에 영향을 주는 다양한 파라미터를 조정해야 하기 때문에 튜닝이 필요합니다.

3. 경쟁 상태(Race Condition)

  • 정의: 둘 이상의 실행 흐름(스레드일 수도 있고, 프로세스일 수도 있다.)이 공동 자원(디스크, 메모리, I/O 등)을 경쟁적으로 동시(concurrently)에 접근할 때 발생한다.
    특히 접근이 이루어지는 순서에 따라 실행 결과가 달라질 수 있는 상황을 말한다.
  • 해결방법: 공동 자원에 동시에 접근하지 못 하도록 막는다.
    구체적으로는, 한 실행 흐름이 공용 데이터를 사용하고 있을 때 다른 실행 흐름이 접근하지 못하도록 사용 중 신호를 담는 변수를 사용하는 방법이 있다. 이런 변수로는 세마포어와 뮤텍스 등이 있다.

4. 세마포어와 뮤텍스

  • 세마포어: 특정 자원에 대해 접근할 수 있는 스레드의 수를 제한하는 방식. 자원을 사용하는 스레의 카운터이며, 일반적으로 긴 시간을 확보하는 리소스에 대해 이용한다.
  • 뮤텍스: 특정 코드 블록을 하나의 스레드만이 실행하도록 하는 것. 1개 스레드만 사용하도록 허용하는 세마포어의 일종이라고 볼 수도 있다. Lock이라고도 하며 블록 안에 진입할 때 Lock, 빠져나올 때 Unlock을 하게된다. 다른 스레드가 Lock을 한 상태에서는 Unlock하기 전까지는 진입할 수없다. 특정 조건이 발생할 경우에만 Unlock하게 하는 방식으로도 사용할 수 있으며 이를 모니터(Monitor)라고 한다.

5. 데드락(Deadlock)

세마포어나 뮤텍스 같은 상호배제 방식을 사용함으로써 발생할 수 있는 상태로 스레드 서로가 서로가 가진 자원을 요구하기 때문에 실행 흐름이 더 이상 진행되지 못하는 상태를 의미한다.
데드락(교착 상태)이 발생하기 위해서는 다음의 네 가지 조건이 모두 충족되어야 한다.(Coffman 조건. 필요충분조건)

  1. 상호 배제(Mutual Exclusion):
    • 자원은 오직 하나의 프로세스만이 사용할 수 있다. 즉, 자원이 비점유 상태에서는 다른 프로세스가 그 자원을 사용할 수 없도록 한다.
  2. 점유와 대기(Hold and Wait):
    • 최소 하나의 자원을 점유하고 있으면서, 동시에 다른 자원을 요청하며 그 자원이 해제되기를 기다리는 프로세스가 있어야 한다.
  3. 비선점(Non-preemption):
    • 프로세스가 어떤 자원을 점유한 상태에서 다른 자원을 추가로 요청할 때, 이미 점유한 자원을 강제로 빼앗길 수 없고, 요청한 자원을 사용할 수 있을 때까지 기다려야 한다.
  4. 순환 대기(Circular Wait):
    • 대기 상태의 프로세스들이 서로 자원을 요청하며 순환적으로 기다리고 있어야 한다. 즉, P1이 P2가 점유한 자원을 기다리고, P2는 P3가 점유한 자원을 기다리며, 마지막으로 Pn이 P1이 점유한 자원을 기다리는 형태의 순환 대기가 존재해야 한다.

6. 문맥 전환(Context Switch)

다른 실행 흐름으로의 전환을 의미하는 문맥 전환을, 실체적인 레지스터 상태를 기준으로 정의하면:
현재 실행 중인 스레드(프로세스)의 상태를 저장하고, 다음에 실행할 프로세스의 상태를 복원하는 과정이다.
스케줄러 등에 의해 인터럽트 문맥에서 이루어진다.
저장하고 복원하는 상태로는 레지스터, 프로그램 카운터, 스택 포인터 등이 있다.
멀티 스레드를 구현하기 위해 필수적인 작업이다.

프로젝트1. Threads

핀토스는 아직은 단일 프로세스로 진행된다.
main 함수라는 하나의 문맥 안에 멀티쓰레드로 프로그램을 실행한다.
즉, os는 여러 개의 쓰레드를 관리해야한다.
핀토스는 한 번에 하나의 스레드만을 실행하기 때문에 실행되는 스레드를 제외하고는 모두 비활성화된다. 다음 실행할 스레드를 결정하는 작업을 통틀어 스케줄링(scheduling)이라고 한다.
수정하지 않은 핀토스는 RR방식의 선점형 스케줄링을 사용한다.

1-1. Alarm Clock

1-1-1. 타이머 인터럽트

선점형 스케줄링을 위해서는 [[CSAPP#8-1. 예외상황|예외상황 Exception]]이 반드시 필요하다.
선점을 위해서는 예외상황 중에서도 비동기적으로 발생하는 인터럽트를 발생시켜야 한다.
선점이 필요한 특별한 상황인지를 파악하기 위해서 커널이 CPU를 점유해야만 하기 때문이다.
특별한 상황인지 파악하기 위해 인터럽트를 특별한 상황에만 발생시키려 하면 문제가 순환한다. 즉, 특별한 상황에만 인터럽트를 발생시킬 수 없다.
따라서 선점형 스케줄링을 위해서 컴퓨터는 주기적으로 인터럽트를 발생시킨다.

타이머 인터럽트는 [[CSAPP#8-1-2-1. 인터럽트 Interrupt|하드웨어 인터럽트]]의 일종이다.
하드웨어 타이머는 컴퓨터에 있는 물리적인 하드웨어 모듈로 일정한 주기(틱 ticks)[^1-1]마다 타이머 인터럽트 시그널을 생성한다.
타이머 인터럽트가 발생하면 프로세서는 예외 테이블에서 타이머 인터럽트 핸들러를 호출한다.
타이머 인터럽트 핸들러는 매 틱마다 수행해야 하는 동작을 수행하고 다시 유저 스레드로 돌려놓는다.

[^1-1]: 주기를 변경할 수 있는 타이머도 존재한다.

/* PintOS에서의 타이머 인터럽트 핸들러 */
static void
timer_interrupt (struct intr_frame *args UNUSED) {
    ticks++;
    thread_tick ();
}

/* Called by the timer interrupt handler at each timer tick.
   Thus, this function runs in an external interrupt context. */
void
thread_tick (void) {
	struct thread *t = thread_current ();

	/* Update statistics. */
	if (t == idle_thread)
		idle_ticks++;
#ifdef USERPROG
	else if (t->pml4 != NULL)
		user_ticks++;
#endif
	else
		kernel_ticks++;

	/* RR 방식의 선점형 스케줄러
	   매 틱마다 TIME_SLICE를 현재 스레드가 초과했는지를 확인하고
	   초과했다면 다음 스레드에 양보(yield)한다. */
	if (++thread_ticks >= TIME_SLICE)
		intr_yield_on_return ();
}

핀토스에서는 매 틱마다 전체 시스템 틱(전역변수 ticks)를 증가시키고 thread_tick을 호출한다.
timer_interrupt에서 이 내용을 볼 수 있다.

1-1-2. Busy-wait

busy-wait은 스레드 대기 방식의 하나로
특정 조건이 충족될 때까지 CPU를 사용해 루프를 돌며 대기하는 방식이다.

/* Suspends execution for approximately TICKS timer ticks. */
void
timer_sleep (int64_t ticks) {
	int64_t start = timer_ticks ();

	ASSERT (intr_get_level () == INTR_ON);
	while (timer_elapsed (start) < ticks)
		thread_yield ();
}

timer_sleep함수는 인자로 받은 값만큼의 틱동안 스레드를 대기시키는 함수이다.
thread_yield함수는 현재 스레드를 스레드 대기열 맨 마지막으로 보내고 다음 스레드를 실행시키는, 양보하는 함수이다.
thread_yield함수를 호출하지 않는다면 RR방식이라면 제한시간이 초과되면 다른 스레드에 넘겨줄 것이고 비선점형 방식이라면 계속 CPU 사용을 점유할 것이다.
이를 방지하기 위해 양보함수를 계속 호출하여 CPU 점유를 넘겨준다.
그러나 이 방식에는 두 가지 문제점이 있다.
1. 일단 스레드 대기열에 자신을 등록해 두었다가 자신의 차례가 되면 CPU 점유권을 받는다.
스레드는 시간을 확인하고 일어날 시간 전이라면 다시 스레드 대기열 뒷쪽으로 물러난다.
즉, 스레드는 계속 스레드 대기열에 등록되어있다.
이 과정에서 컨텍스트 스위치가 일어나며 리소스 낭비가 발생한다.
2. 스레드 대기열이 비어있다면, idle 상태라면 while문을 반복하기 위해 모든 CPU 리소스를 사용하며 리소스를 낭비한다.
이런 문제를 해결하기 위해 정해진 시간을 초과하기 전까지는 대기열에 등록되지 않는 timer_sleep함수를 구현해야한다.

1-1-3. Sleep

sleep 방식은 정해진 시간동안 CPU 사용을 중단하는 방식이다.
즉 다시 깨어나기 전까지는 해당 스레드는 활성화되지 않으므로 다른 컨텍스트에서 시간을 확인하고 깨워줘야 한다.
어떤 스레드가 sleep을 사용할 지 모르므로 다른 스레드가 깨워주는 방식은 불가능하다.
깨어나는 시간이 틱으로 결정되므로 틱마다 작업을 수행하는 타이머 인터럽트 핸들러가 처리하는 것이 적절하다.
이를 구현하기 위해서는 일단 깨어날 시간을 저장하고 잠든 스레드를 기록하는 두 가지 기능이 필요하다.

1-1-3-1. 시간 저장

리눅스커널에서는 스레드를 생성하면
1. 시스템 콜을 처리하고(함수 스택같이)
2. 인터럽트가 발생했을 때 컨텍스트 전환을 위해
스레드별로 커널 스택이 제공된다.
커널스택은 [[가상메모리]]의 커널 영역에 저장되고, 커널스택에는 커널 모드에서의 스택 프레임과 스레드 정보가 저장된다.
![[Pasted image 20240825230615.png]] (커널 스택은 그림기준 최상단 세그먼트에 저장된다.)

인터럽트 핸들러가 스레드를 깨울지 여부를 결정하기 위해선 잠든 스레드 별 깨어날 시간 정보가 필요하다.
이 정보는 커널 모드에서만 사용하므로 저장할 공간은 커널영역에, 그 중에서도 스레드마다 할당되는 커널스택의 스레드 정보에 저장하는 것이 적절해보인다.

struct thread {
	/* Owned by thread.c. */
	tid_t tid;                          /* Thread identifier. */
	enum thread_status status;          /* Thread state. */
	char name[16];                      /* Name (for debugging purposes). */
	int priority;                       /* Priority. */

	/* Shared between thread.c and synch.c. */
	struct list_elem elem;              /* List element. */
    int64_t sleep_until; // 추가된 부분   /* Time to wake up(Ticks)*/

#ifdef USERPROG
	/* Owned by userprog/process.c. */
	uint64_t *pml4;                     /* Page map level 4 */
#endif
#ifdef VM
	/* Table for whole virtual memory owned by thread. */
	struct supplemental_page_table spt;
#endif

	/* Owned by thread.c. */
	struct intr_frame tf;               /* Information for switching */
	unsigned magic;                     /* Detects stack overflow. */
};

코드는 핀토스에서 사용하는 스레드 정보 구조체이다.
sleep_until을 새로운 멤버로 추가하여 스레드가 깨어날 시간(틱)을 저장하도록 하였다.
이 스레드 정보 구조체에는 리스트를 통해서 접근할 수 있기 때문에 리스트 요소(elem) 포인터를 sleep_until에 대한 포인터로 변환해 접근해야 한다.
방법으로는 직접 elem에서 정해진 바이트 수 만큼을 이동하는 방식과 구조체의 포인터를 획득해 ->연산자로 접근하는 방식을 생각할 수 있다.

// 방법 1
struct list_elem_thread {
	struct list_elem *prev;     /* Previous list element. */
    struct list_elem *next;     /* Next list element. */
    int64_t sleep_until;        /* 순서는 struct thread에서와 같아야 한다 */
}
((struct list_elem *)elem)->sleep_until;

// 방법 2
(uint8_t *)elem + offset        /* offset은 여기서 16(바이트) */

// 방법 3
list_entry(elem, struct thread, elem)->sleep_until;
// list_entry(LIST_ELEM, STRUCT, MEMBER)는 (STRUCT *) 자료형의 MEMBER 멤버인  LIST_ELEM을 받아서 STRUCT 포인터를 계산하는 매크로이다.

방법 1, 방법 3같은 경우에는 나중에 구조체에 멤버를 추가할 경우에 불편해질 것 같아서 범용적으로 쓸 수 있을 것 같은 방법 2를 사용했다.

1-1-3-2. 잠든 스레드 리스트

스레드 구조체에는 대기열 리스트ready_list에 연결하기 위한 포인터 구조체인 멤버 elem이 있다.
sleep에 들어가는 경우에는 ready_list에서 빠지게 되므로 이 elem을 다른 리스트에 사용할 수 있다.
전역변수 struct list sleep_list를 만들어서 sleep에 들어간 스레드들을 리스트로 관리할 수 있다.

1-2. Priority Scheduling

요구사항을 요약하면 다음과 같다.
1. 우선순위에 변동이 있을 때 필요하다면 즉시 문맥전환이 일어나야 한다.
2. 우선순위 역전 현상을 방지해야 한다.

1-2-1. 대기열 우선순위 정렬

문맥 전환 시스템 콜 schedule은 스레드 대기열 ready_list에서 다음으로 실행할 스레드를 가져와next_thread_to_run() 해당 스레드의 구조체에서 레지스터, 스택 포인터 정보를 읽어들인다.
우선순위를 기준으로 다음 스레드를 가져오려면
1. 우선순위를 기준으로 삽입해두고 첫 스레드를 가져오거나 (삽입 O(N), 삭제 O(1))
2. 삽입은 순서없이 하고 스레드를 가져올 때 리스트를 탐색하는 방식(삽입 O(1), 삭제 O(N))
을 떠올릴 수 있다.
다만 뒤에서 구현할 우선순위 기부로 인해 우선순위가 변경될 경우를 대비하여 2로 구현하는 것이 낫다.

1-2-2. 우선순위 역전(우선순위 변경, 스레드 생성 시)

우선순위 역전이란 우선순위 스케줄링에서 낮은 우선순위를 가진 스레드가 마치 높은 우선순위를 가진 스레드처럼 스케줄링되는 현상을 의미한다.
이것은 더 낮은 우선순위를 가진 스레드가 락(뮤텍스)을 가지고있고(holding) 높은 우선순위 스레드가 이를 필요로 하여 block될 때 발생한다.

예를 들어 서로 다른 우선순위를 가진 스레드 3개를 우선순위가 높은 순으로 각 H, M, L이라고 하자.
우선순위 스케줄링에서는 H가 먼저 CPU를 점유해야 한다.
그러나 L이 가진 락을 H가 필요로 하게 되면 H는 락이 해제될 때까지 실행을 멈추게 된다.
그러면 다음으로 높은 우선순위를 가진 M이 먼저 CPU를 점유하게 된다.
H는 M이 작업을 끝내고 L이 CPU를 점유하여 락을 해제한 이후에야 CPU를 점유할 수 있게 되므로, 사실상 M이 H보다 높은 우선순위를 가진 것처럼 행동하게 된다.

우선순위 역전을 해결하기 위해서 핀토스에서 우선순위 기부(donate)를 구현해야 한다.

위의 예시에선 H가 L이 가진 락을 요구하는 때 H의 우선순위를 임시로 L에 부여한다.
L로 문맥 전환이 일어나고 L이 락을 해제하는 순간 L의 우선순위는 원래대로 돌아가고,
H로 다시 문맥 전환이 일어난다.

이 과제의 어려운 점은 우선순위 기부가 연쇄적으로 일어날 수 있다는 것이다.
연쇄적 기부를 다루기 간편한 방법은 또다른 리스트를 만들어 관리하는 것이다.

한 스레드가 여러 개의 락을 동시에 요구하는 경우나 우선순위가 낮은 스레드가 우선순위가 더 높은 스레드에 기부하는(또는 기부해야 하는 지를 판단해야 하는) 경우는 절대 일어나지 않는다.
이런 우선순위 기부를 구현한 스케줄러의 특성을 잘 이해하지 않고 시작한다면 많이 헤맬 수 있다.
즉, 바로 코드로 뛰어드는 경우에도 자신이 어떤 것을 구현해야 하는지를 정확하게 인식하고 있어야한다.

1-2-3. 세마포어 리스트 정렬

세마포어 waiting 스레드 목록에 우선순위 내림차순으로 삽입하면 끝난다.
그런데 테스트 코드를 실행하면 약간의 버그가 있었다.
아래는 테스트 코드이다.

/* Tests that the highest-priority thread waiting on a semaphore
   is the first to wake up. */

#include <stdio.h>
#include "tests/threads/tests.h"
#include "threads/init.h"
#include "threads/malloc.h"
#include "threads/synch.h"
#include "threads/thread.h"
#include "devices/timer.h"

static thread_func priority_sema_thread;
static struct semaphore sema;

void
test_priority_sema (void) 
{
  int i;
  
  /* This test does not work with the MLFQS. */
  ASSERT (!thread_mlfqs);

  sema_init (&sema, 0);
  thread_set_priority (PRI_MIN);
  for (i = 0; i < 10; i++) 
    {
      int priority = PRI_DEFAULT - (i + 3) % 10 - 1;
      char name[16];
      snprintf (name, sizeof name, "priority %d", priority);
      thread_create (name, priority, priority_sema_thread, NULL);
    }

  for (i = 0; i < 10; i++) 
    {
      sema_up (&sema);
      msg ("Back in main thread."); 
    }
}

static void
priority_sema_thread (void *aux UNUSED) 
{
  sema_down (&sema);
  msg ("Thread %s woke up.", thread_name ());
}

테스트 코드는 세마포어를 0으로 초기화하고(sema_init (&sema, 0);) 여러 우선순위를 가진 스레드를 생성한다.
새로 생성된 스레드는 모두 메인 스레드보다 우선순위가 높기 때문에 생성 즉시 실행되지만 세마포어를 요구하기 때문에 대기하게 된다(sema_down (&sema);).
스레드 10개를 모두 생성 후 세마포어를 10번 up하며 스레드를 모두 깨우게 된다.

아래는 버그가 있는 실행 결과이다.

(priority-sema) begin
(priority-sema) Back in main thread.
(priority-sema) Thread priority 30 woke up.
(priority-sema) Back in main thread.
(priority-sema) Thread priority 29 woke up.
(priority-sema) Back in main thread.
(priority-sema) Thread priority 28 woke up.
(priority-sema) Back in main thread.
(priority-sema) Thread priority 27 woke up.
(priority-sema) Back in main thread.
(priority-sema) Thread priority 26 woke up.
(priority-sema) Back in main thread.
(priority-sema) Thread priority 25 woke up.
(priority-sema) Back in main thread.
(priority-sema) Thread priority 24 woke up.
(priority-sema) Back in main thread.
(priority-sema) Thread priority 23 woke up.
(priority-sema) Back in main thread.
(priority-sema) Thread priority 22 woke up.
(priority-sema) Back in main thread.
(priority-sema) end

순서대로는 깨어나는 듯 한데 Back in main thread.가 먼저 출력된다.
sema_up을 하면 즉시 스레드가 깨어나서 woke up을 출력해야 하는 것이 정상이다.
즉, sema_up에서 문제가 발생했다는 뜻이다.

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

	ASSERT (sema != NULL);

	old_level = intr_disable ();

	if (!list_empty (&sema->waiters))
		thread_unblock (list_entry (list_pop_front (&sema->waiters),
					struct thread, elem));
	sema->value++;

	intr_set_level (old_level);
}

thread_unblock으로 스레드를 깨운 다음에 semaphore 값을 1로 바꾸고 있다.
이러면 깨어난 스레드는 semaphore가 0인 것을 확인하고 다시 잠들게 된다.
이래서 두 번째 루프부터 스레드가 깨어나기 시작한 것이고 한 스레드가 적게 깨어났던 것이다.

해결 방법은 두 가지를 생각할 수 있다.

  1. sema->value++;구문을 unblock 전에 실행하게 한다.
  2. thread_unblock에 통합시켰던 높은 우선순위에 양보(선점)하는 작업을 분리한다.

unblock을 사용하는 모든 동작에 선점 작업을 시키려고 unblock에 합쳐놓았던 것인데,
한 함수는 하나의 작업만 해야하는 것이 좋다는 말을 떠올리면 분리하여 작업을 명시하는 것이 더 나아보인다.

아래는 수정을 하고난 뒤의 정상적인 실행 결과이다.

(priority-sema) begin
(priority-sema) Thread priority 30 woke up.
(priority-sema) Back in main thread.
(priority-sema) Thread priority 29 woke up.
(priority-sema) Back in main thread.
(priority-sema) Thread priority 28 woke up.
(priority-sema) Back in main thread.
(priority-sema) Thread priority 27 woke up.
(priority-sema) Back in main thread.
(priority-sema) Thread priority 26 woke up.
(priority-sema) Back in main thread.
(priority-sema) Thread priority 25 woke up.
(priority-sema) Back in main thread.
(priority-sema) Thread priority 24 woke up.
(priority-sema) Back in main thread.
(priority-sema) Thread priority 23 woke up.
(priority-sema) Back in main thread.
(priority-sema) Thread priority 22 woke up.
(priority-sema) Back in main thread.
(priority-sema) Thread priority 21 woke up.
(priority-sema) Back in main thread.
(priority-sema) end

1-2-4. Conditional variable

모니터, 또는 Conditional Variable이라고도 불리는 변수는 락(뮤텍스)에 조건을 결합한 구조를 가진다.
조건을 만족하게되면 락이 해제된다.
condition-대기하고 있는 스레드들은 각자의 waiter세마포어를 가지기 때문에 하나의 리스트에 연결되어 있지 않다.
따라서 세마포어에서처럼 리스트를 순회하며 가장 우선순위가 높은 스레드를 찾아 깨우는 방식이 불가능해 진다.

1-3. Advanced Scheduling

우선순위 스케줄러도 기아 문제 등으로부터 완전히 자유롭지 않다.
따라서 현대의 스케줄러들은 보통 피드백을 통해 오랫동안 대기 상태로 있게되면 우선순위가 상승하여 기아문제를 방지한다.
대표적으로 MLFQS(Multi-Level Feedback Queue Scheduler)가 있다.
MLFQS는 다단계로 구성된 대기열(우선순위로 봐도 무방)로 구성되며 동일한 대기열에 있는 스레드들은 RR방식으로 스케줄링된다.

고정 소수점 계산법
그냥 정수를 2의 n제곱으로 나눈 수를 저장한다.

profile
알을 깬 개발자

0개의 댓글