[pintos] 1주차 - Alarm Clock 코드 정리

정글/Pintos

[pintos] 1주차 - Alarm Clock 코드 정리

nkdev 2025. 5. 20. 15:52

📍 함수 정리

thread_start()

pintos-kaist/threads/thread.c

인터럽트를 활성화하여 선점형 스레드 스케줄링을 시작함
idle 스레드를 만듦

/* Starts preemptive thread scheduling by enabling interrupts.
   Also creates the idle thread. */
void
thread_start (void) {
	/* Create the idle thread. */
	struct semaphore idle_started;
	sema_init (&idle_started, 0);
	thread_create ("idle", PRI_MIN, idle, &idle_started);

	/* Start preemptive thread scheduling. */
	intr_enable ();

	/* Wait for the idle thread to initialize idle_thread. */
	sema_down (&idle_started);
}

timer_init()

pintos-kaist/devices/timer.c

타이머를 설정하고 타이머 인터럽트 핸들러를 등록하는 함수

/* Sets up the 8254 Programmable Interval Timer (PIT) to
   interrupt PIT_FREQ times per second, and registers the
   corresponding interrupt. */
void
timer_init (void) {
	/* 8254 input frequency divided by TIMER_FREQ, rounded to
	   nearest. */
	uint16_t count = (1193180 + TIMER_FREQ / 2) / TIMER_FREQ;

	outb (0x43, 0x34);    /* CW: counter 0, LSB then MSB, mode 2, binary. */
	outb (0x40, count & 0xff);
	outb (0x40, count >> 8);

	intr_register_ext (0x20, timer_interrupt, "8254 Timer");
}

👉🏼 intr_register_ext()함수로 인터럽트 백터 0x20에 timer_interrupt 핸들러를 등록한다.

→ 설정된 주기 간격으로 하드웨어 타이머가 인터럽트를 발생시키고, 그 때 마다 등록한 핸들러(timer_interrupt()함수)가 호출됨

timer_interrupt()

pintos-kaist/devices/timer.c

tick이 지날 때마다 호출되는 인터럽트 핸들러
thread_tick()을 호출하여 스케줄링 타이밍을 체크

/* Timer interrupt handler. */
static void
timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_tick ();
}

👉🏼 ticks 변수는 시스템이 부팅된 이후 경과한 tick 수

thread_tick() 함수는 현재 실행 중인 스레드의 tick 수를 증가시키고, 필요 시 스케줄링을 트리거한다.

thread_tick()

pintos-kaist/threads/thread.c

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++;

	/* Enforce preemption. */
	if (++thread_ticks >= TIME_SLICE)
		intr_yield_on_return ();
}

👉🏼

현재 실행 중인 스레드의 구조체를 struct thread* t에 저장
현재 스레드의 종류에 맞는 tick 수를 증가시키기
- 현재 실행 중인 스레드가 없으면 idle_ticks++
- 유저모드이면 user_ticks++
- 커널모드이면 kernel_ticks++
- 경우에 따라 tick을 나눠서 증가시키는 이유 : OS가 cpu 시간을 누가 어떤 용도로 썼는지 추적할 수 있게 하기 위해 → 과제 1의 alarm clock을 구현할 때는 쓰이지 않는 변수
현재 실행 중인 스레드의 tick수(thread_ticks 변수)를 1 올려주고, 그 값이 TIME_SLICE값에 도달하면
- 스케줄러가 강제로 yield를 호출하여 다른 스레드로 전환
- 현재 Round Robin이므로 thread_ticks가 TIME_SLICE값과 같아지면 yield를 호출한다.
- yield : 스레드가 자발적으로 cpu를 양보하고 스케줄러에게 제어권을 넘기는 것
- thread_ticks : 스레드가 마지막으로 yield한 이후부터 경과한 tick 수
- TIME_SLICE : 한 스레드가 cpu를 점유할 수 있는 최대 시간
- intr_yield_on_return()을 호출하여 인터럽트 핸들러가 반환되기 직전에 스케줄링이 이루어지도록 한다. </aside>

intr_yield_on_return()

pintos-kaist/threads/interrupt.c

외부 인터럽트를 처리하는 동안 인터럽트 핸들러가 처리를 다 마치고 복귀하기 직전에 다른 프로세스에게 cpu를 양보하도록 지시함
인터럽트 핸들러가 반환되기 직전에 thread_yield()를 호출하도록 설정 → 현재 스레드가 cpu를 양보하고 스케줄러가 다음 실행할 스레드를 선택하게 함

/* During processing of an external interrupt, directs the
   interrupt handler to yield to a new process just before
   returning from the interrupt.  May not be called at any other
   time. */
void
intr_yield_on_return (void) {
	ASSERT (intr_context ());
	yield_on_return = true;
}

👉🏼 interrupt.c의 yield_on_return 플래그값을 true로 바꿔줌

🤔 yield_on_return 플래그를 true로 만들기만 했는데 어떻게 인터럽트 종료 직전에 thread_yield가 실행되도록 하나?

→ Pintos에서 모든 인터럽트는 interrupt.c에 있는 공통 핸들러를 거친다. (몰라도 되는 부분인듯해서 넘어가기)

thread_yield()

pintos-kaist/devices/timer.c

/* Yields the CPU.  The current thread is not put to sleep and
   may be scheduled again immediately at the scheduler's whim. */
void
thread_yield (void) {
	struct thread *curr = thread_current ();
	enum intr_level old_level;

	ASSERT (!intr_context ());

	old_level = intr_disable ();
	if (curr != idle_thread)
		list_push_back (&ready_list, &curr->elem);
	do_schedule (THREAD_READY);
	intr_set_level (old_level);
}

thread_ticks 변수

pintos-kaist/devices/timer.c

현재 실행 중인 스레드가 cpu를 점유한 이후 경과한 tick 수

/* Scheduling. */
#define TIME_SLICE 4            /* # of timer ticks to give each thread. */
static unsigned thread_ticks;   /* # of timer ticks since last yield. */

👉🏼

TIME_SLICE : 각 스레드에게 주어진 최대 tick수 (각 스레드의 최대 cpu 사용 시간)

thread_ticks : 가장 최근에 cpu 점유한 이후로부터 경과한 tick수

ticks 변수

pintos-kaist/devices/timer.c

컴퓨터가 켜지고 나서 OS가 초기화된 이후부터 발생한 tick 수
timer.c의 전역변수로, 시스템 전체에서 경과한 tick 수를 의미
타이머 인터럽트가 한 번 발생할 때마다 ticks++

/* Number of timer ticks since OS booted. */
static int64_t ticks;

👉🏼

현재까지 경과한 전체 tick수

timer_ticks()로 접근 가능

timer_sleep()에서 현재 시간 + 대기 시간 = 깨어나야 할 시간으로 사용됨

timer_ticks()

pintos-kaist/devices/timer.c

OS가 부팅된 이후부터 지금까지 얼마나 많은 tick이 발생했는지 반환하는 함수

/* Returns the number of timer ticks since the OS booted. */
int64_t
timer_ticks (void) {
	enum intr_level old_level = intr_disable ();
	int64_t t = ticks;
	intr_set_level (old_level);
	barrier ();
	return t;
}

👉🏼 ticks를 t에 저장하고 t를 리턴하는데 그 이전과 이후에 먼가 처리를 해놨는데 머하는건진 잘 모르겠음

real_time_sleep()

pintos-kaist/devices/timer.c

num/denom sec 만큼 sleep한다.

/* Sleep for approximately NUM/DENOM seconds. */
static void
real_time_sleep (int64_t num, int32_t denom) {
	/* Convert NUM/DENOM seconds into timer ticks, rounding down.

	   (NUM / DENOM) s
	   ---------------------- = NUM * TIMER_FREQ / DENOM ticks.
	   1 s / TIMER_FREQ ticks
	   */
	int64_t ticks = num * TIMER_FREQ / denom;

	ASSERT (intr_get_level () == INTR_ON);
	if (ticks > 0) {
		/* We're waiting for at least one full timer tick.  Use
		   timer_sleep() because it will yield the CPU to other
		   processes. */
		timer_sleep (ticks);
	} else {
		/* Otherwise, use a busy-wait loop for more accurate
		   sub-tick timing.  We scale the numerator and denominator
		   down by 1000 to avoid the possibility of overflow. */
		ASSERT (denom % 1000 == 0);
		busy_wait (loops_per_tick * num / 1000 * TIMER_FREQ / (denom / 1000));
	}
}

👉🏼

인자로 받은 num, denom값을 사용해 ticks = num * TIMER_FREQ / denom를 구함
ticks만큼 지났다면 timer_sleep()를 통해 현재 스레드가 자발적으로 cpu를 양보하게 만든다.
그렇지 않으면 busy-wait() 실행

timer_sleep()

pintos-kaist/devices/timer.c

약 ticks만큼 지날 때까지 실행을 미룬다.
tick이 모두 지날 때까지 cpu를 점유하고 있으므로 busy waiting 발생

/* 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 ();
}

👉🏼

인자값으로 sleep 상태로 유지되어야 할 시간을 받는다.
start 변수에 현재 시점에 시스템 전체적으로 tick이 얼마나 지났는지 저장한다.
- timer_ticks()를 통해 시스템 전체 tick수를 리턴받을 수 있음
timer_elapsed(start) < ticks
- timer_elapsed(start)는 start시점으로부터 현재까지 얼마나 시간이 지났는지 알려주는 함수이다.
- 경과한 시간이 아직 ticks에 도달하지 않았다면 thread_yield()를 호출해 cpu를 양보한다.

정리:

while문으로 아직 지정된 sleep 시간 만큼 (ticks 만큼) 지났는지 확인하기를 반복하는데, 아직 지정된 sleep 시간이 안 지났으면 thread_yield()를 호출하여 현재 스레드를 레디 상태로 전환시켜 (레디큐에 넣어) cpu를 양보하고 다른 스레드가 먼저 실행되게 한다. 그리고 나중에 레디큐에 있던 본인이 스케줄링되어 cpu를 점유하면 점유하는 동안 다시 또 while문으로 아직 지정된 sleep시간만큼 지났는지 확인하여 똑같은 작업을 반복한다. 즉 쉬는 척하면서 cpu를 계속 차지하거나 다시 얻어가며 바쁘게 돌아가는 스레드이다. sleep queue를 만들어서 스레드를 ticks시간 만큼 재우고 ticks 시간이 경과하면 다시 깨우는 로직을 만들어야 한다.

thread_yield()

pintos-kaist/threads/thread.c

현재 실행 중인 스레드를 blocked/waiting 상태로 바꾸지 않고 그냥 레디큐(ready_list)에 들어가게 함
thread_block()은 현재 실행 중인 스레드가 blocked/waiting 상태로 바뀌도록 한다면 thread_yield()는 cpu를 자발적으로 양보하고 ready 상태로 바꾼다.
스레드가 cpu를 양보하긴 했지만 레디 큐에 다시 들어갔을 때 본인의 우선 순위가 가장 높으면 다시 스케줄러가 해당 스레드를 실행시키게 될 수도 있다. → thread_yield()를 썼다고 반드시 다른 스레드로 전환되는 것은 아니다

/* Yields the CPU.  The current thread is not put to sleep and
   may be scheduled again immediately at the scheduler's whim. */
void
thread_yield (void) {
	struct thread *curr = thread_current ();
	enum intr_level old_level;

	ASSERT (!intr_context ());

	old_level = intr_disable ();
	if (curr != idle_thread)
		list_push_back (&ready_list, &curr->elem);
		
	do_schedule (THREAD_READY);
	intr_set_level (old_level);
}

thread_block()

pintos-kaist/threads/thread.c

/* Puts the current thread to sleep.  It will not be scheduled
   again until awoken by thread_unblock().

   This function must be called with interrupts turned off.  It
   is usually a better idea to use one of the synchronization
   primitives in synch.h. */
void
thread_block (void) {
	ASSERT (!intr_context ());
	ASSERT (intr_get_level () == INTR_OFF);
	thread_current ()->status = THREAD_BLOCKED;
	schedule ();
}

timer_elapsed()

pintos-kaist/devices/timer.c

then 이후로 tick이 얼마나 경과했는지 리턴
시간 경과를 측정하는 함수
busy-wait 루프 성능 측정하는 데 자주 쓰인다고 함

/* Returns the number of timer ticks elapsed since THEN, which
   should be a value once returned by timer_ticks(). */
int64_t
timer_elapsed (int64_t then) {
	return timer_ticks () - then;
}

👉🏼 then은 이전에 timer_ticks()리턴값

현재 timer_ticks()리턴값 - 이전 timer_ticks()리턴값 이므로 then이라는 시점 이후로 지금까지 얼마나 tick이 경과했는지 계산하는 함수이다.

struct list_elem 구조체

pintos-kaist/include/lib/kernel/list.h

/* List element. */
struct list_elem {
	struct list_elem *prev;     /* Previous list element. */
	struct list_elem *next;     /* Next list element. */
};

👉🏼 이 구조체는 실제 데이터가 아니라 단지 리스트 연결을 위한 고리이다. list_elem은 보통 어떤 구조체 (struct thread) 안에 들어있다. 그래서 list_entry(a, struct thread, elem)를 사용해서 list_elem *a를 변수로 가지는 struct thread 타입 구조체를 복원해주고 나서 우리가 사용하고싶은 필드(priority, wakeup_tick)를 꺼내서 비교하면 된다.

list_entry 매크로

pintos-kaist/include/lib/kernel/list.h

/* Converts pointer to list element LIST_ELEM into a pointer to
   the structure that LIST_ELEM is embedded inside.  Supply the
   name of the outer structure STRUCT and the member name MEMBER
   of the list element.  See the big comment at the top of the
   file for an example. */
#define list_entry(LIST_ELEM, STRUCT, MEMBER)           \\
	((STRUCT *) ((uint8_t *) &(LIST_ELEM)->next     \\
		- offsetof (STRUCT, MEMBER.next)))

👉🏼 list_elem값으로 그 list_elem이 포함된 struct thread가 뭔지 찾을 때 사용하는 함수

list_elem으로 struct thread 구조체의 주소를 찾아 그 스레드 구조체로 접근

→ 구조체에 저장된 스레드 end 시간과 현재 시간을 비교하여 깨워야 할 스레드인지 아닌지 판단 후 깨워야 되면 깨우기

→ 끝나는 시간이 긴 애 일수록 sleep_list의 뒤쪽에 있을 것이다.

📍개념 보충 설명

cpu tick

system timer 또는 programmable interrupt timer(PIT)라는 하드웨어 컴포넌트가 한 번 hit할 때를 tick이라고 한다.
이 타이머의 tick이 한 번 지날 때마다 커널이 interrupt handler function 또는 timer interrupt handler를 호출하여 정해진 시간 마다 인터럽트를 발생시킨다.
OS는 이 타이머가 발생시키는 tick 주기 마다 스케줄링과 같은 시스템 작업을 처리한다.
tick frequency는 1초당 tick이 몇 번 발생하는지로 계산한다.
예를 들어 tick frequency=10ms이면 1초에 100번의 tick이 발생하는 것

cpu clock cycle vs tick

clock cycle
- cpu가 하나의 명령어를 처리할 때 걸리는 시간
- 3GHz(진동수)의 클럭을 가진 cpu는 초당 30억번의 클럭 주기를 가짐
- 클럭 사이클이 짧으면 더 빠르게 작업을 처리한다고 볼 수 있음
tick
- OS가 작업을 처리할 때 따르는 일정하게 고정된 주기
- oscillator에 의해 발생하는 일정하게 고정된 주기

clock cycle은 컴퓨터 구조에서 cpu가 명령어를 처리하는 방법을 설명할 때 사용했던 용어이다.

예전에는 한 instruction을 수행하는 것도 여러 단계로 나뉘어지므로 (fetch: 명령어 가져오기→decode: 명령어 해석→execute: 명령어 실행→write back: 결과 저장 ⇒ 각 단계를 처리하는 독립적인 하드웨어 유닛이 존재) 한 instruction을 수행할 때 여러 clock cycle이 필요했는데 pipelining을 사용하고 나서 부터는 1 clock cycle 안에 한 intruction을 수행할 수 있게 되었다.

그리고 tick은 운영체제에서 cpu가 하나의 작업(프로세스나 스레드, 인터럽트 등)를 처리하는 방법을 설명할 때 사용했던 용어이다.

tick은 일정하게 고정된 주기이고, clock cycle은 어떤 작업이 처리되는 시간을 측정한 개념의 느낌?

# ifdef

#ifdef [매크로]
	문장들 A
#else
	문장들 B
#endif

매크로가 정의되어 있다면 문장들 A를 컴파일하고, 그렇지 않다면 문장들 B를 컴파일한다.

매크로는 보통 다음과 같은 방법으로 정의되어있다.

소스코드 내에 #define [매크로]로 정의됨
컴파일 옵션에서 gcc -D옵션으로 정의함
- makefile 확인해보기
헤더파일에 정의됨

Kernel Thread 와 User Thread

커널 스레드는 OS의 커널이 관리하는 스레드이다. 프로세스가 하나 생성되면 커널은 하나의 커널 스레드를 만드는데, 프로세스가 아닌 커널 스레드가 실질적인 스케줄링 대상이 된다.

유저 스레드는 유저 공간에서 관리하는 스레드이다. 커널은 유저 스레드의 존재를 모르며, 모든 유저 스레드의 관리는 유저 공간에서 이루어진다. 유저 스레드의 실질적인 수행은 자신이 속한 프로세스의 커널 스레드와 연결되어 수행된다.

하나의 프로세스는 하나 이상의 유저 스레드 또는 커널 스레드를 가질 수 있다.

커널 스레드가 시스템콜을 호출하면 해당 스레드만 **블로킹(함수 제어권을 넘겨주고 리턴값을 받을 때까지 실행을 중단)**되고, 다른 커널 스레드들은 계속 실행될 수 있다.

반면 유저 스레드는 하나의 유저 스레드가 시스템콜을 호출하면 같은 프로세스의 다른 유저 스레드들도 블로킹(제어권을 넘겨주고 실행 중단)될 수 있다.

커널은 그 유저 스레드에 연결된 커널 스레드가 시스템콜을 호출한 것이라고 여기기 때문에, 해당 커널 스레드가 블로킹되면서 물려있던 다른 유저 스레드들도 블로킹될 여지가 있다.

컨텍스트 스위칭 비용은 커널 스레드가 유저 스레드보다 가볍다.

https://jofestudio.tistory.com/136 → 여기 잘 정리되어있음

blocking vs non-blocking

블로킹과 논블로킹은 함수가 제어권을 어떻게 처리하는지에 따라 나뉜다.

제어권 : 자신의 코드를 실행할 권리. 제어권을 가진 함수는 자신의 코드를 끝까지 실행한 후, 자신을 호출한 함수에게 돌려준다.
블로킹 :
1. A함수가 B함수를 호출하면 A가 B에게 제어권을 넘겨준다.
2. 제어권을 넘겨받은 B는 함수를 실행한다. A는 함수 실행을 잠시 멈춘다.
3. B는 실행이 끝나면 자신을 호출한 A에게 제어권을 돌려준다.
논블로킹 :
1. A함수가 B함수를 호출해도 제어권을 자신이 그대로 가지고 있는다.
2. A함수가 B함수를 호출하면 B함수는 실행되지만 제어권은 A함수가 그대로 가지고 있는다.
3. A는 계속 제어권을 가지고 있기 때문에 B를 호출한 이후에도 자신의 코드를 계속 실행한다.

동기와 비동기는 호출되는 함수의 작업 완료 여부를 고려하는지에 따라 나뉜다.

동기 : A가 B를 호출한 뒤 B의 리턴값을 기다림
비동기 : A가 B를 호출할 때 콜백 함수를 함께 전달해서 B의 작업이 완료되면 함께 보낸 콜백 함수를 실행함. A는 B를 호출한 이후로 B의 작업 완료 여부는 신경쓰지 않는다.

https://velog.io/@nittre/블로킹-Vs.-논블로킹-동기-Vs.-비동기

프로세스와 스레드 상태 변화의 차이점

둘 다 상태의 정의는 똑같다.

running : cpu 점유하고 명령어 실행 중인 상태
waiting/blocked : I/O처리가 필요할 때, 어떤 이벤트가 끝나기를 기다려야 할 때
ready : 언제든 cpu를 할당받아 실행될 준비가 된 상태
terminated : 실행 종료 상태
new : 생성되었을 때

차이점은 다음과 같다.

	프로세스	스레드
상태 변화 주체	전체 프로세스 (코드/데이터/힙)	하나의 실행 흐름(스택+레지스터)
상태 공유 여부	프로세스 마다 독립적	스레드들은 같은 프로세스 주소 공간을 공유
I/O 요청 시	프로세스 전체가 block	현재 스레드만 block, 나머지 스레드는 계속 동작 가능
문맥 교환 시	주소 공간도 바뀜 (무겁고 느림)	주소 공간 공유, 스택만 바뀜 (빠름)

'정글 > Pintos' 카테고리의 다른 글

[pintos] 1주차 - Priority Scheduling 문서 해석 / 코드 해석 (1)	2025.05.20
[pintos] 1주차 - Alarm Clock 구현 과정 (0)	2025.05.20
[pintos] 1주차 - 키워드 정리 (2) : Process/Thread, DeadLock, 프로세스 상태/CPU Scheduling (3)	2025.05.11
[pintos] 1주차 - 키워드 정리 (1) : Semaphore/Mutex, Busy Waiting/Sleep Waiting (0)	2025.05.10
[pintos] 1주차 - 문서 정리 (0)	2025.05.10

현재글[pintos] 1주차 - Alarm Clock 코드 정리

기록장

학습, 트러블 슈팅, 회고 https://github.com/syounng

Today :
Yesterday :

기록장