jungle PintOS Thread alarm clock 운영체제

PintOS Project1-1 WIL

정글일지 28

PintOS Project1-1 Alarm Clock 구현

개요

  • 기간 : 2023년 4월 20일 ~ 27일
  • 주제 : Threads
  • 과제
    • Alarm Clock
    • Priority Scheduling
    • Advanced Scheduler

배경지식

1. interrupt

  • 기본 개념

    • CPU의 명령 수행속도에 비해 I.O(입출력) 연산의 속도는 훨씬 느리다.
    • I.O 연산을 위해 CPU가 쉬면서 기다리는 것은 낭비다.
    • I.O 연산 중에 CPU는 다른 일을 하고 있는다.
    • I.O 연산 결과가 나오면 CPU에게 알린다. => “Interrupt”

  • 정의

    • CPU가 프로그램을 실행하고 있을 때, 입출력 하드웨어 등의 장치나 예외상황이 발생하여 처리가 필요한 경우에 마이크로프로세서에서 알려 처리할 수 있도록 하는 것. 하드웨어 interrupt와 소프트웨어 interrutp로 나뉜다.
    • trap이라고도 일컬어지며 프로세서에게 최근에 실행된 코드의 중단을 요청해서 event가 때맞은 방식으로 처리될 수 있도록 하는 것.
    • 요청이 받아들여지면, 프로세서는 최근 활동을 중단시키고 state를 저장한 후 event를 처리하기 위해 interrupt handler(ISR, interrupt service routin)라고 불리는 함수를 실행한다.

  • 종류

    • 하드웨어 인터럽트
      • 하드웨어가 발생시킴
      • CPU가 아닌 하드웨어 장치가 CPU에게 알려주거나, 서비스 요청할 경우 발생
    • 소프트웨어 인터럽트
      • 소프트웨어가 발생시킴
      • 사용자 프로그램(소프트웨어)가 스스로 인터럽트 라인을 세팅
      • 종류 : exception(예외), system call(syscall)
    • 두 종류 모두 CPU내의 인터럽트 라인을 세팅하여 인터럽트 발생시킴
    • CPU : 매 명령 수행 전 인터럽트 라인 검사

  • 과정

상황 : 프로세스 A 실행 중 디스크에서 어떤 데이터를 읽어오라는 명령을 받음

  1. 프로세스 A는 system call로 인터럽트 발생시킨다.
  2. 명령 받은 CPU는 현재 수행중인 기계어 코드 완료
  3. 수행중이었던 현재 상태를 해당 process의 PCB(Process Control Block)에 저장
  4. PC(Program Counter, IP)에 다음으로 실행할 명령의 주소 저장
  5. 인터럽트 벡터를 읽고 ISR 주소값을 얻어 ISR(Interrupt Service Rountine)로 점프하여 루틴 실행
  6. 해당 코드 실행
  7. 해당 작업 종료시, 레지스터 복원
  8. ISR의 끝에 있는 IRET 명령어에 의해 인터럽트 해제
  9. IRET 명령어 실행 후, 대피시킨 PC값 복원하여 복귀

  • 특권 명령

    • 명령어의 종류
      • 일반 명령 : 모든 프로그램이 수행 가능
      • 특권 명령(previleged) : 운영체제(Operation system)만 수행 가능
    • Kernel Mode VS User Mode
      • Kernel Mode : 운영체제가 CPU의 제어권을 갖고 명령을 수행. 일반, 특권 명령 모두 가능
      • User Mode : 일반 사용자 프로그램이 CPU의 제어권을 가짐. 일반 명령만 가능

  • 관련 용어

    • Interrupt handler(Interrupt service routine)

      실제 인터럽트를 처리하기 위한 루틴. 운영체제 코드 영역내에 인터럽트별 처리할 내용이 프로그래밍 되어 있음.

    • Interrupt vector

      인터럽트 발생 시 처리해야 할 interrupt handler의 address를 인터럽트 별로 보관하는 테이블

    • PCB(Process control Block)

      커널의 데이터 영역에 존재. 각 프로세스는 고유의 PCB 가짐. 인터럽트 발생 시 수행중의 조건들 저장

2. Processor

  • Processor 혹은 processing unit은 보통 메모리나 다른 data stream같은 외부의 data source에서 operation을 수행하는 전기적 구성요소이다.
  • 시스템의 주요 processor인 CPU(Central Processing Unit)을 지칭하는데 사용되지만 CPU는 processor의 한 예시이다.
  • GPU(Graphic Processing Unit), DSP(Digital Signal Processor), Network Processor 등도 포포함되는 개념이다.
  • microprossor은 processor의 종류 중 하나이며, processor이 더 넓은 개념이다.
  • CPU가 하드웨어 용어이듯 processor도 하드웨어 용어이다.

3. Thread

  • 프로그래밍되어 scheduler가 독립적으로 관리할 수 있는 instruction의 가장 작은 단위이다. 쓰레드가 프로세스의 구성요소인 경우가 꽤 많다.
  • excutable code, 동적으로 할당된 변수들의 값과 non-thread-local 변수(전역 변수)들을 언제든 공유한다.
  • 다양한 업무를 동시에 수행할 필요가 있는 웹 서버, 멀티미디어 어플리케잇견, 운영 체제 같은 어플리케이션에서 사용
  • 각 쓰레드는 프로그램의 다른 부분을 동시에(concurrently) 수행할 수 있어 더 효율적이고 빠르게 실행하게 해준다.
  • 프로그램의 responsiveness(민감성)을 향상시키는데 사용될 수 있음.
    • GUI(Graphic User Interface) 어플리케이션의 경우, 분리된 쓰레드가 파일 I/O나 데이터 처리같은 배경 업무(background task)를 수행하는 동안 main 쓰레드가 유저 입력과 display를 다루는데 사용될 수 있음.
    • 프로그램이 background에서 resource-intensive(자원집약적인) 업무를 수행하는 동안 유저 input에 대한 반응성을 유지시켜줌.
  • TCB(Thread Control Block)
    • Thread를 다루는데 필요한 정보가 있는 운영체제 커널 안의 데이터 구조.
    • 다음과 같은 정보가 들어있다.
      • Thread Identifier : 모든 새 쓰레드가 가지는 고유 id(tid)
      • Stack pointer : 프로세스 내 쓰레드의 stack을 가리키는 포인터
      • Program counter : 쓰레드의 최근 프로그램 instruction을 가리키는 포인터
      • Thread’s register value : 쓰레드의 레지스터 값
      • Pointer to the PCB of the process that the thread lives on : 쓰레드가 위치한 프로세스의 PCB(Process Control Block)을 가리키는 포인터
      • State of the thread : 쓰레드의 상태(running, readyt, waiting, start, done, …)

4. Process VS Thread

  • Process 내 여러 개의 Threads 존재 가능
  • Process는 자신만의 오픈 파일, 네트워크 소켓, 스택 등을 가진다.
  • Process는 다른 process의 메모리 공간이나 자원 접근 못함.
  • Thread는 프로세스에 속하는 가상 주소 공간을 thread와 공유
  • Thread는 자신만의 스택이 있지만, 코드, 데이터 세그먼트는 공유한다.

5. Schedule

  • 데이터베이스 안 transection set를 바탕으로 한 수행 리스트(a list of actrion).
  • 우선순위 등의 다양한 기준에 따라 쓰레드와 프로세스의 실행 순서를 조정하는 것.

  • scheduler가 수행한다.

  • Round Robin(RR) scheduling
    • 프로세스와 네트워크 스케쥴러에서 이뤄지는 알고리즘 중 하나.
    • time slice가 각 프로세스에 동일한 부분만큼 순환하는 순서로 배당되어 모든 프로세스들을 우선순위 없이 다룬다.
    • starvation-free : 모두 공평하기 때문

과제

목표

현재 Ready_list에서 사용되는 1 방식을 개선하기

sleep/wakeup 함수를 사용하여 시간 단위인 tick에 맞게 프로세스/쓰레드 관리

과정

struct thread 요소 추가하기

  • 수정 파일 : include/threads/thread.h

  • 개선 방향

    • 쓰레드가 깨어날 시간을 나타내는 변수 추가

    정답 코드

1
2
3
4
5
6
7
8
9
10
11
12
13

struct thread
{
    tid_t tid;
    enum thread_status status;

    ...

    int64_t wake_up_tick; // 추가한 변수

    ...

    unsigned magic;
};

전역변수 추가, 함수 선언

  • 수정 파일 : threads/thread.c

  • 개선 방향

    • 잠든 쓰레드들을 관리할 sleep queue 자료구조 추가
    • sleep_list에서 대기중인 쓰레드들의 wakeup_tick 값 중 최솟값 저장하는 전역 변수 추가(min_ticks)
    • 실행 중인 쓰레드를 재우는 함수 : thread_sleep()
    • sleep_list에서 꺠워야 할 쓰레드를 깨우는 함수 : void thread_wakeup()
    • 가장 작은 tick 값을 가진 쓰레드 저장하는 함수 : update_next_to_wake()
    • get_next_to_wakeup() 정답 코드
1
2
3
4
5
6
7
8
9
10
11
12
13

#define USERPROG
#include "threads/thread.h"

...

static struct list sleep_list;
static int64_t min_ticks;
void thread_sleep(int64_t ticks);
void thread_wakeup(int64_t ticks);
void update_next_to_wake(int64_t local_ticks);
int64_t get_next_to_wakeup(void);

추가한 요소 초기화

  • 수정 파일 : threads/thread.c

  • 개선 방향

    • sleep_list 초기화
    • 전역변수 min_ticks 초기화 정답 코드
1
2
3
4
5
6
7
8

void thread_init(void)
{
    ...

    list_init(&sleep_list);
    min_ticks = INT64_MAX; /* 이후 비교를 통해 낮은 값으로 update할 것이므로 현재는 최댓값으로 초기화한다. */

}

수면여부 결정하는 함수 수정

  • 수정 파일 : devices/timer.c

  • 개선 방향

    • busy waiting 유발 코드 삭제
    • 일어나야 할 시간과 비교하여 불만족 시 재우는 함수 호출

    정답 코드

    1
2
3
4
5
6
7
8
9

    void timer_sleep(int64_t local_ticks) 		/* local_ticks : 자고싶은 시간 */
{
    int64_t start = timer_ticks();			/* 현재 시간 설정 */
    ASSERT(intr_get_level() == INTR_ON); 	/* 인터럽트 방지 */
    if (timer_elapsed(start) < local_ticks) /* 아직 일어날 시간이 안되었다면? */
    {
        thread_sleep(start + local_ticks);	/* 현재 시간에서 local_ticks 만큼 지난 후 깨우도록 한다. */
    }
}

쓰레드 재우는 함수 구현

  • 수정 파일 : threads/thread.c
  • 개선 방향
    • 현재 쓰레드가 idle thread가 아닌 경우
      • 깨울 ticks 저장
      • sleep_list의 min_tick 업데이트
      • sleep_list 삽입
      • 쓰레드의 상태 변경
      • 정답 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void thread_sleep(int64_t local_ticks) /* local_ticks : 깨울 시간 */
{
    struct thread *curr = thread_current();
    enum intr_level old_level;

    ASSERT(!intr_context());
    ASSERT(curr != idle_thread);

    old_level = intr_disable(); /* 인터럽트 방지 */

    curr->wake_up_tick = local_ticks;
    update_next_to_wake(local_ticks);
    list_push_back(&sleep_list, &curr->elem);
    thread_block();

    intr_set_level(old_level); /* 인터럽트 재개 */
}

깨울 쓰레드 확인하는 함수 구현

  • 수정 파일 : devices/timer.c

  • 개선 방향

    • 매 tick마다 깨울 쓰레드 확인
    • 있으면 깨우는 함수 호출

  • 정답 코드

    1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

	/*-------------------------[project 1]-------------------------*/
	/* 깨울 스레드가 있으면 깨우기 */
	if (get_next_to_wakeup() <= ticks) /* get_next_to_wakeup(): 가장 작은 wakeup_ticks를 가진 스레드를 반환 */
	{
		thread_wakeup(ticks);
	}
	/*-------------------------[project 1]-------------------------*/
}

깨우는 함수 구현

  • 수정 파일 : threads/thread.c

  • 개선 방향

    • sleep list 순회하며 현재 tick이 쓰레드의 깨어날 tick보다 크거나 같으면 제거하고 unblock
    • 작으면 update_next_tick_to_awake() 호출

  • 정답 코드

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

    void thread_wakeup(int64_t ticks) /* ticks: global ticks */
{
	struct list_elem *curr = list_begin(&sleep_list);
	/* ⚠️ list_front 사용 시 sleep_list가 비어 있을 경우, ASSERT 발생 => list_begin 사용 */
	while (curr != list_end(&sleep_list)) /* sleep_list 끝까지 탐색 */
	{
		struct thread *t = list_entry(curr, struct thread, elem);
		int64_t tmp_ticks = t->wake_up_tick;
		if (tmp_ticks <= ticks) /* 현재 탐색 중인 스레드가 깰 시간이 되었을 때 */
		{
			curr = list_remove(&t->elem); /* sleep_list에서 제거 */
			thread_unblock(t);
			/*
			⚠️ thread_unblock을 list_remove보다 먼저 사용 시 ready_list로 이동 => list_remove 시 ready_list에서 제거
				* 원래 의도: sleep_list에서 제거
			 */
		}
		else /* 깨울 스레드가 아니면 */
		{
			curr = list_next(curr);
			update_next_to_wake(t->wake_up_tick);
		}
	}
}

쓰레드의 깨워야할 tick과 현재 최소 tick을 비교하는 함수

  • 수정 파일 : threads/thread.c

  • 개선 방향

    • 두 값을 비교하여 최솟값을 업데이트

  • 정답 코드

    1
2
3
4

    void update_next_to_wake(int64_t local_ticks)
{
	min_ticks = (local_ticks < min_ticks) ? local_ticks : min_ticks;
}

쓰레드를 깨워야할 다음 tick을 반환하는 함수

  • 수정 파일 : threads/thread.c
  • 개선 방향
    • 최소 tick 반환해준다.
  • 정답 코드
1
2
3
4

int64_t get_next_to_wakeup(void)
{
	return min_ticks;
}

소감

지금까지 배운 걸 다 이해도 못한듯 한데 악명(?)높은 pintos라니 여러모로 겁이 많이 났다. 실제로 gitbook도 읽고 카이스트, 한양대 ppt나 블로그 자료, 유튜브 등을 보면서 하나하나 알아간다기 보다는 도대체 내가 뭘 모르고 있는지를 공부하는 느낌이 강하게 들었다… 물론 나중에는 그것조차 힘들게 되긴 한데.. 혹시 이걸 보시는 분에게 조언을 드리자면

  • 지금 당장 무엇부터 해야할지 보다는 지금 시키는게 뭔지, 뭐가 어떻게 돌아가고 있고 그걸 어떻게 바꾸라는 건지를 파악하는 것을 최우선으로 하라고 권하고 싶다. Alarm Clock은 간단히 요약하면 Busy-wating 상태에서 tick을 기준으로 block하여 sleep-list에 보내거나, unblock하여 꺼내오는 것을 구현했다. 매 tick마다 모든 쓰레드를 검사할 필요 없이 sleep-list에서 깨울 tick이 가장 작은 애만 알고 있으면 된다. 예를 들어, 군대 내무반에서 3시에 일어날 애가 가장 빨리 일어날 애라면 그 뒤는 몰라도 된다. 3시까지 냅두다가 3시에 깨우고, 그 이후 일어날 애를 다시 조사하면 되니까.
  • 위가 파악 되면 함수 흐름을 파악하는게 개인적으로 좋았다. thread_init 하면 어떤 일이 일어나고, 내부에서 누가 호출되고, thread_create , 이후 끝까지 과정을 팀이 같이 파악해보면 좋다. 말로만 하지 말고 칠판에 그려가면서 하길 강력하게 권고함.
  • 페어 코딩의 장점 : 하루 종일 팀원들과 함께 고민하면 배우는게 정말 많다.
  • 페어 코딩의 단점 : 하루종일 함께 하면 안 싸울 사람은 없다.
  • “디버깅만 하면 된다!” 가 아니라 그게 시작이다.
  • 혹시 자료를 찾았다면 우선 그걸 fork해서 MAKE CHECK 하는 것을 추천한다. 생각보다 안되는 경우가 많다.

참고자료

  1. 한양대 Pintos PPT
  2. 카이스트 Pintos PPT
  3. https://www.youtube.com/@nesoacademy
  4. https://woonys.tistory.com/

  1. 현재 시간을 체크하면서 충분한 시간이 지나면 thread_yield()함수를 호출을 하는 루프를 도는 것. 매 tick마다 interrupt가 발생하기에 쓰레드들이 매 단위시간(틱)마다 현재시간을 확인하며 대기하기 때문에 자원 낭비가 심하다. ↩

CATALOG
    log