PROJECT-1 (thread)

커널 스레드 생성, 스케줄링, 우선순위 기반 실행, 동기화 구현
→ “동시에 여러 작업을 할 수 있도록 운영체제의 핵심 기능을 만들기” 프로젝트.

---

시작 전

주제	내용	추천 자료
운영체제 기초	프로세스, 스레드, 스케줄링	Three Easy Pieces 2~4장
Pintos 기본 구조	디렉토리와 흐름	pintos.pdf 1장 "Getting Started"
스레드 관련 코드	thread.c, timer.c 분석	Pintos src 직접
디버깅 연습	GDB 사용해보기	$ pintos --gdb + break

---

참고

구현 순서 추천

• Alarm Clock
  • 기능이 명확하고 단일 흐름이라 구현 진입 장벽이 가장 낮음.
  • timer_interrupt() 흐름을 파악하면 스레드 block/unblock 연습에 적응.
• Priority Scheduling
  • Alarm에서 배운 thread_block, unblock, ready_list 개념을 확장해서 우선순위 기반 정렬에 적용
  • list_insert_ordered()로 정렬, yield() 타이밍에 대한 이해 필요
• Priority Donation
  • 개념이 복잡하고 테스트가 까다롭기 때문에 가장 마지막에 추천
  • nested donation, priority 복원, lock 구조체까지 함께 이해해야 함

---

시작

• 목표: Pintos의 커널 스레드 시스템에 대해, alarm clock, priority scheduling, priority donation 기능을 구현하고, 동기화 도구(semaphore, lock, condition variable)를 활용하여 안전한 병행성을 제공하기
• 핵심 수정 파일  threads/thread.c, threads/synch.c, devices/timer.c, threads/interrupt.c
  
• 참고 파일 흐름 이해: init.c, thread.c, syscall.c, exception.c

  파일	역할
  init.c	Pintos 부팅 진입점, 전체 초기화 담당
  thread.c	스레드 생성, 종료, 상태 관리 및 스케줄러 구현
  syscall.c	유저 프로그램의 시스템 콜 처리 (exec, exit, read 등)
  exception.c	예외(예: 페이지 폴트, 잘못된 접근) 처리 핸들러

---

1. Alarm Clock

항목	작성 예시
어떻게 구현할 건가요?	struct thread에 wakeup_tick 필드 추가. timer_sleep()에서 현재 tick에 + t 더해 저장 후 block. timer_interrupt()에서 리스트 순회하며 깨움.
어떤 자료구조 사용할 건가요?	sleeping_list: 정렬된 리스트 사용. list_insert_ordered() 활용.
어떤 코드 수정하나요?	timer_sleep() (threads/timer.c), timer_interrupt() 내부 수정
주의할 점은?	인터럽트 컨텍스트에서는 yield 하면 안 됨 → intr_context() 체크 필요

구현 목표

• timer_sleep(int ticks) 호출 시 현재 스레드를 ticks 만큼 잠자게 함
• wakeup_tick 이 지나면 다시 깨움

설계

• struct thread에 wake_tick 필드 추가
• sleeping_list 리스트 생성 (priority로 정렬 X, wake_tick 기준 정렬)
• timer_sleep()에서 스레드 block 및 리스트 삽입
• timer_interrupt()에서 현재 tick과 비교해 깨울 스레드 unblock

수정 함수

• timer_sleep()
• timer_interrupt()
• thread_block() / thread_unblock()

테스트

테스트 이름	의미
alarm-single	하나의 스레드가 지정된 시간 뒤에 깨어나야 함
alarm-multiple	여러 스레드가 서로 다른 시간에 깨어나야 함
alarm-priority	우선순위가 높은 순서로 정확히 깨어나는지 확인

---

2. Priority Scheduling

항목	작성 예시
Ready 리스트 정렬은 어떻게 하나요?	list_insert_ordered()로 Ready 리스트 정렬
우선순위 변경 시 재정렬 필요 여부	thread_set_priority() 호출 시 yield() 필요
새 스레드가 Ready 상태가 될 때 어떻게 하나요?	thread_unblock()에서 정렬 삽입
어디서 수정해야 하나요?	thread_unblock(), thread_yield(), schedule()
주의할 점은?	같은 priority라면 round-robin 유지해야 함

구현 목표

• Ready 상태의 스레드 중 우선순위가 가장 높은 스레드가 먼저 실행됨

설계

• thread->priority 필드 사용
• Ready list를 list_insert_ordered()로 정렬 삽입
• 스레드가 unblock될 때 현재 실행 중인 스레드보다 우선순위 높으면 yield
• thread_yield()에서 ready list의 가장 높은 priority 비교

수정 함수

• thread_create()
• thread_unblock()
• thread_yield()
• schedule(), next_thread_to_run()

테스트

테스트 이름	의미
priority-change	우선순위가 바뀔 때 스케줄러가 적절히 반응하는지
priority-preempt	더 높은 우선순위 스레드가 나타나면 선점되는지 확인
priority-fifo	같은 priority이면 FIFO 순서로 동작하는지

---

3. Priority Donation

항목	작성 예시
nested donation은 어떻게 처리하나요?	최대 깊이 제한 설정 (예: 8), 재귀적으로 priority 전달
어떤 구조체 수정하나요?	struct lock, struct thread에 waiting_lock, donors 리스트 추가
어떤 함수에서 donation 발생하나요?	lock_acquire(), lock_release(), thread_set_priority()
주의할 점은?	donation 제거 시 원래 priority 복구 필요

구현 목표

• 낮은 priority의 스레드가 락을 점유했을 때, 높은 priority 스레드가 우선 실행되도록 donation

설계

• struct thread에 original_priority, waiting_lock, donors 리스트 추가
• struct lock에 holder 필드 활용
• lock_acquire() 시 락의 holder에게 priority 전달
• nested donation은 재귀적으로 처리 (깊이 제한 필요)
• thread_set_priority()에서 donation 취소 시 원래 priority 복원

수정 함수

• lock_acquire()
• lock_release()
• thread_set_priority()

테스트

테스트 이름	의미
priority-donate-one	하나의 락에 대해 donation이 제대로 되는지
priority-donate-multiple	여러 스레드가 하나의 락에 nested donation 시도
priority-donate-chain	중첩된 락 대기 상황에서 donation이 전달되는지
priority-donate-lower	donation 후 priority 복원이 정확히 되는지

---

4. 동기화 도구 개선

항목	작성 예시
sema_down()에서 priority 고려했나요?	waiters 리스트를 우선순위로 정렬
lock_acquire()에서 donation 처리	락 holder에게 priority 전달
cond_wait()에서 priority 고려	condition 변수의 waiters 리스트도 정렬 필요

목표

• sema_down(), cond_wait() 등 대기 리스트에서 우선순위 고려하도록 개선

설계

• semaphore, condvar 내부 waiters 리스트를 우선순위 기준 정렬

수정 함수

• sema_down(), sema_up()
• cond_wait(), cond_signal()

---

참고 구조체 및 함수 흐름

파트	주요 파일	함수
스레드 생성/종료	threads/thread.c	thread_create(), thread_exit()
스레드 스케줄링	threads/thread.c	thread_yield(), schedule(), next_thread_to_run()
블록/언블록 처리	threads/thread.c	thread_block(), thread_unblock()
타이머 & 틱	devices/timer.c	timer_ticks(), timer_sleep(), timer_interrupt()
락/세마포어	threads/synch.c	lock_acquire(), sema_down(), cond_wait()

struct thread (thread.h)

• 필수 필드: priority, wake_tick, original_priority, waiting_lock, donors

주요 함수 흐름

• init.c: main() → 시스템 전체 초기화 흐름
• thread_create() → 스레드 생성
• thread_block() / thread_unblock() → 상태 전이
• schedule() → 다음 스레드 선택
• timer_interrupt() → wake_tick 검사하여 unblock
• syscall.c, exception.c → 이후 Project 2 이상에서 프로세스 관리 및 예외 처리 추가됨

---

요약

기능	핵심 키워드	주요 수정 위치
Alarm Clock	sleep list, wake_tick	timer.c, thread.c
Priority Scheduling	ready list 정렬	thread.c
Priority Donation	nested donation	synch.c, thread.c
동기화	우선순위 기반 대기 정렬	synch.c

---