[TIL][Project 1] process & thread in PintOS + Alarm Clock

오늘의 할일 

process와 thread , 그리고 핀토스 내에서 어떻게 구현되었는지 살펴보기

마저 alram 해결하기.

Process, Thread + PintOS

process는 실행 중인 프로그램의 instance이다.
thread는 프로세스 내에서 실행되는 실행의 단위. 

Process

A process is a program in execution

시분할(time sharing) 기법을 통해 CPU를 가상화하는데, 이를 구현하기 위해 매커니즘(mechanism)과 운영체제의 스케줄링 정책(scheduling policy)이 필요하다. 

구성 요소

1. 주소 공간(address space)
   • 실행 중인 프로그램이 읽고 쓰는 데이터와 명령어가 저장되는 메모리 공간. 프로세스마다 하나씩 존재한다.

     

2. 레지스터
   • 프로그램 카운터(program counter, PC) / 명령어 포인터(instruction Pointer, IP) : 프로그램의 어떤 명령어가 실행 중인지 알려줌
   • 스택 포인터(stack pointer): 함수의 변수 저장하는 스택 관리하는 레지스터
   • 프레임 포인터(frame pointer): 리턴 주소를 저장하는 스택 관리하는 레지스터

 

운영체제에서 제공하는 프로세스 API

create(생성), destroy(제거), wait(대기), Miscellaneous Control(각종 제어), status(상태)

thread는 그 안에서 실행되는 자원을 공유하는 별개의 흐름

프로세스 생성 (process creation) 

프로세스는 실행 중인 프로그램의 instance이다. 프로세스를 생성한다는 것은 프로그램을 실행한다는 것과 같다. (정확히는 프로그램이 프로세스로 변형되는 것 같다.)

1. 먼저 디스크에 있는 코드와 정적 데이터를 메모리 어딘가에 탑재(load)한다. 이 코드와 정적 데이터는 실행 파일 형식으로 존재하며, OS는 이 로딩(loading)을 lazy하게 수행한다. 즉, 프로그램을 실행하며 그때그때 코드와 데이터가 필요할 때 paging과 swapping을 활용하여 메모리에 올린다.
   • 디스크 상의 프로그램(데이터)를 찾아서, 프로세스의 주소 공간으로 읽어들인다. load 후 실행 전에, runtime stack용도로 일정량의 메모리가 할당되는 듯 하다. 
2. 그 다음, 프로그램의 runtime stack이 할당하고 stack을 초기화한다. 여기서 초기화한 stack은 프로그램 내에서 실행될 local variables이나 함수, 리턴 주소 값을 저장하는 데 쓰인다. 동시에 프로그램의 heap을 생성한다. 이 heap은 malloc으로 메모리를 요청하면 os가 메모리를 할당할 때 쓰일 것이다. 
3. 마지막으로 OS가 입출력의 setup을 초기화한다. 각 프로세스들은 기본적으로 세 가지 파일 디스크립터를 가진다. 
   1. Standard In ( STDIN )
   2. Standard Out ( STDOUT )
   3. Standard Error ( STDERROR ) 

 

프로세스 상태(State) /생명주기 

공룡 책

위키피디

어쩐지, wating과 ready 개념과 관련한 용어들이 wikipedea에서는 'ready'와 waiting을 함께 혼용하지만 서적은 위키피디아에서는 block으로 쓴 개념을 waiting으로 표기하는 등...  꽤 다르다. 향후 면접 혹은 사람들과 대화할 때 이 부분에 대해 조심해야 할 것 같다. 일단, 이 포스트는 한국어로는 '운영체제 세 가지 이야기' 에서 다루는 용어를 기준으로 삼았다.

New 생성 - Ready 준비 - Running 실행 - Waiting(Blocked) 대기 - (Running) - Terminated(Exit) 종료

 

프로세스가 실행되고 난 뒤에, 프로세스는 현재 그 프르세스가 현재 어떤 활동을 하는지에 따라 상태를 바꾼다. 생성, 준비, 실행, 대기, 그리고 마지막으로 종료 상태이다. 생성은 프로세스가 막 생성된 시점의 상태이고, 실행은 명령어가 실행중인 상태를 뜻한다. 준비는 프로세스가 프로세서에게 배치되기 위해 기다리는 상태이며, 대기는 프로세스가 어떤 이벤트가 발생하기를 기다리고 있는 상태이다. 종료 상태는 프로세스가 실행을 끝마친 시점의 상태이다.오직 하나의 프로세스만이 하나의 프로세서 코어에서 실행될 수 있다는 점이 중요하다!

 

이 중 ready(준비)와 wating(대기)의 상태에 대해 다시 짚어야 할 거 같다. 

준비(ready)상태는 실행(running)되기를 기다린다. 스케쥴러가 dispatch 하면, 이 프로세스는 실행된다. 

대기(wait) 상태는 준비(ready) 되기를 기다린다. 이것은 I/O 완료(키보드 입력 등)나 어떤 이벤트가 신호를 주면 ready queue에 들어간다. 

실행 중(running)인 프로세스는 interrupt를 받으면 준비ready 상태가 되며, I/O 신호나 event발생시 대기waiting 상태가 된다.

Preemptive scheduler 선점 스케쥴러	Non preemptive scheduler 비선점 스케쥴러
Waiting > Ready	Running -> Ready
Running -> Wating	Running -> waiting
Running -> Ready	Exit
New -> Ready
Exit

 

 

프로세스 제어 블록 (Process  Control  Block)

 

OS가 프로세스를 관리하기 위한 정보를 저장하는 자료구조이다.

프로세스의 상태, 프로세스가 다음에 실행할 명령어 주소를 나타내는 counter, interrupt 발생시 정보를 저장하고 향후 다시 실행 상태로 되돌아올 시 복구할 정보를 담는 register, CPU 스케쥴링하는 queue에 대한 포인터(정보), 등... 어떤 프로세스를 시작하고, 재실행하기 위한 모든 정보를 저장하는 저장소이다. 

여기에 멀티 스레드 프로세스를 지원하는 시스템은 PCB에 스레드에 대한 정보를 저장할 수 있게 확장된다고 한다. 

 

핀토스: process ; https://cs162.org/static/proj/pintos-docs/docs/processes/ 

Thread

A thread is a basic unit of CPU utilization
-

Thread는 process 내에서 실행된다. 여러 스레드가 하나의 프로세스 안에서 실행된다면, 그 뜻은 그 프로세스가 할당 받은 자원들, 그리고 code section, data section과 같은 것들, 그리고 OS가 제공하는 자원(파일 열기나 signal)들을 공유하고 있다. 전통적으로는, 그리고 pintOS가 그러하듯, 하나의 프로세스에는 하나의 스레드가 존재하고 하나의 테스크만 처리한다. 프로세스의 실행 단위가 바로 스레드이기 때문이다. 그러나 프로세스가 멀티 스레드를 지원한다면 그 프로세스는 여러 테스크를 동시에 처리한다. 

아래 그림은 공룡책에서 가져온 것인데, 공통된 process에서 thread가 공유하는 것들(코드, 데이터, 파일)과 각 스레드 별 개별로 갖고 있는 것들(register, pc, stack)에 대해 잘 보여준다. 

그러면 왜 OS는 이런 multithread를 사용하는 걸까? 프로세스를 여러 개 띄우면 되지 않을까? 일반적으로는 여러 스레드를 포함하는 하나의 프로세스를 사용하는 것이 효율적이다. 왜냐하면 스레드들은 그것들이 속한 프로세스의 자원을 공유하기 때문에 context switch 시 시간과 메모리 소비가 적다.

 

 

ubunto에서 ps -ef 커멘드를 사용할 시 보이는 리눅스에서 돌아가는 커널 스레드 리스트. 더 있다. 여기서 kthreadd(pid 2)가 다른 커널 스레드의 부모 역할을 한다.

 

그러나 단점 또한 존재한다. 바로 동기화 문제이다. 이건 다음에 포스트하기로 한다.

 

---

PintOS에서 Process와 Thread 

구현하면서 느끼기로는, pintOS에서 thread 구조체 코드를 보면 pintOS에서는 구현상으로는 process와 thread의 차이가 없는 것 같이 보였다.... 주어진 thread 구조체 내부를 까보면, ID(identifier), 상태(status)가 존재하며 따라서 ready list 등에 들어가는 건 이 thread구조체로 구현된 것들이다!  그래서 처음엔 pintOS가 single process single thread... 라고 생각했는데, 착각인 것 같다. 실행 흐름을 살펴보면, load하여 올려놓은 하나의 프로세스 내부에서 여러 thread가 바쁘게 움직이고, 이것을 스케쥴링해야 했다. 따라서 single process, multi thread. 같다. 이게 꽤 헷갈렸는데, 다른 팀의 이야기를 들어보면, 일부러 thread를 감싸고, PID, process status등을 포함하는 struct를 구현해 이론으로 배운 process-thread를 구현한 팀도 있다고 들었다. 

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. */
};

 

상태 전이는 ready list (queue) 와 sleep_list로 구현한다. 

/* List of processes in THREAD_READY state, that is, processes
   that are ready to run but not actually running. */
static struct list ready_list;

/* 준비 상태 이전의 대기큐입니다. */
static struct list sleep_list;

---

Alarm Clock

Reimplement timer_sleep(), defined in devices/timer.c.

위에서 OS는 가상화를 실현하기 위해 프로세스(실행 중인 프로그램)를 일정 주기로 CPU 제어권을 주어(자원을 할당) 여러 프로그램이 동시에 실행되는 듯한 환상을 준다고 공부했다. 그렇다면 그것을, OS는 어떻게 구현했을까? 바로 프로세스를 재우고(sleep), 알람으로 깨워서(awake) 실행한다.

tick / timer

tick: 현재 스레드를 인자로 받은 ticks (시간) 동안 잠재운다. 여기서의 tick은 pintOS 내부에서 시간 측정에 사용되는 값으로, HW에 전원이 들어온 이후 1ms(밀리세컨드, 1/1000초)에 1씩 증가하는 것으로 기본 설정되어 있다. 

timer: 일정 시간 단위(tick)를 세고 일정 시간마다 cpu에 interrupt를 날려 현재 cpu를 점령하고 있는 스레드의 제어권을 빼앗고, 다음 스레드에게 cpu 주도권을 넘겨준다.

Sleep / Awake

Sleep과 Awake

Sleep은 ready가 아닌 blcok상태로 만드는 것이다. 어떻게 구현해야할까?

잠드는(sleep, blocked) 상태를 관리하는 리스트를 만들어 그곳에 추가한다. 

ready list에 삽입함으로써 thread를 ready 상태로 만든 것처럼, sleep list 구조를 생성함으로써 blcok 한다. 

이럴 경우 ready list와 분리되고, 일정 시간 동안 (ready list에 존재하지 않으므로) 불필요하게 cpu 를 점유하지 않을 것이다.

struct thread, sleep_list, thread_init()

/* List of processes in THREAD_READY state, that is, processes
   that are ready to run but not actually running. */
static struct list ready_list;

/* 준비 상태 이전의 대기큐입니다. */
static struct list sleep_list;

//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. */

	/* 깨어나야 할 틱 저장 */
	int64_t wake_up_ticks;
   ...
   }
   
  //thread.c
  // in thread_init()
  /* Init the globla thread context */
	lock_init (&tid_lock);
	list_init (&ready_list);
	list_init (&sleep_list);

 

 

언제 일어나지?

각 thread에 언제 일어날 것인지에 대한 정보도 넣어준다. 스레드 구조체에 일어날 시간을 저장할 수 있는 필드를 추가한다.

 

초기화를 잊지말자!

thread_init에서 sleep list를 ready_list와 같은 방법으로 초기화해준다. 

 

timer_sleep()

timer에 있는 기존 timer sleep 코드의 기능을  thread의 기능이 모여있는 코드는 thread.c에 정리하고자  thread.c에 옮겨서 새로 선언했다. 이때 트러블이 있었는데, thread와 timer의 기능을 두 파일(timer.c와 thread.c) 왔다 갔다 뒤죽박죽 쓰다가, 그만 코드가 먹통이 되어 다시 리셋했다... 

//timer.c

/* Suspends execution for approximately TICKS timer ticks. */
void
timer_sleep (int64_t ticks) {

	/* 기존 코드 */ 
	// int64_t start = timer_ticks();
	// int64_t end = start + ticks;
	// ASSERT(intr_get_level() == INTR_ON);
	// 현재 스레드에 깨어날 틱을 추가하고 sleep처리 
	// struct thread *current = thread_current();
	// current->wake_up_ticks = start + ticks;
    
	thread_sleep(timer_ticks()+ticks);
}

thread_sleep()

/* [ sleep list에 있는 알람시간 중 가장 이른 알람시간 ]
   가장 이른 알람시간 ≤ 현재 ticks 이면, 깨울 스레드가 없다는 의미이다. */
int64_t MIN_alarm_time = INT64_MAX;

/* 현재 실행 중인 스레드를 대기 상태로 변경하고 대기큐에 삽입한다 */
void 
thread_sleep(int64_t ticks) {
	struct thread *curr = thread_current();
    
	enum intr_level old_level;
	ASSERT(!intr_context());
	old_level = intr_disable(); //인터럽트 off
    
	if (curr != idle_thread) // 현재 스레드가 idle이 아닐 때를 체크.
		curr->wake_up_ticks = ticks; //일어날 시간을 저장
		if (MIN_alarm_time > ticks) {
			MIN_alarm_time = ticks;
		}
        
        //queue로 사용하기 위해 push back
    	list_push_back(&sleep_list, &curr->elem);
		
	do_schedule(THREAD_BLOCKED); //현재 thread를 block으로 전환
    
	intr_set_level(old_level); //인터럽트 활성on
}

 

thread.h에 선언하는 것을 잊지 말자.

이 과정에서 interrupt의 방해가 오면 안 된다.

따라서 intr_disable()와 intr_set_level(old_level)을 사용하여 인터럽트를 on / off 해야 한다. 

 

timer_interrupt ()

매 틱마다 발생하는 timer interrupt 핸들러에서 깨워야 하는 스레드가 있는지 점검한다. 팀원이 작성한 코드였는데, 알람 시간의 최솟값을 나타내는 전역변수를 설정하고, sleep list에 신규 스레드를 넣을 때 이 값을 갱신하며 순회를 할 것인지, 하지 않을 것인지부터 체크하는 기능이다. 

/* [ sleep list에 있는 알람시간 중 가장 이른 알람시간 ]
   가장 이른 알람시간 ≤ 현재 ticks 이면, 깨울 스레드가 없다는 의미이다. */
int64_t MIN_alarm_time = INT64_MAX;

/* Timer interrupt handler. */
static void
timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_tick ();

	if (MIN_alarm_time <= ticks) {
		thread_awake(ticks);
	}
}

thread_awake()

void thread_awake(int64_t ticks)
{
	struct thread *t;
	struct list_elem *now = list_begin(&sleep_list);
	int64_t new_MIN = INT64_MAX;


	while (now != list_tail(&sleep_list)) {
		t = list_entry(now, struct thread, elem);

		if (t->wake_up_ticks <= ticks) {
			now = list_remove(&t->elem);
			thread_unblock(t);
		}
		else {
			now = list_next(now);
			if (new_MIN > t->wake_up_ticks) {
				new_MIN = t->wake_up_ticks;
			}
		}
	}
	MIN_alarm_time = new_MIN;
}

sleep list를 순회하면서 현재 틱과 깨워야 할 틱을 비교한다.

현재 틱이 더 작다면 sleep list(queue)에서 제거(=unblock, ready list에 삽입)한다. 

리스트를 순회하며 최소 시간을 저장하고, 비교하며 전역변수에 선언된 최소 알람 시간을 필요시 갱신한다.

 

[잠깐!] C와 h

처음 구현 당시 실행조차 되지 않았는데, 그 이유는 h파일에 제대로 선언하지 않았기 때문이다. 왜 이런 번거로운 행위를 해주어야 하는지 궁금했는데, 찾아보니 해당 함수들이 받는 인자와 리턴 값을 정의해둠으로써 컴파일러가 타입 검사를 수행할 때 필요한 정보를 제공한다고 한다. 

 

테스트 실행

// threads/build 를 생성 후 입력!
pintos -- -q run alarm-multiple

오늘의 소감

프로세스에 대해 공부할 때에는 운영체제 세 가지 이야기를 읽고 공룡책을 보니 확실히 도움이 많이 되었다! 운영체제 서적으로 백그라운드 지식을 쌓고, 공룡책으로 확실하게 다잡을 수 있었다. 읽고 공부할수록 이 매력적인 체계와 방식, 그리고 구현에 감탄을 금치 못했다. 굉장히 문어적인 표현이지만 정말 그렇다... 

 

코드를 쓰면서 이미 주어진 코드 중에서 쓰기 좋은 tool들이 많은 걸 깨달았다. 예를 들어 do_schedul같은 것들... pintOS는 생각보다는 친절했다.