[PintOS-KAIST]Project1:preview

본격적으로 project1을 하기 위한 전반적인 코드 분석 및 flow 이해를 하기위한 포스트이다.

pintos의 경우 굉장히 많은양의 코드(대략 기본 코드가 2만줄이라고한다,,,)와 많은 파일들이 있기에 전반적이 flow 이해와 더불어 구현해야할 부분에 대한 코드분석이 우선이라고 생각했다.

실제로 2일동안은 코드 한줄 작성하지 않고 코드분석과 flow이해를 위한 기본적인 개념공부와 더불어 gdb를 이용해 test를 돌려보면서 한줄 한줄 뜯어보면서 확인했다.(alarm-multiple)

확인하는 방법은 main()에서 thread_start()에 breakpoint를 찍고 한줄한줄 step over,into,out을 반복하며 확인했다.(실제로 into를 깊게 들어가면 어셈블리어까지 있다.... 이론적으로 공부한걸 직접 코드로 보니 어지럽다,,,)

gdb가 생소하고 test run하는법이 어려울수도 있기에(내가 기억하려고) 하는 과정을 적어둔다.

launch.json 파일

    "version": "0.2.0",
    "configurations": [
        {
            "name": "[P1] Debug a Test",
            "type": "cppdbg",
            "request": "launch",
            "program": "${workspaceFolder}/threads/build/kernel.o",
            "miDebuggerServerAddress": "localhost:1234",
            "stopAtEntry": false,
            "cwd": "${workspaceFolder}",
            "environment": [],
            "externalConsole": false,
            "MIMode": "gdb",
            "setupCommands": [
                {
                    "description": "Enable pretty-printing for gdb",
                    "text": "-enable-pretty-printing",
                    "ignoreFailures": true
                }
            ],
            "symbolLoadInfo": {
                "loadAll": true,
                "exceptionList": ""
            }
        },
    ]

활성화 실행파일 실행

thread 폴더 이동후 make

build 폴더 이동후 pintos 디버깅 실행

이후에 디버깅 실행버튼을 누르면 

 

종단점을 찍은 thread_start()부터 시작하게 된다.

 

 

자 여기까지 직접 코드를 뜯어볼수 있는 방법을 설명했다. flow에 따라 간략하게 설명하겠다.

먼저 thread_start()다.

/* Starts preemptive thread scheduling by enabling interrupts.
   Also creates the idle thread. */
void thread_start(void) {
    /* Create the idle thread. */
    struct semaphore idle_started;
    sema_init(&idle_started, 0);
    // idle_thread 실행(kenerl의 main thread)
    thread_create("idle", PRI_MIN, idle, &idle_started);

    /* Start preemptive thread scheduling. */
    intr_enable();

    /* Wait for the idle thread to initialize idle_thread. */
    sema_down(&idle_started);
}

 

 

과제 설명

Priority Inverstion Problem은 thread가 두 개 이상의 lock보유가능할 때, 높은 priority의 thread가 낮은 priority의 thread보다 늦게 실행될 수 있는 문제점을 말한다.

✔️ 자세한 Priority Inversion Problem 설명 확인하기

• 유튜브 영상 참고하기
  🖥️ CS450: Priority Donation 1 (Pintos Project)
  🖥️ CS450: Priority Donation 2 (Pintos Project)
  🖥️ CS450: Priority Donation 3 (Pintos Project)

Priority Inverstion

간단하게 설명하자면,

H (high), M (medium), L (low) 라는 세 개의 스레드가 있고 각각의 우선순위는 H > M > L 이다. H 가 L 을 기다려야 하는 상황(예를 들어, H 가 lock 을 요청했는데 이 lock 을 L 이 점유하고 있는 경우)이 생긴다면 H 가 L 에게 CPU 점유를 넘겨주면 M 이 L 보다 우선순위가 높으므로 점유권을 선점하여 실행되어서 스레드가 마무리 되는 순서가 M->L->H 가 된다. 따라서 M 이 더 높은 우선순위를 가진 H 보다 우선하여 실행되는 문제가 발생한다.

구현 목표

priority donation

이를 해결하기 위해 priority donation을 구현하여야 한다.

priority donation 이란 위의 상황에서 H 가 자신이 가진 priority 를 L 에게 일시적으로 양도하여서 H 자신의 실행을 위해 L 이 자신과 동일한 우선순위를 가져서 우선적으로 실행될 수 있도록 만드는 방법이다.

핀토스 documents 에서는 priority donation 이 일어난 수 있는 모든 상황을 고려해야 한다고 하면서 Multiple donation, Nested donation 두 가지를 언급한다.

1. Multiple donation

• lock을 여러 개 점유한 스레드는 lock을 요청한 스레드의 priority 중 가장 높은 priority로 갱신한다.
• lock을 반환할 경우에는, 반환한 lock을 획득한 스레드를 제외한 lock을 요청한 스레드들의 priority 중에서 가장 높은 priority로 갱신한다.

2. Nested donation

• Donation은 재귀적으로 이어진다.
  • T1이 점유한 lockA를 T2가 요청하면 (T2가 더 높을 경우) T2의 priority로 갱신한다.
  • 위 상황에서, T2가 점유한 lockB를 T3이 요청하면 (T3이 더 높을 경우) T1과 T2를 T3의 priority로 갱신한다.

수정 함수 및 자료구조

• void lock_acquire (struct lock *lock) : lock을 점유하고 있는 스레드와 요청 하는 스레드의 우선순위를 비교하여 priority donation을 수행하도록 수정
• void lock_release (struct lock *lock) : donation list 에서 스레드를 제거하고 우선순위를 다시 계산하도록 remove_with_lock(), refresh_prioriy() 함수를 호출
• void thread_set_priority (int new_priority) : 스레드 우선순위 변경시 donation의 발생을 확인 하고 우선순위 변경을 위해 donation_priority()함수 추가
• struct thread

추가 함수

• void donate_priority(void) : priority donation을 수행
• void remove_with_lock(struct lock *lock) : donation list에서 스레드 엔트리를 제거
• void refresh_priority(void) : 우선순위를 다시 계산

사전 환경 설정

동작 순서 중 Source ./activate 안치게 하는법!!

1. 루트 디렉토리로 이동
2. code .bashrc 입력
   
3. 파일 제일 밑에 본인의 source activate 경로 추가

테스트 방법

1. /pintos 경로에서 source ./activate (사전 환경 설정을 했다면 안해줘도 된다!)
2. threads 폴더 들어가서 make clean make check를 수행하면 Test Case들에 대해서 채점을 수행한다.
3. Test Case 한가지만 돌리고 싶다면, pintos/(프로젝트명)/build에 들어가서 아래 명령어를 수행하면 된다.
   pintos -T (Timout이 걸리는 시간) -- -q -run (Test case 이름)
   ex) `pintos -T 30 -- -q run donate-one

구현

struct thread에 prioriry donation관련 항목 추가

• include/threads/thread.h
  • donation 이후 우선순위를 초기화하기 위해 초기 우선순위 값을 저장할 필드
  • 해당 쓰레드가 대기하고 있는 lock 자료구조의 주소를 저장할 필드
  • multiple donation을 고려하기 위한 리스트 추가
    • 해당 리스트를 위한 elem도 추가

.
.
.
	/** project1-Priority Inversion Problem */
	int original_priority;
    struct lock *wait_lock;
    struct list donations;
    struct list_elem donation_elem;
.
.
.

init_thread() 함수 수정

• threads/thread.cPriority donation 관련 자료구조 초기화 코드 삽입

static void
init_thread (struct thread *t, const char *name, int priority) {
	ASSERT (t != NULL);
	ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
	ASSERT (name != NULL);

	memset (t, 0, sizeof *t);
	t->status = THREAD_BLOCKED;
	strlcpy (t->name, name, sizeof t->name);
	t->tf.rsp = (uint64_t) t + PGSIZE - sizeof (void *);

	/** project1-Priority Inversion Problem */
    t->priority = t->original_priority = priority;
    list_init(&t->donations);
    t->wait_lock = NULL;

	t->magic = THREAD_MAGIC;
}

lock_acquire() 함수 수정

• threads/synch.c
  • 해당 lock의 holder가 존재하여 wait을 하게 되면 아래 동작을 수행.
    • wait을 하게 될 lock 자료구조 포인터 저장
      • 쓰레드 디스크립터에 추가한 필드
    • lock의 현재 holder의 대기자 list에 추가
    • priority donation을 수행하는 코드 추가
      • 구현하게 될 함수인 donate_priority()
    • lock 획득 후 lock의 holder 갱신

void
lock_acquire (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (!lock_held_by_current_thread (lock));

   /** project1-Priority Inversion Problem */
   struct thread *t = thread_current();
    if (lock->holder != NULL) {
        t->wait_lock = lock;
        list_push_back(&lock->holder->donations, &t->donation_elem);
        donate_priority();
    }

	sema_down (&lock->semaphore);

   /** project1-Priority Inversion Problem */
   t->wait_lock = NULL;
   lock->holder = t;
}

구현할 함수 선언

• include/threads/thread.h

.
.
.
/** project1-Priority Inversion Problem */
void donate_priority(void);
void remove_with_lock(struct lock *lock);
void refresh_priority(void);
.
.
.

donate_priority() 함수 추가

• threads/thread.c
  • void donate_priority(void)
  • priority donation을 수행하는 함수
  • Nested donation을 고려하여 구현
    • 현재 쓰레드가 기다리고 있는 lock과 연결된 모든 쓰레드들을 순회하며 현
      재 쓰레드의 우선순위를 lock을 보유하고 있는 쓰레드에게 기부
    • nested depth는 8로 제한

/** project1-Priority Inversion Problem */
void 
donate_priority() 
{
    struct thread *t = thread_current();
    int priority = t->priority;

    for (int depth = 0; depth < 8; depth++) 
	{
        if (t->wait_lock == NULL)
            break;

        t = t->wait_lock->holder;
        t->priority = priority;
    }
}

lock_release() 함수 수정

• threads/synch.c
  • lock을 해제한 후, 현재 쓰레드의 대기 리스트 갱신 (remove_with_lock() 사용)
  • priority를 donation 받았을 수 있으므로 원래의 priorit로 초기화 (refresh_priority() 사용)

void
lock_release (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (lock_held_by_current_thread (lock));

	lock->holder = NULL;

   /** project1-Priority Inversion Problem */
   remove_with_lock(lock);
   refresh_priority();

	sema_up (&lock->semaphore);
}

remove_with_lock() 함수 추가

• threads/thread.c
  • lock을 해지 했을 때, waiters 리스트에서 해당 엔트리를 삭제 하기 위한 함수를 구현
  • 현재 쓰레드의 waiters 리스트를 확인하여 해지할 lock을 보유하고 있는 엔트리를 삭제

/** project1-Priority Inversion Problem */
void remove_with_lock(struct lock *lock) 
{
    struct thread *t = thread_current();
    struct list_elem *curr = list_begin(&t->donations);
    struct thread *curr_thread = NULL;

    while (curr != list_end(&t->donations)) 
	{
        curr_thread = list_entry(curr, struct thread, donation_elem);

        if (curr_thread->wait_lock == lock)
            list_remove(&curr_thread->donation_elem);

        curr = list_next(curr);
    }
}

refresh_priority() 함수 추가

• threads/thread.c
  • 스레드의 우선순위가 변경 되었을 때, donation을 고려하여 우선순위를 다시 결정하는 함수
  • 현재 쓰레드의 우선순위를 기부 받기 전의 우선순위로 변경
  • 현재 쓰레드의 waiters 리스트에서 가장 높은 우선순위를 현재 쓰레드의 우선순위와 비교 후 우선순위 설정

/** project1-Priority Inversion Problem */
void refresh_priority(void) 
{
    struct thread *t = thread_current();
    t->priority = t->original_priority;

    if (list_empty(&t->donations))
        return;

    list_sort(&t->donations, cmp_priority, NULL);

    struct list_elem *max_elem = list_front(&t->donations);
    struct thread *max_thread = list_entry(max_elem, struct thread, donation_elem);

    if (t->priority < max_thread->priority)
        t->priority = max_thread->priority;
}

thread_set_priority() 함수 수정

• threads/thread.c

• refresh_priority() 함수를 사용하여 우선순위의 변경으로 인한 donation 관련
  정보를 갱신
• donation_priority(), test_max_priority() 함수를 적절히 사용하여 priority
  donation을 수행하고 스케줄링

void
thread_set_priority (int new_priority) {
	thread_current ()->priority = new_priority;

	/** project1-Priority Inversion Problem */
    thread_current()->original_priority = new_priority;

	/** project1-Priority Inversion Problem */
    refresh_priority();

	/** project1-Priority Scheduling */
	test_max_priority();
}

테스트 결과

통과되어야하는 테스트

• donate-one
• donate-multiple
• donate-multiple2
• donate-nest
• donate-sema
• donate-lower