Pintos Project1 - Alarm Clock (1)

시작 준비가 안됐다면, 아래 포스팅으로 감 잡기

Pint OS project 1 - 시작 준비

---

 ⏱️Alarm Clock

• timer_sleep() 함수를 수정
• busy waiting을 피하는 방식으로 재구현 목표
• timer_sleep() 함수는 devices/timer.c 파일에 있음
• 반복적으로 시간이 경과했는지를 체크하고 thread_yield()를 호출해 CPU를 낭비하는 방식으로 작동하는데, 이를 효율적인 방식으로 개선하는 것이 과제의 핵심

 

1. timer_sleep() 함수의 목적

• timer_sleep(int64_t ticks) 함수는 현재 스레드의 실행을 지정된 시간(틱 수) 동안 중단
• 인자로 받은 ticks는 시스템 틱 단위로, 1초당 TIMER_FREQ에 해당하는 틱이 발생
• 기본적으로 TIMER_FREQ는 100으로 설정되어 있어, 1초에 100번의 틱이 발생
• 예를 들어 ticks 값이 100이라면, timer_sleep() 함수는 현재 스레드를 약 1초간 중단

 

2. busy waiting을 피하기 위한 개선

• 기존의 timer_sleep()은 busy waiting 방식으로 동작
• 이는 스레드가 CPU를 계속 점유하면서 반복적으로 시간을 확인하는 방식
• CPU 자원을 낭비하므로 이 방식을 개선해야 함
• 해결 방법:
  • 스레드를 바로 대기 상태로 전환하고, 대기 시간이 지나면 스레드를 준비 큐(ready queue)로 되돌림
  • 이를 위해 대기할 스레드와 깨어날 시간을 저장하는 자료 구조가 필요
  • 시스템 틱이 증가할 때마다 대기 중인 스레드가 깨어날 시간이 되었는지 확인하고, 깨어날 시간이 되면 해당 스레드를 준비 큐에 추가

 

3. timer_sleep() 구현 단계

1. 스레드 대기 리스트 추가:
   • 대기할 스레드와 깨어날 시간 정보를 저장하는 대기 리스트를 추가
   • 대기 중인 스레드들은 이 리스트에 삽입되고, 각 스레드는 깨어날 시간을 기준으로 정렬
2. timer_interrupt() 함수 수정:
   • timer_interrupt() 함수는 틱이 증가할 때마다 실행
   • 이 함수에서 현재 틱 수를 기준으로 깨어날 시간이 된 스레드들을 준비 큐로 이동
   • 이 과정에서 대기 리스트를 확인하여, 시간이 된 스레드들을 차례로 깨워 준비 큐에 추가
3. 스레드 대기와 깨우기:
   • timer_sleep() 함수는 현재 스레드를 대기 리스트에 추가
   • 지정된 시간이 지날 때까지 대기 상태로 전환
   • 지정된 시간이 지나면, timer_interrupt() 함수에 의해 스레드가 준비 큐로 이동되어 다시 실행

 

4. 시간 단위와 기타 함수

• timer_sleep()의 인자는 틱(ticks) 단위로 표현
• timer_msleep(), timer_usleep(), timer_nsleep() 등의 함수는 각각 밀리초, 마이크로초, 나노초 단위로 스레드를 중단할 수 있지만, 이들은 내부적으로 timer_sleep()을 호출하여 실제 중단 시간을 관리
• 따라서 timer_sleep()만 재구현하면, 다른 함수들은 수정할 필요가 없음

 

5. 활용 예 및 주의사항

• timer_sleep()은 1초에 한 번 깜빡이는 커서 등과 같이 실시간으로 작동해야 하는 스레드에서 유용
• TIMER_FREQ는 변경하지 않는 것이 좋음 
• 이 값을 변경하면 테스트들이 실패할 가능성이 높음

 

Thread에 대한 상태

• Thread에 대한 모든 상태 
• 위의 사진 완전히 익혀야 함

---

Busy-Waiting 

• CPU가 어떤 조건이 충족될 때까지 반복적으로 확인
• CPU는 대기 중에도 계속 작업 수행하여 CPU 자원 지속적으로 사용  
  • CPU는 반복문이나 조건문을 사용해 지속적으로 조건 확인하며 기다림 
  • 다른 스레드가 작업을 완료할 때 까지 반복해서 확인

// 조건이 충족될 때까지 반복적으로 확인 (busy waiting)
while ((time(NULL) - start_time) < wait_seconds) {
    // CPU를 계속 사용하여 대기 상태 유지
}

 

Sleep-Awake 

• 스레드나 프로세스를 대기 상태로 전환하여 CPU 자원 절약
• 조건이 만족될 때 해당 스레드를 awake하여 다시 실행
• 스레드는 조건이 충족될 때까지 대기 상태로 전환
• 대기 상태의 스레드는 CPU를 사용하지 않기 때문에 다른 스레드가 CPU 자원을 사용할 수 있음
• 조건 충족시, 스레드가 다시 준비 큐에 추가되어 CPU에서 실행

void timer_sleep(int ticks) {
    // 조건이 충족될 때까지 스레드를 대기 상태로 전환
    current_thread->sleep(ticks);
    // 조건이 충족되면, 스레드가 다시 준비 큐에 추가됨
}

 

 

Tick

• 타이머나 시계 장치에서 일정한 주기로 발생
• CPU나 시스템 타이머의 주기적 인터럽트를 의미
• 틱 단위로 시간을 관리하여 프로세스 스케줄링, 대기 시간 관리, 타이머 기능 구현
• ex) TIMER_FREQ가 100으로 설정된 경우 1초에 100번 틱이 발생
  • Kernel Ticks 
    • 운영체제 커널이 CPU를 사용한 시간
    • 커널이 어떤 작업을 수행하거나 특정 스레드가 커널 모드에서 실행될 때 틱 증가
    • 일반적으로 커널이 할 일이 많으면 커널 틱 수 증가
  • Idle Ticks
    • Idle Ticks는 CPU가 놀고 있는 시간
    • Idle Ticks의 증가는 CPU가 아무 작업도 하지 않고 대기
    • Idle Ticks이 많으면 CPU 효율적 관리 
  • User Ticks
    • User Ticks  틱은 사용자 모드에서 CPU를 사용한 시간
    • Pintos 같은 시스템은 주로 커널 모드에서 실행
    • 따라서 대부분 User Ticks는 0
    • 일반적인 운영체제에서는 User Ticks이 많은수록 Application이 CPU를 많이 사용 함을 의미
  • Timer Ticks
    • 시스템이 부팅된 이후 경과된 시간 

 

---

빌드 방법

make build/tests/threads/alarm-single.result
make build/tests/threads/alarm-multiple.result
make build/tests/threads/alarm-simultaneous.result
make build/tests/threads/alarm-priority.result
make build/tests/threads/alarm-zero.result
make build/tests/threads/alarm-negative.result

• 해당 명령어로 원하는 부분만 결과 확인 가능
• (현재 명령어는 alarm 실행 기준)

pintos -v -- -q run alarm-single
pintos -v -- -q run alarm-multiple
pintos -v -- -q run alarm-simultaneous
pintos -v -- -q run alarm-priority
pintos -v -- -q run alarm-zero
pintos -v -- -q run alarm-negative

• 위의 명령어를 쓰거나
• "/threads/build/tests/threads/... .output" 에서 출력 결과를 확인하거나 하면 된다.

---

✨ CODE 구현

기존 Busy wating 

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

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

• 스레드 time_sleep 할 만큼의 ticks에 도달 할 때 까지 계속 thread_yield 수행
• thread_yield ()  내부 list_push_back() 함수로  현재 스레드를 ready_list에 push 
• 스케줄링 후 위 과정 반복

 

📌 Busy waiting 결과

// threads/build/tests/threads/alarm-single.output
Timer: 277 ticks
Thread: 0 idle ticks, 277 kernel ticks, 0 user ticks

• 277개의 Kernel Tick 사용
  • 시스템이 부팅된 이후 경과된 시간
• Idle Ticks의 0라는 것은 CPU가 작업이 없는 시간이 없음을 의미

 

 

Sleep awake

구현 목표

1. 스레드 timer_sleep 함수 실행 후 대기 시간 계산 (wake_up_ticks)
2. 대기 시간 계산 후 대기 리스트에 추가 (sleep_list) 및 정렬 
3. 대기 리스트에 추가된 스레드 CPU 실행되지 않도록 차단 (BLOCKED)
4. 매 순간 틱을 증가시키는 인터럽트 발생 → 대기 중인 스레드 wake_up_ticks 넘었는지 확인
5. 대기 시간 종료 및 깨우기 

 

thread.h

struct thread {

	...
  
    /* 새로 추가: 스레드가 깨어나야 할 tick */
    int64_t wake_up_tick;               /* Tick at which to wake up */

	...
 
};

• thread 구조체에 wake_up_tick (대기 시간 계산) 추가 

 

// 비교 함수 선언
bool cmp_wake_up_ticks(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED);

 

 

 

devices/timer.c

static struct list sleep_list;  // 스레드를 재울 대기 리스트

• sleep_list 선언
• BLOCKED 상태의 스레드를 저장 할 sleep_list 
• timer_sleep 함수를 통해서 현재 스레드 sleep_list에 삽입 및 정렬

 

void timer_init (void) {

   	. . .
    
    list_init(&sleep_list);  // sleep_list 초기화
}

• init 함수에 sleep_list 값 초기화 코드 추가

 

/* wake_up_tick 기준으로 정렬하기 위한 비교 함수 */
bool cmp_wake_up_ticks(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED) {
    struct thread *t_a = list_entry(a, struct thread, elem);
    struct thread *t_b = list_entry(b, struct thread, elem);
    
    // 먼저 wake_up_tick 기준으로 정렬
    if (t_a->wake_up_tick != t_b->wake_up_tick) {
        return t_a->wake_up_tick < t_b->wake_up_tick;
    }
    // wake_up_tick이 같으면 우선순위 기준으로 정렬
    return t_a->priority > t_b->priority;
}

• list_entry 매크로로  list_elem 구조체 a를 가지고 있는 Thread의 주소 값 구함
• thread_a, thread_b의 주소 값으로 wake_up_tick를 알아내고 크기 비교
• 만일  wake_up_tick가 같은 경우 priority로 크기 비교

 

➕ list_entry 매크로

#define list_entry(LIST_ELEM, STRUCT, MEMBER)           \
	((STRUCT *) ((uint8_t *) &(LIST_ELEM)->next - offsetof (STRUCT, MEMBER.next)))

list_entry 매크로의 역할은 list_elem를 포함하고 있는 thread의 주소 값을 구하는 것이다. 

매크로 내부를 보면 복잡한 부분이 있는데 생각보다 간단하다. 

 

&(LIST_ELEM) -> next : 현재  list_elem의 next는 thread 구조체의 끝

offsetof (STRUCT, MEMBER.next) :  thread 시작 주소 ~ elem.next 까지의 오프셋

 

결국 이 두개를 빼면 elem를 포함하는 thread의 주소를 구할 수 있다.

 

참고로 여기에서 list != list_elem != thread 임을 기억 !!

 

 

 

void timer_sleep(int64_t ticks) {
    int64_t start = timer_ticks();  // 현재 틱 값을 가져옴

    ASSERT(intr_get_level() == INTR_ON);  // 인터럽트가 켜져있는지 확인
    if (ticks <= 0) return;  // 대기할 필요가 없으면 종료

    struct thread *current_thread = thread_current();  // 현재 스레드를 가져옴
    enum intr_level old_level = intr_disable();  // 인터럽트를 끄고 안전하게 조작

    current_thread->wake_up_tick = start + ticks;  // 깨어날 시간을 설정
    list_insert_ordered(&sleep_list, &current_thread->elem, cmp_wake_up_ticks, NULL);  // 대기 리스트에 삽입

    thread_block();  // 현재 스레드를 BLOCKED 상태로 전환 (대기)
    intr_set_level(old_level);  // 이전 인터럽트 레벨로 복구
}

•  timer_sleep을 처음 호출한 ticks을 start에 저장
  • 해당 ticks는 time_sleep을 요청한 ticks와 더해져서 현재 스래드의 wake_up_tick 값으로 할당
• list_insert_ordered 함수 
  • 매개변수 sleep_list의 주소, 현재 스레드의 list_elem, 비교 함수, aux 
  • ist_insert_ordered 함수 내부 반복문 진행
    • 반복문 진행 중 비교함수로 크기 비교 후 list_insert 함수 실행
• thread_block으로 현재 스레드의 status를 BLOCKED 상태로 전환 후 스케줄링 진행

 

/* 타이머 인터럽트 핸들러 */
void timer_interrupt(struct intr_frame *args UNUSED) {
    ticks++;  // 타이머 틱 증가
    thread_tick();  // 스레드 틱 함수 호출
    /* 깨어나야 할 스레드들을 검사하고 깨움 */
    while (!list_empty(&sleep_list)) {
        struct thread *t = list_entry(list_front(&sleep_list), struct thread, elem);
        // 깨어날 시간이 아직 이르다면, 반복 종료
        if (t->wake_up_tick > ticks) break;
        // 깨어날 시간이 된 스레드가 있으면 리스트에서 제거하고 깨움
        list_pop_front(&sleep_list);
        thread_unblock(t);  // 스레드를 깨움
    }
}

• intr_register_ext에서 타이머 인터럽트의 벡터 번호 0x20 로 timer_interrupt를 주기적으로 인터럽트 발생 시킨다.
• 하드웨어의 타이머 인터럽트에 의해 실행되는 timer_interrupt는 ticks를 호출 때 마다 1씩 증가 시킨다.
• thread_tick()
  • 조건에 따라 idel_ticks 또는 kernel_ticks를 올려준다. 
  • thread_ticks를 한개씩 올려주면서 TIME_SLICE보다 큰 경우  yield_on_return 플래그를 ture로 해줌
  • ( yield_on_return 는 플래그 중 하나로 스케줄링과 CPU 양보 요청)
• lisr_entry 매크로, list_front 함수, sleep_list의 elem을 이용해서 thread 주소값을 t에 반환
  • 만일 현재 스레드의 wake_up_tick가 ticks보다 큰 경우 break
    • 이 경우는 아직 awake 할 준비 안됨
  • 그게 아닌 경우 list_pop_front 함수로 sleep_list 가장 앞 비움
• thread_unblock 함수 내 list_push_back 함수로 ready_list에 thread의 elem 추가

 

 

📌Sleep/Awake 결과

Timer: 273 ticks
Thread: 250 idle ticks, 24 kernel ticks, 0 user ticks

• 24개의 커널 틱 사용 
  • 보통 운영체제가 스케줄링,인터럽트 처리, 시스템 호출 등을 처리하는데 사용
  • ex) 스레드가 잠들어 있을 때 커널이  관리
• 250개의 idle 틱 기록 
  
  • CPU가 작업 없이 유휴 상태로 있는 시간
  • 273 타이머 중 250틱 동안 유휴 상태

 

"/threads/build/tests/threads/... "   이 경로의 .result 된 값 들을 보면,

테스트 6개가 모두 Pass가 뜬 것을 볼 수 있다.

(.output은 출력 한 결과들이 나옴)

 

---

https://github.com/pintos-project1/PintOS-Project1/tree/jerim_project1

GitHub - pintos-project1/PintOS-Project1