[PintOS] Project 1 : Thread - Alarm Clock

CorinBeom·2025년 5월 9일

OS jungle pintos

PintOS

목록 보기

1/19

이제 핀토스 주간으로 들어왔다. 커리큘럼 중 제일 중요한 부분이라고 많이 이야기를 들어서 공을 많이 들일 생각이다
우선 첫 번째 과제인 Thread부터 들어가보자

무엇을 해야하는가 (전체적인 관점)

이번 과제에서는 최소한의 기능을 갖춘 스레드 시스템을 제공해준다.
여기서 내가 해야할 것은 이 시스템의 기능을 확장하는 것이다.
좀 더 디테일하게 순서대로 얘기해보자면

Alarm Clock 구현 (기존 방식 개선)

Priority Scheduler 구현
2-1. Priority Donation 구현

Advanced Scheduler 구현

이 세 단계는 독립적인 과제가 아니라, "스레드가 어떻게 선택되고, 실행되고, 양보되는가"를 순차적으로 확장해나가는 과정이다.

현재 기능의 문제점

Busy-Waiting 방식 :

특정 조건이 충족될 때 까지 조건이 만족될 때까지 루프를 돌며 thread를 자발적으로 양보 (yield)하는 방식
CPU 자원을 낭비하고, 다른 스레드가 실행될 기회를 줄여서 성능이 저하될 수 있음

무엇을 해야하는가 (Project 1 : Alarm Clock 관점)

우리는 우선적으로 앞서 얘기한 Busy-Waiting을 Sleep and WakeUp으로 전환하는 작업을 해야한다.

Sleep and WakeUP 방식 :

현재 tick에 + 일정 tick을 더한 시점까지 thread를 BLOCKED 상태로 대기시키고, 그 시간이 되면 READY 상태로 복귀시킨다.
대기 상태에 들어간 동안은 CPU 사이클을 사용하지 않기 때문에, 위에서 얘기한 Busy-Waiting 방식에 비해 CPU 자원을 아낄 수 있다

우리가 구현할 기능 (우구기)

`thread_init(void)` 에서 `sleep_list` 초기화

thread_init(void) {
	...
    list_init (&ready_list);
	list_init (&sleep_list); // sleep_list 초기화
    ...
 }

`thread_sleep(int64_t wakeup_tick)`

📌 책임: 현재 thread를 BLOCKED 상태로 만들고, 깨울 시점을 기록하여 sleep_list에 삽입

현재 실행중인 thread를 BLOCKED 상태로 만들고
wakeup_tick 값을 저장한 뒤
sleep_list 에 오름차순 정렬되도록 삽입

`thread_wakeup(int64_t current_tick)`

📌 책임: 깰 시점이 된 thread들을 찾아 READY 상태로 바꾸고, ready_list에 넣음

매 tick마다 호출됨 (timer_interrupt() 내부)
sleep_list 에서 wakeup_tick <= current_tick 인 thread들을 찾아서 :
- thread_unblock() 을 통해 READY 상태로 전환
- 리스트에서 제거

`timer_interrupt()`

매 tick마다 실행되는 interrupt handler
내부에서 thread_tick() 호출 외에도
thread_wakeup(ticks) 호출해서 깨어날 thread 처리

`struct thread` 에 필드 추가

int64_t wakeup_tick;

`bool cmp_thread_ticks(const struct list_elem a, const struct list_elem b, void *aux)`

list_insert_ordered() 에서 사용되는 비교 함수
두 thread의 wakeup_tick 값을 비교해서
- 더 빠른 tick이 앞에 오도록 오름차순 정렬

구현 하기 전 알아두면 좋을 내용

PintOS는 Zero부터 시작하는 과제가 아님을 알아야한다.
PintOS의 함수는 단순 도우미가 아니라, 해당 시스템의 철학이 녹아있는 구성 요소다.
따라서 하나하나를 무작정 호출하는 것이 아니라, 언제 어떤 함수가 어떤 책임을 갖고 실행되는지를 파악해야 내가 전체 시스템의 흐름을 이해할 수 있다.
또한 Pintos를 잘 다루기 위해선, "내가 추가하는 기능이 기존 흐름을 어떻게 바꾸는가?"를 계속 질문하는 태도가 필요하다.
기존 함수에 대한 이해도가 있냐 없냐에 따라 코드 작성시에도 그렇고 본인이 먹을 수 있는 경험치의 양이 달라진다.
본인의 경우는 다른 블로그를 참고하며 코드를 작성하여 이 부분을 개선해야겠다고 생각했다.

구현 시작 전 흐름 정리

1. 사용자가 thread를 잠재운다 
- 사용자가 timer_sleep(ticks) 호출
- → 현재 tick + ticks = wakeup_tick 계산
- → thread는 BLOCKED 상태로 전환 + sleep_list에 넣음

2. 매 tick마다 인터럽트 발생
- timer_interrupt()가 매 tick마다 실행됨
- 이 안에서 sleep_list를 확인

3. 깨울 시점 확인
- sleep_list를 앞에서부터 검사
- wakeup_tick <= 현재 tick 인 thread는 꺼낸다

4. thread를 꺠움
- thread_unblock() 호출 → 상태를 READY로 변경
- ready_list에 넣는다

5. 스케줄러가 다시 실행함
- 준비된 thread 중 하나가 스케줄링되어 실행됨

sleep_list는 오름차순 정렬되므로, wakeup_tick이 현재 tick보다 큰 thread를 만나면 그 뒤는 모두 pass 가능

`thread_sleep(int64_t wakeup_tick)`

thread_sleep(int64_t wakeup_tick) 전체코드

void thread_sleep(int64_t ticks) {
	struct thread *curr;
	enum intr_level old_level;
	old_level = intr_disable();  // 인터럽트 비활성

	curr = thread_current();	 // 현재 스레드
	ASSERT(curr != idle_thread); // 현재 스레드가 idle이 아닐때만

	curr->wakeup_tick = ticks;	 // 일어날 시각 저장

	list_insert_ordered(&sleep_list, &curr->elem, cmp_thread_ticks, NULL);  // sleep_list에 추가
	thread_block();	// 현재 스레드 재우기

	intr_set_level(old_level);  // 인터럽트 상태를 원래 상태로 변경
}

curr : 현재 실행 중인 스레드 포인터
intr_disable() :
- sleep_list는 공유 자원이므로 인터럽트 핸들러가 건드릴 수도 있음
- thread_wakeup() 도 sleep_list를 접근하므로 동기화 필요
- 그래서 인터럽트를 잠깐 꺼서 atomic하게 만들고, 원래 상태를 old_level에 저장

curr = thread_current();

현재 CPU를 점유하고 있는 Thread의 정보를 가져온다
이 Thread를 BLOCKED 상태로 만들고 sleep_list에 넣는 게 목적임

ASSERT(curr != idle_thread);

idle Thread는 절대 BLOCK되면 안됨 !!
idle Thread까지 자면 CPU가 돌릴 Thread가 사라져서 커널이 정지됨
안정성 확보용 방어 코드

curr->wakeup_tick = ticks;

thread 구조체 안에 int64_t wakeup_tick 필드를 추가했다고 가정 (실제로 구현해야함)
나중에 thread_wakeup() 에서 이 값을 비교해서 꺨 조건으로 사용

list_insert_ordered(&sleep_list, &curr->elem, cmp_thread_ticks, NULL);

sleep_list 는 BLOCKED 상태인 Thread들의 리스트
wakeup_tick 기준으로 오름차순 정렬된 상태를 유지. 조건 만족하는 Thread만 빠르게 탐색이 가능해짐
cmp_thread_ticks() 는 비교 함수이다. 둘 중 wakeup_tick이 작은 애가 먼저 오도록 한다 (구현 예정)

thread_block();

BLOCKED 상태로 상태전환 → 스케줄러 대상에서 제외됨
이 시점에서 Context Switch 발생이 가능하다
즉, 이 코드를 실행한 Thread는 이 함수 호출 이후에 실행되지 않음 (다름 Thread로 전환)

intr_set_level(old_level);

공유 자원 접근이 끝났으니, 이전 interrupt 상태로 복원
예전 상태가 INTR_ON 이면 다시 활성화됨

단계별로 보기

인터럽트 잠금
현재 스레드 확인
idle thread 방지
깨울 시점 설정
sleep_list에 삽입
thread_block()
이전 인터럽트 상태로 복원

`thread_wakeup(int64_t current_ticks)`

전체코드

void thread_wakeup(int64_t current_ticks) {
	enum intr_level old_level;
	old_level = intr_disable();

	struct list_elem *curr_elem = list_begin(&sleep_list);
	while (curr_elem != list_end(&sleep_list)) {
		struct thread *curr_thread = list_entry(curr_elem, struct thread, elem);

		if (current_ticks >= curr_thread->wakeup_tick) {
			curr_elem = list_remove(curr_elem);
			thread_unblock(curr_thread);
		}
		else break;
	}
	intr_set_level(old_level);
}

intr_disable() : 위 설명과 동일

struct list_elem *curr_elem = list_begin(&sleep_lsit);
while (curr_elem != list_end(&sleep_lsit) {
	struct thread *curr_thread = list_entry(curr_elem, struct thread, elem);

sleep_list를 돌면서 하나씩 꺼냄
curr_elem 은 list_elem의 포인터임
list_enrty : 존나 중요함
- ```
#define list_entry(LIST_ELEM_PTR, STRUCT, MEMBER) \
	 ((STRUCT *) ((uint8_t *) &(LIST_ELEM_PTR)->next - offsetof(STRUCT, MEMBER.next)))
```
- list_elem의 포인터를 원래 구조체 포인터로 되돌리는 매크로임
- 즉, struct thread 구조체에 list_elem elem이 포함돼 있다고 할 때,
- elem의 포인터만 가지고 있으면 다시 struct thread*로 되돌릴 수 있음

if (current_ticks >= curr_thread->wakeup_tick) {
	curr_elem = list_remove(curr_elem);
    thread_unblock(curr_thread);
}
else break;

조건 만족하면 thread_unblock() 해서 ready_list로 이동
아니라면 sleep_list는 오름차순 정렬이므로 break

`bool cmp_thread_ticks(const struct list_elem a, const struct list_elem b, void *aux)`

전체 코드

bool cmp_thread_ticks (const struct list_elem *a, const struct list_elem *b, void *aux UNUSED) {
	struct thread *st_a = list_entry(a, struct thread, elem);
	struct thread *st_b = list_entry(b, struct thread, elem);
	return st_a->wakeup_tick < st_b->wakeup_tick;
}

list_entry()로 list_elem 포인터를 다시 struct thread* 로 역참조
즉, sleep_list 에 &thread->elem 이 들어가 있었으므로
→ elem 의 위치로부터 다시 thread 전체 구조체 주소를 계산해냄

return st_a->wakeup_tick < st_b->wakeup_tick;

두 Thread의 wakeup_tick 을 비교해서
a가 더 먼저 깨어나야 한다면 true 반환
→ a가 b보다 앞에 오도록 list가 정렬됨 (오름차순 정렬

인자값에 aux 라는 생소한 친구가 보일 것이다. 어셈블리 공부할 때 종종 봤던 아이같아서 어떤 용도로 쓰이는건지 궁금해졌다

지피티에게 물어보니...

나중에 priority를 구현하거나 기존 코드에 고도화 작업을 할 때 사용하는 값인 듯 하다.

`timer_interrupt()`

전체 코드

static void
timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_tick ();
	thread_wakeup(ticks);
}

타이머 하드웨어가 주기적으로 발생시키는 인터럽트의 핸들러 함수
인터럽트 컨텍스트에서 실행되며, 현재 실행 중인 스레드 문맥을 중단시킴
args 는 인터럽트 프레임 정보인데 여기선 안 쓰므로 UNUSED 처리 (아까 aux랑 비슷한 느낌인듯)

ticks++;

전체 시스템에서 흐르는 시간(전역 tick 수)를 증가시킴
이 값이 바로 thread_wakeup에 쓰이는 현재 tick임 (current_ticks)

thread_tick();

현재 실행 중인 Thread의 CPU 사용 시간을 accounting
스레드 스케줄링 관련 통계를 갱신
→ Advanced Scheduler 구현할 때 여기에서 우선순위 계산 등 사용됨

thread_wakeup(ticks);

우리가 구현한 Alarm Clock의 핵심 호출
sleep_list 를 순회하며 wakeup_tick <= ticks 인 Thread 들을 READY 상태로 복귀시킴
그 결과로 준비된 Thread가 ready_list에 올라감.

마무리

Alarm Clock 전체 흐름 정리하자면

thread_sleep()으로 BLOCKED → sleep_list 등록
매 tick마다 timer_interrupt() → thread_wakeup(ticks)
조건 만족하면 thread_unblock() → ready_list 등록
스케줄러가 우선순위 비교 후 문맥 전환 시점 결정

P.S

ready_list, sleep_list, running 이런 개념들이 헷갈릴 수 있다.
축구를 좋아하는 본인으로서 생각을 해본 결과

ready_list : 실행중이진 않지만 실행 가능한 대기 상태
- 이거 완전 축구 벤치멤버 아님? 지피티에게 물어보니 아주 적절한 비유란다
sleep_list : BLOCKED 상태의 스레드 리스트
- 명단 제외, 경기장 밖에 있는 선수 (누가 떠오르지만 말을 아끼겠음)
running : CPU를 점유하고 있는 스레드 or 프로세스
- 선발로 뛰고있는 선수

CorinBeom

Before Sunrise

다음 포스트

[PintOS] Project 1 : Thread - Alarm Clock

PintOS

무엇을 해야하는가 (전체적인 관점)

현재 기능의 문제점

Busy-Waiting 방식 :

특정 조건이 충족될 때 까지 조건이 만족될 때까지 루프를 돌며 thread를 자발적으로 양보 (yield)하는 방식

CPU 자원을 낭비하고, 다른 스레드가 실행될 기회를 줄여서 성능이 저하될 수 있음

무엇을 해야하는가 (Project 1 : Alarm Clock 관점)

Sleep and WakeUP 방식 :

현재 tick에 + 일정 tick을 더한 시점까지 thread를 BLOCKED 상태로 대기시키고, 그 시간이 되면 READY 상태로 복귀시킨다.

대기 상태에 들어간 동안은 CPU 사이클을 사용하지 않기 때문에, 위에서 얘기한 Busy-Waiting 방식에 비해 CPU 자원을 아낄 수 있다

우리가 구현할 기능 (우구기)

`thread_init(void)` 에서 `sleep_list` 초기화

`thread_sleep(int64_t wakeup_tick)`

`thread_wakeup(int64_t current_tick)`

`timer_interrupt()`

`struct thread` 에 필드 추가

`bool cmp_thread_ticks(const struct list_elem a, const struct list_elem b, void *aux)`

구현 하기 전 알아두면 좋을 내용

구현 시작 전 흐름 정리

`thread_sleep(int64_t wakeup_tick)`

단계별로 보기

`thread_wakeup(int64_t current_ticks)`

`bool cmp_thread_ticks(const struct list_elem a, const struct list_elem b, void *aux)`

`timer_interrupt()`

마무리

Alarm Clock 전체 흐름 정리하자면

P.S

[PintOS] project 1 : Thread - Priority Scheduler

0개의 댓글

[PintOS] Project 1 : Thread - Alarm Clock

PintOS

무엇을 해야하는가 (전체적인 관점)

현재 기능의 문제점

Busy-Waiting 방식 :

특정 조건이 충족될 때 까지 조건이 만족될 때까지 루프를 돌며 thread를 자발적으로 양보 (yield)하는 방식

CPU 자원을 낭비하고, 다른 스레드가 실행될 기회를 줄여서 성능이 저하될 수 있음

무엇을 해야하는가 (Project 1 : Alarm Clock 관점)

Sleep and WakeUP 방식 :

현재 tick에 + 일정 tick을 더한 시점까지 thread를 BLOCKED 상태로 대기시키고, 그 시간이 되면 READY 상태로 복귀시킨다.

대기 상태에 들어간 동안은 CPU 사이클을 사용하지 않기 때문에, 위에서 얘기한 Busy-Waiting 방식에 비해 CPU 자원을 아낄 수 있다

우리가 구현할 기능 (우구기)

thread_init(void) 에서 sleep_list 초기화

thread_sleep(int64_t wakeup_tick)

thread_wakeup(int64_t current_tick)

timer_interrupt()

struct thread 에 필드 추가

bool cmp_thread_ticks(const struct list_elem *a, const struct list_elem *b, void *aux)

구현 하기 전 알아두면 좋을 내용

구현 시작 전 흐름 정리

thread_sleep(int64_t wakeup_tick)

단계별로 보기

thread_wakeup(int64_t current_ticks)

bool cmp_thread_ticks(const struct list_elem *a, const struct list_elem *b, void *aux)

timer_interrupt()

마무리

Alarm Clock 전체 흐름 정리하자면

P.S

[PintOS] project 1 : Thread - Priority Scheduler

0개의 댓글

`thread_init(void)` 에서 `sleep_list` 초기화

`thread_sleep(int64_t wakeup_tick)`

`thread_wakeup(int64_t current_tick)`

`timer_interrupt()`

`struct thread` 에 필드 추가

`bool cmp_thread_ticks(const struct list_elem a, const struct list_elem b, void *aux)`

`thread_sleep(int64_t wakeup_tick)`

`thread_wakeup(int64_t current_ticks)`

`bool cmp_thread_ticks(const struct list_elem a, const struct list_elem b, void *aux)`

`timer_interrupt()`