알람시계 구현

timer_alarm(int ticks)

주어진 시간(ticks) 이후에 프로세스를 깨우는 시스템콜

PintOS는 바쁜 대기 알람을 사용한다.

목표

devices/timer.c에 정의된 timer_sleep()을 다시 구현하기

PintOS에서는 제공된 코드는 Busy-waiting(바쁜대기)를 수행하는 코드다. 즉, 현재 실행중인 스레드를 주어진 조건이 맞을 때 까지 반복적으로 다른 스레드에게 CPU를 양보하여 주어진 틱 동안 실행을 일시 중단하는 방식으로 구현되어있다.

비효율적인 Busy-waiting이 아닌 sleep-awake방식으로 바꿔서 구현하는게 alarm-clock의 목표인데 여기서 Busy-waiting과 sleep-awake방식에 대해 알아보자

Busy waiting

• 프로세스가 다른 프로세스에게 CPU를 양보하지 않고 계속 조건이 맞을 때 까지 확인하는 방식을 말한다.

• 이러한 방식은 CPU 자원을 낭비하고, 다른 스레드가 실행되는 기회를 줄여 성능 저하가 발생할 수 있다.

Sleep-Awake

• 프로그램이 대기하는 동안 CPU를 사용하지 않고 일정 시간이 지난 후에 다시 CPU를 사용할 수 있도록 프로그램은 대기 상태에 들어간다.
• 이 방식은 Busy waiting 방식에 비하여 CPU 자원을 절약할 수 있다.

그렇다고 무조건 Busy-waiting이 사용되지 않는건 아니다.
1. 대기하는 시간이 매우 짧고, 컨텍스트 스위칭으로 인한 오버에드가 대기 시간 보다 큰 경우
2. 빠른 반응이 필요한 실시간 시스템에서, 조건이 빠르게 충족될 것으로 예상되는 경우에 사용된다.

각 방식의 장단점을 따져 적절한 상황에 쓰는 것이 중요하다.

non-Busy-waiting

busy-waiting이 아닌 방식은 non-busy-waiting이라고 하는데 이 방식은 대기 시간이 길어 CPU를 양보하는게 효율적이거나, 대기 시간을 예측할 수 없는 경우에 사용한다. 위에 sleep-Awake방식이 non-busy-waiting 방식이다.

공부하면서 이슈

• 내가 busy-waiting은 CPU를 반납하지 않고 조건을 계속 확인하여 컨텍스트 스위칭이 일어나지 않는건데 PintOS에서는 현재 스레드의 조건이 맞을 때까지 계속 CPU를 양보해서 내가 아는 것과 괴리가 있어 받아 들이기 까지 꽤 많은 시간이 걸렸다.

• 나중에 찾아보니 PintOS에서의 busy-waiting 구현 방식은 전통적인 바쁜대기와는 차이점이 있다고한다.

수정해야할 파일

• threads/thread.*
• devices/timer.*

해결해야할 문제 코드

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

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

• 이 함수는 주어진 시간(ticks)동안 스레드를 일시정지하는 시스템콜이다.
• 현재 timer_ticks와 주어진 ticks를 비교해서 도달하지 않은 경우 thread_yield ()를 호출하여 다른 스레드에게 CPU를 양보한다.
• ticks에 도달할 때 까지 계속 양보하여 비교하는 것은 큰 비효율을 발생시키고 이를 해결하는 것이 이번 과제의 목표이다.

해결방안

• 스레드가 tick에 도달하지 않는 경우 바로 readylist로 넣는 것이 아니라 sleeplist를 만들어서 각 틱마다 깨어날 수 있는 스레드를 선택해서 readylist넣는 방법
• 이 방식은 아직 깰 시간이 아닌 스레드를 깨우지 않아 cpu를 효율적으로 사용할 수 있다.

1) sleepList 선언 및 초기화

 static struct list sleep_list;
 
 thread_init (void) {
 ...
 
 	list_init (&sleep_list);
    
 ...
 }
    

2) 구조체 필드 추가

struct thread {
...

	int64_t wake_up_tick;  
    
...
}

• 타이머 인터럽트 핸들러를 통해서 매 틱마다 깨워야할 스레드를 확인할 수 있는 변수를 추가한다.

3) 스레드 재우기 로직 변경
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 ();
	thread_sleep (start + ticks); 
    // 현재 시각 (start) + 잠들 시간 (ticks)
}

thread_sleep

void thread_sleep(int64_t ticks)
{
	struct thread *curr = thread_current();
	enum intr_level old_level;

	ASSERT(curr != idle_thread);

	old_level = intr_disable();
	curr->wakeup_ticks = ticks;
	list_insert_ordered(&sleep_list, &curr->elem, cmp_thread_ticks, NULL);
	thread_block();
	intr_set_level(old_level);
}

thread_block (void)

void thread_block (void) {
	ASSERT (!intr_context ());
	ASSERT (intr_get_level () == INTR_OFF);
	thread_current ()->status = THREAD_BLOCKED;
	schedule ();
}

• 현재 스레드가 유휴 스레드가 아닌경우, 호출 스레드의 상태를 차단(blocked)으로 변경하고, 깨울수 있도록 local tick을 저장, 해당 스레드를 대기(sleep) 큐에 넣는다"
• 필요할 때 전역 tick을 업데이트하고 ? 스캔시간을 단축 , schedule()을 호출
• 스레드 목록을 조작할 때 인터럽트를 비활성화하기

cmp_thread_ticks

    // 두 스레드의 wakeup_ticks를 비교해서 작으면 true를 반환하는 함수
    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_ticks < st_b->wakeup_ticks;
    }

4) 재운 스레드 깨우기 로직 추가
timer_interrupt

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

• 매 틱(tick)마다, sleep queue를 확인하여 깨워야 할 스레드가 있는지 검사하고, 해당 스레드를 깨우는 함수를 호출
• 타이머 인터럽트가 발생할 때마다 실행되며, sleep queue에 있는 스레드들 중에서 현재 시간(틱)에 맞춰 깨워야 할 스레드를 찾아 준비 상태로 전환시키는 작업

thread_wakeup

void thread_wakeup(int64_t os_ticks)
{
	if (list_empty(&sleep_list))
		return;
	struct thread *t;
	enum intr_level old_level;

	old_level = intr_disable();
	while (!list_empty(&sleep_list))
	{
		t = list_entry(list_front(&sleep_list), struct thread, elem);
		if (t->wakeup_ticks > os_ticks)
			break;
		list_pop_front(&sleep_list);
		list_insert_ordered(&ready_list, &t->elem, cmp_priority, NULL);
		t->status = THREAD_READY;

	}

	intr_set_level(old_level);
}

여기서 깨우고 준비리스트에 삽입할 때 우선순위 별로 준비 리스트에 오름차순으로 정렬해주면 우선순위 순서대로 실행된다.
cmp_priority

bool cmp_priority(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->priority > st_b->priority;
}

알람 시계 구현 결과

위의 코드에서 우선 순위별로 readylist에 삽입해주면 alarm관련 테스트는 모두 통과할 수 있다!!

구현 목록

수정해야할 파일

• threads/thread.*
• devices/timer.*

수정 메소드

• timer_sleep()
• 블록 상태를 도입해서 timer_sleep 새로 만들기 -> 'blocked'로 변경하고 sleep queue에 넣기
• thread.h thread 구조 수정: int64_t Type -> 깨어날 시간 저장
• timer_interrupt
  • 슬립리스트랑 글로벌틱체크
  • 일어날 스레드 찾기
  • 필요한경우 레디큐로 이동
  • 글로벌틱 업데이트
• thread_init
• timer_sleep()
• timer_interrupt()

추가

• static struct list sleep_list; 선언

• list_init (&sleep_list); 초기화

• 각각의 스레드에 깨어나는 시간저장

• thread_sleep

  • 유휴스레드가 아닌경우 BLOCKED로 변경
  • localtick 저장
  • 전역 tick update
  • schedule() 호출
  • 목록 조작시 인터럽트 활성화 비활성화

• thread-wakeup

  • 슬립큐에서 제거 후 레디큐삽입
  • 수정전 활성화 비활성화

• 스레드가 가진 틱의 최소값을 저장하는 함수

• 틱의 최소값을 반환하는 함수