[SW 정글 58일차] Pintos Project 1. Alarm clock

오늘부터 PintOs project 1. Alarm clock 구현에 들어가기 시작했다.

일단은 https://casys-kaist.github.io/pintos-kaist/에 설명되어있는 우리가 해결해야할 과제를 파악했다.

 

 

 

1. 내가 해결해야할 것은?

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

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

Pintos에서 기본적으로 구현한 timer_sleep()함수의 구조는 위와 같다.

timer_sleep()은 인자로 받은 ticks시간만큼 어떠한 쓰레드를 잠들게 하는 것(running 상태에서 벚어나는 것)이다.

문제는 스레드를 잠들게 하고 난 이후이다.

코드를 보면 잠들게 한 이후에 얼마나 시간이 흘렀는지와 ticks(우리가 설정한 잠든 시간)보다 작은지를 계속 확인하면서 자신(스레드)가 일어날 시간인지 확인하는 것이다.

조금 더 명시적으로 설명하면 다음과 같다.

A는 3시간 이후에 일어나기로 했다. 1분 후에 3시인가? 아니네.. 다시 1분 후에 3시인가? 아니네... 이러한 행동을 반복하는 것이다.

 

이것은 계속해서 CPU를 점유하는 현상을 일으키는 것이고 busy waits현상이다.

조금 더 컴퓨터 시스템적으로 얘기를 해보자.

running 상태인 스레드가 timer_sleep()을 만나게 되면 정해진 시간동안 잠을 자게 된다.

잠을 자는 동시에 잠을 잔 시간과 정해진 시간(ticks)와 비교를 하면서 계속 running상태로 전이를 하는 것이다.

이 문제를 해결하기 위해 reimplement를 해야한다.

 

 

 

2. 코드 파헤치기

일단은 문제를 파악하였고 문제를 해결하기 위해서는 기존에 설계된 코드를 파악해야한다고 생각했다.

중요하다고 생각하는 것은 thread.h 파일과 thread.c 파일에 구현된 것이다.

 

- 스레드의 상태를 나타낼 수 있는 구조체 (thread.h)

/* States in a thread's life cycle. */
enum thread_status {
	THREAD_RUNNING,     /* Running thread. */
	THREAD_READY,       /* Not running but ready to run. */
	THREAD_BLOCKED,     /* Waiting for an event to trigger. */
	THREAD_DYING        /* About to be destroyed. */
};

해당 구조체에는 스레드의 상태 종류를 담고 있다.

코드를 보면 알 수 있듯이, running, ready, blocked, dying이 있다.

위 구조체를 이용하여 각각의 스레드의 상태정보를 저장할 수 있다.

 

 

- 각 스레드의 정보를 담는 구조체 (thread.h)

struct thread {
	/* Owned by thread.c. */
	tid_t tid;                          /* Thread identifier. */
	enum thread_status status;          /* Thread state. */
	char name[16];                      /* Name (for debugging purposes). */
	int priority;                       /* Priority. */

	/* Shared between thread.c and synch.c. */
	struct list_elem elem;              /* List element. */

	/* Owned by thread.c. */
	struct intr_frame tf;               /* Information for switching */
	unsigned magic;                     /* Detects stack overflow. */
};

tid는 스레드의 식별자를 의미하고 모든 스레드는 중복되지 않은 tid를 가지고 있다.

status는 스레드의 상태정보를 가지고 있는 것이다.

name[16]은 name은 스레드의 이름을 문자열로 담고 있다.

priority는 스레드에게 우선순위를 매긴다.

elem은 doubly linked list에 스레드를 넣는 것이다.

tf는 context switching을 위한 정보를 저장하는 것이다.

magic은 항상 THREAD_MAGIC이라는 값을 가지는데 이것은 스택의 overflow를 감지하고자 할 때 쓰인다.

 

 

위에서는 thread.h파일에 선언된 구조체가 어떠한 것들을 가지고 있는지 알아보았다.

다음부터 알아 볼 것은 thread.c파일에 있는 thread functions인데 모두 다 보면서 정리하기에는 시간이 없고 많이 사용되는 함수만 알아보려고 한다.

 

- void thread_init (void);

 

 

thread_init()함수는 main()이 실행될 때 call되는 함수로 Pintos의 initial thread, 즉 main 스레드를 생성하는 역할을 한다.

main 스레드를 생성하기 전에 tid_lock list, ready_list list, bdestruction_req list를 초기화해준다.

 

 

-void thread_start (void);

thread_start()함수도 main()에서 호출되는 스케쥴러를 시작하기 위한 함수이다.

일단은 idle thread를 만들어서 ready 상태인 스레드가 없을 경우에 스케쥴러가 돌도록 해준다.

idle 스레드란 운영체제가 초기화되고 ready_list가 생성되는데 이때 ready_list에 첫번째로 추가되는 스레드다.
이 스레드가 필요한 이유는 CPU가 실행상태를 유지하기 위해서는 실행할 스레드 하나 필요해서 입니다.
CPU가 할일이 없으면 아얘 꺼져버렸다가 할일이 생기면 다시 켜는방식에서 소모되는 전력보다 무의미한 일이라도 하고 있는게 더 적은 전력을 소모하기 때문이다.

interrupt enable하게(intr_enable()) 해주어서 time interrupt에 의해 스케쥴러가 돌 수 있도록 해준다.

 

 

- void thread_tick (void);

매 tick마다 타이머 인터럽트에 의해 호출되는 함수이다.

이 함수를 통해 스레드(idle, kernel)별 tick이 얼마나 이루어졌는지의 통계량을 내고 TIME_SLICE(여기서는 4로 설정)보다 현재 running 상태인 thread의 tick이 크면 yield가 진행되도록 설정을 해준다.

 

 

- tid_t thread_create (const char *name, int priority, thread func *func, void *aux);

인자로 받은 name으로 nammed된 새로운 스레드를 만드는 역할을 하는 함수이다.

반환 값은 새로운 스레드의 tid값이고 스레드는 aux 인자로 하여 func을 실행한다.

그리고 page와 stack 영역을 할당받고 스레드 구조체의 멤버를 초기화를 진행한다.

init_thread()를 하면 초기 스레드 상태가 BLOCKED인데 return을 하기 전에 thread_unblock()을 실행시켜 새로운 스레드가 READY상태가 되고 ready_list에 들어가 스케쥴링되도록 해준다.

 

 

 

3. 과제 구현

구현의 원리는 다음과 같다.

일단은 현재 running 상태인 스레드가 sleep(block)시켜주는 함수를 마주치면 ready_list에 들어가서 계속 running 상태가 되는 것을 바꿔줘야한다.

즉, 새로운 list인 blocked_list를 만들어주어서 sleep()함수를 만나면 blocked_list로 넣어주게끔 해야한다.

/* List of processes in THREAD_BLOCKED state, that is, processes
   that are ready to be waiting for something. */
static struct list blocked_list;

blocked_list에는 스레드의 상태가 BLOCKED인 스레드만 모여있는 것으로 추후에 깨어날 시간이 된 쓰레드가 있으면 꺠워주고 다시 ready 상태로 바꿔주고 ready_list에 넣어주는 것이다.

 

그리고 깨워준다는 기준이 될 비교값(스레드가 잔 시간)이 있어야하므로 스레드 구조체에 멤버 하나를 추가한다.

struct thread {
	/* Owned by thread.c. */
	tid_t tid;                          /* Thread identifier. */
	enum thread_status status;          /* Thread state. */
	char name[16];                      /* Name (for debugging purposes). */
	int priority;                       /* Priority. */

	/* Shared between thread.c and synch.c. */
	struct list_elem elem;              /* List element. */

#ifdef USERPROG
	/* Owned by userprog/process.c. */
	uint64_t *pml4;                     /* Page map level 4 */
#endif
#ifdef VM
	/* Table for whole virtual memory owned by thread. */
	struct supplemental_page_table spt;
#endif

	/* Owned by thread.c. */
	struct intr_frame tf;               /* Information for switching */
	unsigned magic;                     /* Detects stack overflow. */
	int64_t wake_time;             /* the time is thread wake up*/
};

 

여기서 추가적으로 생각해볼 것은 sleep_list에 그냥 tail에 넣어줄지, 잔 시간을 기준으로 정렬된 상태가 유지되도록 넣어줄지이다.

나는 그냥 tail에 넣어주는 것으로 구현을 했다.

일단은 직접 머릿 속으로 그린대로 구현해보려고 했지만 설정해주어야할 값들이 너무 많아서 시간 상 이것만 붙잡고 있지 못하는 상황이라서 다른 오픈소스 코드를 참고했다.

코드는 아래 깃헙에 저장되어 있다.

https://github.com/JJong-Min/pintos-kaist

 

 

---

[오늘의 나는 어땠을까?]

오늘은 운영체제 개념 공부를 마치고 과제 구현에 돌입했다.

내가 계획했던 것보다 오전, 오후 시간을 다른 곳에 쓰느라 구현 시작이 늦어졌다.

하지만 빠르게 시작한 동료들의 도움 덕분에 이해하는데 어려움이 없었고 항상 나에게 도움을 주는 동료들에게 감사하다.

내일은 다음 주제를 보고 구현을 해야한다.

목표는 빠르게 해결하고 다시 운영체제 개념 공부를 하는 것이다.

아직 놓친 것들이 많아서 빨리 개념 공부를 하고 싶다.