[PintOS] Project 1 - Alarm Clock, Priority, Donate

novxerim·2021년 12월 30일

SW-Jungle

목록 보기

36/59

PintOS 실행하기

핀토스 실행

우리는 핀토스라는 시뮬레이터에서 핀토스를 편리하게 실행할 수 있는 프로그램을 제공했습니다. 가장 간단한 경우, pintos 인수로 pintos를 호출할 수 있습니다.... 각 인수는 작동하도록 Pintos 커널에 전달됩니다. 시도해보십시오. 먼저 새로 생성된 build디렉토리 로 cd하십시오 . 그런 다음 명령 pintos run alarm-multiple을 실행하면 run alarm-multiple 인수를 Pintos 커널에 전달합니다. 이 인수에서 run은 테스트를 실행하도록 커널에 지시하고 alarm-multiple은 실행할 테스트입니다. Pintos는 몇 화면 분량의 텍스트를 출력하는 다중 알람 테스트 프로그램을 부팅하고 실행합니다.

명령줄에서 리디렉션하여 직렬 출력을 파일에 기록할 수 있습니다(예: pintos -- run alarm-multiple > logfile. pintos 프로그램은 qemu 또는 가상 하드웨어를 구성하기 위한 몇 가지 옵션을 제공합니다. 옵션을 지정하는 경우 Pintos 커널에 전달된 명령 앞에 오고 로 구분해야 --전체 명령 pintos option... -- argument....이 사용 가능한 옵션 목록을 보기 위한 인수 없이 Pintos를 호출하는 것처럼 보입니다 . 옵션에는 다음이 포함됩니다.
VM 출력을 표시하는 방법: -v VGA 디스플레이를 끄거나 -s stdin에서 직렬 입력을 억제하고 stdout으로 출력하는 데 사용합니다. Pintos 커널에는 실행 이외의 명령과 옵션이 있습니다. 이것들은 지금으로서는 그다지 흥미롭지 않지만 -h, 예를 들어 를 사용하여 그것들의 목록을 볼 수 있습니다 pintos -h.

threads 파일에서 source ./activate 한 후 build 파일에 들어가기
pintos -- run alarm-multiple 로 실행
사용중인 프로세스 확인하기 ps -f
프로세스 종료 pintos -- -q run alarm-multiple

1번 프로젝트 : devices 폴더 - timer.c 에서 함수를 수정 / 추가 해야 한다.

Alarm Clock

목표 : `devices/timer.c`에 정의된 `timer_sleep()`을 다시 구현한다.

timer_sleep()은 커서를 1초에 한 번 깜박이는 것과 같이 실시간으로 작동하는 스레드에 유용하다. timer_sleep() 함수는 밀리초나 다른 단위가 아닌 타이머 눈금 단위로 표현된다. 초당 TIMER_FREQ 타이머 틱이 있으며, 여기서 TIMER_FREQ는 devices/timer.h에 정의된 매크로이며, 기본값은 100이다. 이 값을 변경할 경우 많은 테스트가 실패할 수 있으므로 이 값을 변경하지 않는 것이 좋다.

Pintos에서는 알람 기능이 Busy waiting을 이용하여 구현되어 있는데, 이는 매우 비효율적으로 많은 CPU 시간을 낭비하게 하므로 sleep/wake up을 이용하여 다시 구현한다.

Busy waiting 이란?

Thread가 CPU를 점유하면서 대기하고 있는 상태이다.
timer.c 파일 안의 코드를 보자.

/* devices/timer.c */
void timer_sleep (int64_t ticks) {
  int64_t start = timer_ticks ();
  while (timer_elapsed (start) < ticks) 
    thread_yield ();
}

while문을 보면, ticks 만큼 계속해서 현재 CPU 점유를 다른 Thread에게 양보(yield)하여 ready_list의 가장 마지막 순서에 넣어주고 있다.

이는 CPU 자원과 소모 전력이 불필요하게 낭비될 수 있다.

왜냐면 ready queue에 있는 Thread들이 자신의 의지와 상관없이 깨워져 ready state 에서 running state가 되는데, 깨어난 후 자신이 작동할 시간이 되었는지 체크하고 아직 시간이 되지 않았다면 다시 ready state로 돌아가게 된다.
이렇게 계속해서 잠들고 깨워지고 시간 확인하고 잠들고 깨워지고.. 를 무한 루프를 돌면서 반복 체크를 하게 되기 때문에 CPU 자원을 낭비하게 된다.

구현

1. wakeup_tick 으로 깨어나야 할 tick을 저장할 변수 추가한다

/* pintos/src/thread/thread.h */
struct thread{
...
int64_t wakeup_tick;
...
}

2. `sleep_list`와 `next_tick_to_awake`함수를 추가한다.

/* pintos/src/thread/thread.c */


/* Alarm System Call 전역변수 추가 */
static struct list sleep_list;			/* THREAD_BLOCKED 상태의 스레드를 관리하기 위한 리스트 자료 구조 추가 */
static int64_t next_tick_to_awake;		/* sleep_list에서 대기중인 스레드들의 wakeup_tick 값 중 최솟값을 저장하기 위한 변수 추가 */

...

void thread_init(void) {
...
list_init (&sleep_list);		/* sleep_list를 초기화 (추가) */
...
}

3. next_tick_to_awake 변수를 업데이트한다.

/* Alarm Clock 추가. 최소 틱을 가진 스레드 저장 */
void update_next_tick_to_awake(int64_t ticks){
	/* next_tick_to_awake가 깨워야 할 스레드 중 가장 작은 tick을 갖도록 업데이트 한다. */
	next_tick_to_awake = (next_tick_to_awake > ticks) ? ticks : next_tick_to_awake;
}

4. 실행중인 스레드를 재우는 thread_sleep을 구현한다.

/* Alarm Clock 추가. 실행 중인 스레드를 슬립으로 만듦, 인자로 들어온 ticks까지 재움 */
// Thread를 blocked 상태로 만들고 sleep queue에 삽입하여 대기, timer_sleep()함수에 의해 호출됨. 
void thread_sleep(int64_t ticks) {
	struct thread* curr;

	enum intr_level old_level;
	old_level = intr_disable(); // 이 라인 이후의 과정 중에는 인터럽트를 받아들이지 않는다
	// 다만 나중에 다시 받아들이기 위해 old_level에 이전 인터럽트 상태를 담아둔다

	curr = thread_current(); // 현재의 thread 주소를 가져온다
	ASSERT(curr != idle_thread); // 현재의 thread가 idle thread이면 sleep 되지 않아야 함.

	// awake함수가 실행되어야 할 tick값을 update
	update_next_tick_to_awake(curr->wakeup_tick = ticks); // 현재의 thread의 wakeup_ticks에 인자로 들어온 ticks를 저장후 next_tick_to_awake를 업데이트한다
	list_push_back(&sleep_list, &(curr->elem)); // sleep_list에 현재 thread의 element를 슬립 리스트(슬립 큐)의 마지막에 삽입한 후에 스케쥴한다.

	thread_block(); // 현재 thread를 block 시킴. 다시 스케쥴 될 때 까지 블락된 상태로 대기

	/* 현재 스레드를 슬립 큐에 삽입한 후에 스케쥴 한다. 해당 과정 중에는 인터럽트를 받아들이지 않는다. */

	intr_set_level(old_level); // 다시 스케쥴하러 갈 수 있게 만들어줌 (인터럽트를 다시 받아들여서 인터럽트가 가능하도록 수정함)
	/* 여기서 현재 스레드가 idle thread 이면 sleep 되지 않도록 해야한다. idle 스레드는 운영체제가 초기화되고 ready_list가 생성될때 첫번째로 추가되는 스레드이다. 
		굳이 이 스레드를 만들어준 이유는 CPU를 실행상태로 유지하기 위함이다.
		CPU가 할일이 없으면 아예 꺼져버리고, 할 일이 생기면 다시 켜지는 방식이므로 소모되는 전력보다 무의미한 일이라도 그냥 계속 하고 있는게 더 적은 전력을 소모한다. */
}

Thread를 깨우는 thread_awake 함수를 구현한다.

/* Alarm Clock 추가. wakeup_tick값이 ticks보다 작거나 같은 스레드를 깨움, 
	현재 대기중인 스레드들의 wakeup_tick변수 중 가장 작은 값을 next_tick_to_awake 전역 변수에 저장 */
void thread_awake(int64_t ticks) {
	struct list_elem *e = list_begin(&sleep_list);
	while (e != list_end (&sleep_list)) {
		struct thread *t = list_entry(e, struct thread, elem);
		if (t -> wakeup_tick <= ticks) {
			e = list_remove(e);
			thread_unblock(t);
		}
		else 
			e = list_next(e);
	}
}

6. devices/timer.c에서 Busy waiting부분을 삭제하고 새로 구현한 thread_sleep 함수를 넣어준다.

void // timer_sleep() 함수가 호출되면, 해당 스레드는 ready상태가 아닌 blocked상태로 전환된다. blocked된 스레드들은 일어날 시간이 되면 일어나야 한다.
timer_sleep (int64_t ticks) { // system timer : 초당 100회의 ticks 발생. (1 tick = 10ms)
	/* Busy waiting : Thread가 CPU를 점유하면서 대기하고 있는 상태. CPU 자원이 낭비 되고, 소모 전력이 불필요하게 낭비될 수 있다. */
	int64_t start = timer_ticks ();
	ASSERT(intr_get_level() == INTR_ON);

	/* Busy waiting */
	/* 현재 while문 안에서 인자로 받은 ticks 만큼 계속해서 현재 CPU 점유를 다른 스레드에게 양보하고 ready_list의 제일 뒤로 넣어주고 있다. 
		즉, 계속해서 무한 루프를 돌면서 체크를 하기 때문에 CPU 자원을 낭비하게 된다. */
// 기존의 busy waiting을 유발하는 코드 삭제. #ifdef로 묶어준다
// 	while (timer_elapsed (start) < ticks)
// 		thread_yield ();

/* 새로 구현한 thread를 sleep queue에 삽입하는 함수를 호출한다 */
	thread_sleep(start + ticks); // 원래 시작 시간 + 틱 시간
}

7. 매 tick마다 sleep queue에서 깨어날 thread가 있는지 확인하여, 깨우는 함수를 호출하도록 한다.

/* pintos/src/device/timer.c */
static void timer_interrupt (struct intr_frame *args){
...
if(get_next_tick_to_awake() <= ticks){
thread_awake(ticks);
}
}

Priority scheduling

기존에 구현한 alarm-clock에서의 thread들은 FIFO 방식으로 스케쥴링된다. 단순히 FIFO 방식으로 구현이 되는 것을 우선순위를 주는 방식으로 개선을 해볼 수 있다. 이것이 priority scheduling이다.
ready_list에 들어가는 스레드들이우선순위순으로 정렬이 되도록 하면 된다. 이때 조금 신경써서 생각해야 할 부분은 현재 실행 중인 스레드보다 우선순위가 더 높은 스레드가 만들어질 때 선점이 일어나도록 구현을 해야한다.

방법

새로 추가된 thread가 실행 중인 thread보다 우선순위가 높은 경우 CPU를 선점하도록 하기 위해서 thread_create() 함수 수정

tid_t thread_create(const_char *name, int priority, thread_func *function, void *aux)
{
...
thread_unblock(t);
thread_test_preemption(); /* Priority Scheduling 추가 */
...
}

thread가 unblock 될 때 우선순위 순으로 정렬되어 ready_list에 삽입되도록 수정

void
thread_unblock (struct thread *t) {
	'''
	list_insert_ordered(&ready_list, &t->elem, thread_compare_priority, 0); /* Priority Scheduling 추가 */
	'''
}

현재 thread가 CPU를 야야보하여 ready_list에 삽입될 때 우선순위 순서로 정렬되어 삽입되도록 수정

void thread_yield(void){
	'''
		if (curr != idle_thread){
			list_insert_ordered(&ready_list, &curr->elem, thread_compare_priority, 0); /* Priority Scheduling 추가 */
		}
   '''
}

스레드의 우선순위가 변경되었을 때 우선순위에 따라 선점이 발생하도록 하기 위해 thread_set_priority()함수 수정

void
thread_set_priority (int new_priority) {
  thread_current ()->init_priority = new_priority;
  thread_test_preemption (); /* Priority Scheduling 추가 */
}

선점을 실행하기 위한 thread_test_preemption() 함수 추가. ready_list에서 우선순위가 가장 높은 스레드와 현재 스레드의 우선순위를 비교하여 스케줄링 하도록 함수를 짜줘야 함.
```
void thread_test_preemption (void){
   if (!list_empty (&ready_list) && thread_current ()->priority < list_entry(list_front(&ready_list), struct thread, elem)->priority){
		thread_yield ();
	}
}
```

list를 sort할 때나 정렬된 상태로 넣을 때 우선순위로 정렬되게 하기 위한 비교함수를 추가

bool thread_compare_priority (struct list_elem *l, struct list_elem *s, void *aux UNUSED) {
  return list_entry (l, struct thread, elem)->priority > list_entry (s, struct thread, elem)->priority;
}

WIL을 팀별로 파트를 나눠서 써서
Priority 부분은 팀원의 글을 가져왔다....

Priority scheduling

기존에 구현한 alarm-clock에서의 thread들은 FIFO 방식으로 스케쥴링된다. 단순히 FIFO 방식으로 구현이 되는 것을 우선순위를 주는 방식으로 개선을 해볼 수 있다. 이것이 priority scheduling이다.

ready_list에 들어가는 스레드들이 우선순위순으로 정렬이 되도록 하면 된다. 이때 조금 신경써서 생각해야 할 부분은 현재 실행 중인 스레드보다 우선순위가 더 높은 스레드가 만들어질 때 선점이 일어나도록 구현을 해야한다.

그리고 스레드들은 preemptive해서 우선순위가 높은 스레드가 생긴다면 자원을 빼앗길 수 있다.

Priority scheduling - syncronization

이전까지는 동기화 해야하는 자원이 프로세서였다면, 그 상태에서 다른 공유자원까지 동기화가 되어야 하는 상황이다. 이를 동기화를 위해서 semaphore, lock, condvar(monitor, 정확히는 monitor에서 특수한 상황)을 이용하고, 그 자원들에 대해서 우선순위가 높은 스레드가 높은 우선순위를 가지고 대기할 수 있도록 한다.

주의) lock, semaphore을 쓴다는 것은 임계영역이 생긴다는 것이고, 임계영역에서는 atomic하게 실행될 수 있어야 한다. 더 높은 우선순위를 가진 스레드가 이 공유자원까지 preempt해버린다고 생각해버리면 안된다.

즉, synchronization하고자 하는 자원이 어떤 자원인지 잘 구별해서 생각해야한다. 이전까지는 공유하는 자원은 프로세서였고 preemptive가 가능한 상황이었고, 이런 상황에서 다른 공유자원이 있는데 임계영역에 대해서는 atomic하게 이뤄져야 한다. 그래서 프로세서를 빼앗길 수는 있어도 지금 lock을 건 공유자원을 빼앗겨서는 안된다.

바로 이 글을 본다면 이해가 안될 수 있지만, priority inversion problem을 donation으로 해결하는 과정을 통해 위 말이 어떤 말인지 이해할 수 있을 것이다.

위는 waiters가 FIFO로 구현되어 있는 상황이다.

위는 waiters를 priority로 개선한 것인데, 눈치가 빠른사람이라면, 여기서 core 개수가 thread 수 보다 충분히 많아서 preemption이 일어나지 않는 상황을 전제로 한 것이다. -> 이 문제는 아래의 priority inversion problem이라는 상황에서 donation이라는 기법을 통해 해결하는 것을 알 수 있다.

Priority inversion problem - donation

위와 같은 상황에서는 core의 개수가 충분하여 preemption이 일어나지 않는 상황을 가정했다면 이번에는 그런 상황이 아니라, thread의 우선순위에 따라 preemption이 일어나고 그랬을 때 발생하는 priorty inversion problem을 donation으로 해결하는 상황이다.

아래의 그림과 같이 preemption이 일어나면 우선순위가 높으 스레드가 우선순위가 낮은 스레드를 기다리는 priority inversion problem이 일어난다.

Lock을 걸었으면 critical area를 침범하지 않으면서 프로세스가 진행되어야 하는데 파란색 스레드는 lock을 요구하지 않고, critical area에 접근하지 않는 스레드라고 보면 된다.

위와 같은 상황을 아래의 donation으로 해결할 수 있다.

위는 donation을 하면서 inversion problem이 일어나지 않는 것을 확인할 수 있다. 또한 lock 영역에 대해 atomic하게 하는 효과를 보이는듯 하기도 하다.

추가적으로 multiple donation과 nested donation이 발생하는 상황을 고려할 수 있는데, 이는 위 개념을 제대로 이해했다면 핀토스 pdf자료를 바탕으로 이해할 수 있을 것이다.

코드

priority inversion problem을 donation으로 해결 했다.
구현의 과정은 핀토스 pdf를 참고하는 게 좋고, 구현한 내용은 아래 링크로 첨부한다.

https://github.com/Yerimi11/pintos-kaist-team09/tree/yerim_donate

novxerim

블로그 이전했습니다. https://yerimi11.tistory.com/

이전 포스트

[WEEK07] 네트워크 - Tiny.c, Proxy.c (코드&주석)

다음 포스트

[PintOS] Project 1 - Alarm Clock, Priority, Donate

SW-Jungle

PintOS 실행하기

핀토스 실행

Alarm Clock

목표 : `devices/timer.c`에 정의된 `timer_sleep()`을 다시 구현한다.

Busy waiting 이란?

구현

1. wakeup_tick 으로 깨어나야 할 tick을 저장할 변수 추가한다

2. `sleep_list`와 `next_tick_to_awake`함수를 추가한다.

3. next_tick_to_awake 변수를 업데이트한다.

4. 실행중인 스레드를 재우는 thread_sleep을 구현한다.

6. devices/timer.c에서 Busy waiting부분을 삭제하고 새로 구현한 thread_sleep 함수를 넣어준다.

7. 매 tick마다 sleep queue에서 깨어날 thread가 있는지 확인하여, 깨우는 함수를 호출하도록 한다.

Priority scheduling

방법

Priority scheduling

Priority scheduling - syncronization

Priority inversion problem - donation

코드

[WEEK07] 네트워크 - Tiny.c, Proxy.c (코드&주석)

[PintOS] About OS, Process, Thread

0개의 댓글

[PintOS] Project 1 - Alarm Clock, Priority, Donate

SW-Jungle

PintOS 실행하기

핀토스 실행

Alarm Clock

목표 : devices/timer.c에 정의된 timer_sleep()을 다시 구현한다.

Busy waiting 이란?

구현

1. wakeup_tick 으로 깨어나야 할 tick을 저장할 변수 추가한다

2. sleep_list와 next_tick_to_awake함수를 추가한다.

3. next_tick_to_awake 변수를 업데이트한다.

4. 실행중인 스레드를 재우는 thread_sleep을 구현한다.

6. devices/timer.c에서 Busy waiting부분을 삭제하고 새로 구현한 thread_sleep 함수를 넣어준다.

7. 매 tick마다 sleep queue에서 깨어날 thread가 있는지 확인하여, 깨우는 함수를 호출하도록 한다.

Priority scheduling

방법

Priority scheduling

Priority scheduling - syncronization

Priority inversion problem - donation

코드

[WEEK07] 네트워크 - Tiny.c, Proxy.c (코드&주석)

[PintOS] About OS, Process, Thread

0개의 댓글

목표 : `devices/timer.c`에 정의된 `timer_sleep()`을 다시 구현한다.

2. `sleep_list`와 `next_tick_to_awake`함수를 추가한다.