2025.05.12

TIL(TODAY I LEARN)

---

• 오늘한 내용 : PintOS - Project1: Threads - Alarm Clock 구현

• WEEK 09 : 정글 끝까지(PintOS) - Threads

---

Thread Project 1 - 목표 1

1. Alarm Clock (devices/timer.c)
   • timer_sleep() 재구현
   • 타이머 인터럽트 핸들러 수정

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

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

---

테스트 방법

build 폴더 내부에서

make tests/threads/(테스트 하고싶은 테스트 명).result VERBOSE=1
ex)
make tests/threads/alarm-simultaneous.result VERBOSE=1

---

스레드 실행 흐름

[NEW]
   │ thread_create()
   ▼
[READY]         ←––– thread_unblock() 호출
   │ schedule()
   ▼
[RUNNING]
   │ thread_block() 호출 (lock_fail, cond_wait, timer_sleep 등)
   ▼
[BLOCKED]       ←––– event 발생 시 thread_unblock()
   │
   └───────────(thread_unblock)───▶ back to [READY]

그리고 실행이 다시 잡히면
[READY] –– schedule() ––▶ [RUNNING]

1. NEW → READY
   • thread_create() 로 생성 직후 바로 준비 큐로
2. READY → RUNNING
   • 스케줄러(schedule())가 선택해 문맥 전환
3. RUNNING → BLOCKED
   • 스레드 스스로 더 이상 실행할 수 없다고 판단되면
     • lock_acquire() 실패 → thread_block()
     • cond_wait() → thread_block()
     • timer_sleep() → thread_block()
4. BLOCKED → READY
   • 블록 조건 충족 시
     • lock_release() / sema_up()
     • cond_signal() / cond_broadcast()
     • timer_interrupt() 에서 슬립 리스트 처리
   • 각 경우 내부에서 thread_unblock() 호출해 준비 큐로 복귀
5. 종료
   • 스레드 함수 return 또는 thread_exit() → 자원 정리 → 더 이상 READY/RUNNING 상태로 돌아오지 않음

이 사이클을 통해 “준비 큐에 들어가고 → Running → Blocked → (Unblock) → 다시 Ready → Running” 과 같은 흐름을 거침

---

알람 시계(Alarm Clock) ← blocked 일종

• 목표: timer_sleep()을 busy‐wait 대신 다른 방식으로 재구현
• 수정 파일: devices/timer.c
  • void timer_sleep(int64_t ticks)
    • 슬립 리스트에 (wake_tick, cur_thread)
    • 추가 후 thread_block()
  • timer_interrupt()
    • 매 틱마다 current_ticks++ → 슬립 리스트 순회 → 기상 시점 도달 스레드 thread_unblock()

수정한 함수

* thread.h
int64_t wakeup_tick; 추가
struct list_elem sleep_elem; 추가
----------------------------------------
* timer.c
list.c 참고

sleep_list 선언
timer_init() - sleep_list 초기화 추가
timer_sleep() - busy_wait 제거
	thread_current(),list_insert_ordered() 사용
	wakeup_tick_less() 구현
		list_entry() - elem포인터가 있는 상위 구조체를 반환
timer_interupt() - 깨우기 구현

How?

1. 슬립리스트와 깨어날 시각 변수를 thread 구조체에 추가

struct thread
{
	/*... 기존 필드...*/
	/* alarm을 위한 깨울 시각, 슬립 리스트 연결용 엘리먼트 추가*/
	int64_t wakeup_tick;
	struct list_elem sleep_elem; //list.h에 자료구조 있음
};

2. timer_sleep() 호출 시 깰 시각, 리스트에 추가(b 방법사용)
   • 깰 시각
     • thread_current()->wakeup_tick = start + ticks;
   • 리스트 자료구조는 list.c 참고
   • 리스트에 추가할 방법
     1. 끝에 붙이고 전체 순회
        • 장점: 구현이 단순
        • 단점: 매 틱마다 리스트 전체를 O(n) 순회 → 스레드 수가 많아지면 오버헤드 폭증
     2. 정렬해서 앞부분만 검사
        • 장점: 틱당 검사 작업이 “깨울 스레드만” O(1) 또는 O(k) (깨워질 k개)
        • 단점: list_insert_ordered()가 O(n) (한 번만)
     3. 결론
        • 스레드 수가 작고 단순 구현을 원한다면 a번 방법도 가능
        • 성능을 중시한다면 b번(정렬된 리스트)
3. timer_interrupt()
   • sleep_list가 비지 않았다면
     • 현재 tick보다 list 맨 앞의 wakeup_tick이 작으면 unblock
     • wakeup_tick이 현재 tick 보다 크면 break