Pintos Project 1-2 Priority Scheduling 구현

배경지식

1. Round Robin(RR) Scheduling

프로세스와 네트워크 스케쥴러에서 이뤄지는 알고리즘 중 하나이다. 일반적으로 time slice가 각 프로세스에서 동일한 부분만큼 순환하는 순서로 배당되어 모 프로세스들을 우선순위 없이 다룬다는 의미이다. 수행하기 간단하고 쉬우며 starvation-free(공평하게 모두 나눠가짐)가 특징이다.

2. Priority Donation(Priority Inheritance)

unbounded inversion(끝없는 우선순위 도치)을 제거하기 위한 방법이다. 이 알고리즘은 우선순위가 가장 높은 프로세스 A가 있다고 가정한다면, A가 필요한 lock의 holder인 다른 프로세스의 우선순위를 A만큼 증가시키는 것이다. 그 결과 우선순위가 증가한 프로세스가 우선적으로 실행되고 hold한 lock을 release하면 프로세스 A가 실행될 수 있게 된다. 즉, A가 우선순위에 따라 가장 먼저 실행되기 위해서 필요한 것들(lock과 같은)을 확보하기 위해 다른 누군가에게 A 자신의 우선순위를 부여해 주는 것이다.

3. Synchronization

쓰레드(or 프로세스)간 자원분배는 조심히 다뤄야 한다. 시스템에서 다른 프로세스가 실행됨으로써 영향을 주거나 받을 수 있는 것을 cooperationg process라고 한다. 이 process는 직접적으로 주소(code,data 모두 해당)를 공유할수도, 파일이나 메세지를 통해서만 데이터를 공유할 수 있도록 허용될 수도 있다. 공유 데이터로 동시(concurrent) 접근은 data inconsistency를 초래할 수 있다. 주소 공간을 공유하는 cooperationg processes이 순차적으로 실행하도록 해야한다. 이를 통해 데이터의 synchronization을 유지해야 한다.

예를 들자면, 하나의 화장실 칸에 10명의 사람이 기다리고 있다고 가정한다. 누군가가 화장실에 들어가 사용중이라면 다른 사람이 접근해선 안된다! 보통은 노크를 하는 방법을 쓰긴 하지만, 사용중 이라는 빨간 표시등이 나타나기도 한다. 현재 화장실 칸이 사용중이고 다른 누군가가 접근하면 안된다는 걸 표시하는 것이다. 이 화장실을 우선순위 등에 맞게 순차적으로 사용할 수 있도록 scheduling하는 과정에서 현재 칸이 비어있는지, 사용 중인지를 모두가 알게 하는 것이 동기화 과정이다. 화장실을 쓰고 싶어서 방금 온 사람들도 이 정보를 알도록 해야한다.

생산자 프로세스는 소비자 프로세스에 의해 소비되는 정보를 생산한다. 예를 들어, 컴파일러는 assembler에 의해 소비되는 assembly code를 생산하고 assemble은 loader에 의해 소비되는 객체 모듈을 만든다. 생산자와 소비자는 메모리가 꽉차서 만드는걸 중단하거나 만들어 진게 없어서 소비하는 것을 중단하거나 하는 상황이 생기게 된다. 이를 해결하는 방법이 공유 메모리를 사용하는 것이다.

생산자와 소비지 프로세스들이 동시에 작동하도록 하여, 생산자가 채우고 소비자가 비우는 buffer를 설정한다. 이 buffer가 공유 메모리 지역에 있게 된다. 이 과정에서 생산자와 소비자간 동기화하여 아직 생산되지 않는 아이템을 소비하지 않도록 해주어야 한다.

4. Semaphore

공유된 자원의 데이터 혹은 Critical Section 등에 여러 Processes나 Threads가 접근하는 것을 막아준다. 즉, 동기화 대상이 다수이다. 리소스의 상태를 나타내는 간단한 카운터이고 비교적 긴 시간을 확보하는 리소스에 대해 이용한다. 유닉스 시스템에서 운영체제의 리소스를 경쟁적으로 사용하는 다중 프로세스의 동기화 등에 사용되며 세마포어를 사용하는 프로세스는 그 값을 확인하고, 자원을 사용하는 동안에는 그 값을 변경함으로써 다른 세마포어 사용자들이 기다리도록 해야한다.

5. Mutex

공유된 자원의 데이터 혹은 Critical Section 등에 단일 Process나 Thread가 접근하는 것을 막아준다. 즉, 동기화 대상이 하나이다. Mutual Exclusion(상호 배제)라고도 한다. Crticial section을 가진 쓰레드들의 작동 시간이 겹치지 않도록, 각각 단독으로 실행되게끔 해준다. locking과 unlocking을 사용하여 뮤텍스 개체를 두 쓰레드가 동시에 사용할 수 없다. 세마포어와 비교해보면 다음과 같다.

하지만 둘 다 Critical section으로 들어가기 전 wait(), 빠져 나올때 signal or release 처리를 직접 해주어야 한다는 단점이 있다.

6. Lock

Lock은 1의 초기 값을 가진 세마포어 같다. 록에서 “up”은 “release”라 불리고, “down”은 “acquire”로 불린다.

세마포어와 비교해서, 록은 limitation을 하나 더 가진다. 록을 acquire한 쓰레드만 release할 수 있다. 재귀가 불가능하여 현재 lock을 가진 쓰레드가 그 lock을 acquire하려고 하면 error가 된다.

7. Monitor

Monitor는 semaphore나 lock보다 높은 형태의 동기화이다. 모니터는 동기화되는 data와 monitor lock이라 부르는 lock, 하나 이상의 condition variables로 이루어져 있다. 데이터에 접근 전에, 쓰레드는 monitor lock을 얻어야 한다. 얻으면 “in the monitor”라고 한다. monitor에서, 자유롭게 examine, modify 할 수 있다. 작업이 끝나면 release한다.

8. Condition Variables

모니터에 있는 코드는 조건이 True가 되길 기다리게 된다. 코드가 True를 기다린다는 것은 lock을 release하고 condition variable을 기다린다는 의미이다. 이 조건 중 하나가 True가 되면, signal을 보내 waiter 하나를 깨우거나 broadcast로 모두 깨운다.

9. Race condition

다음과 같은 예시가 있다.

counter = 5

우리는 두 과정들이 동시에 COUNTER 변수를 조작하도록 하였기 때문에 부정확한 상황에 도달하였다.

다수의 프로세스들이 같은 데이터에 동시에 접근하여 조작하고 실행의 결과가 접근이 발생하는 특정 순서와 연관된 이러한 상황을

race condition 이라고 한다.

과제

목표

• 각 thread에게 우선순위를 부여하기

• 우선순위에 따라 scheduling하기

• 필요한 경우 priority donation하도록 구현하기

과정

구현할 함수 선언

• 수정 파일 : /include/threads/thread.h
• 개선 방향
  • 현재 수행중인 스레드 VS 가장 높은 우선순위의 스레드 간 우선순위 비교하여 스케쥴링하는 함수 1개
  • 인자로 주어진 스레드들의 우선순위를 비교하는 함수 1개 (총 2개)

정답코드

1
2
3
void test_max_priority(void);

bool cmp_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED);

thread_create() 함수 수정

• 수정 파일 : threads/thread.c

• 개선 방향

  • 생성된 스레드의 우선순위가 현재 실행중인 스레드의 우선순위보다 높다면 CPU 양보

정답코드

1
2
3
4
5
6
7
8
9
10
11
12
13
struct thread_create(const char *name, int priority, thread_func *function, void *aux){

    ...

    thread_unblokck(t);

    if (t->priority->thread_current()->priority)
        thread_yield();

    thread_yield();

    return tid;
}

thread_unblock() 함수 수정

• 수정 파일 : threads/thread.c
• 개선 방향
  • 쓰레드 unblock 될 때, 우선순위값으로 정렬하여 ready_list 삽입

정답 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void thread_unblock(struct thread *t)
{
    enum intr_level old_level;

    ASSERT(is_thread(t));

    old_level = intr_disalbe();
    ASSERT(t->status == THREAD_BLOCKED);

    list_insert_ordered(&ready_list, &t->elem, &cmp_priority, NULL);

    t->status = THREAD_READY;
    intr_set_level(old_level);
}

thread_yield() 함수 수정

• 수정 파일 : threads/thread.c
• 개선 방향
  • 현재 작동중인 쓰레드가 CPU 양보
  • 그 쓰레드는 ready_list에 우선순위에 맞게 정렬하여 삽입

정답 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
void thread_yield(void){
    struct thread *curr = thread_current();
    enum intr_level old_level;

    ASSERT(!intr_context());
    old_level = intr_disable();

    if(curr != idle_thread)
        list_insert_ordered(&ready_list, &curr->elem, cmp_priority,NULL);

    do_schedule(THREAD_READY);
    intr_set_level(old_level);
}

thread_set_priority() 함수 수정

• 수정 파일 : `threads/thread.c’
• 개선 방향
  • 우선순위에 변화가 발생하면, 우선순위에 맞게 preemption 발생

정답 코드

1
2
3
4
5
void thread_set_priority(int new_priority)
{
    thread_current()->priority = new_priority;
    test_max_priority();
}

test_max_priority() 함수 생성

• 수정 파일 : threads/thread.c

• 개선 방향

  • ready_list 비어있는 지 확

  • 현재 작동중인 쓰레드 VS ready_list에서 가장 높은 우선순위를 가진 쓰레드 간 비교하여 스케쥴링

정답 코드

1
2
3
4
5
6
7
8
9
10
11
void test_max_priority(void)
{
    if(list_empty(&ready_list))
        return:

    struct thread* max_priority = list_entry(list_front(&ready_list), struct thread, elem);

    if(max_priority->priority > thread_current()->priority){
        thread_yield();
    }
}

sema_down()함수 수정

• 수정 파일 : threads/synch.c
• 개선 방향
  • Semaphore를 얻고 wait-list 삽입시에 우선순위에 맞게 삽입되도록 한다.

정답 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void sema_down(struct sepaohre *sema)
{
    enum intr_level old_level;

    ASSERT (sema != NULL);
    ASSERT (!intr_context());

    old_level = intr_disable();
    while(sema->value == 0)
    {
        list_insert_ordered(&sema->waiters, &thread_current()->elem, thread_compare_priority, 0);
        thread_block();
    }
    sema->value--;
    intr_set_level(old_level);
}

sema_up() 함수 수정

• 수정 파일 : threads/synch.c
• 개선 방향
  • wait_list 비어있는 지 확인해야 한다.
  • 변경된 우선순위가 있을 수 있으니 우선순위에 맞게 정렬한다.
  • priority preemption 코드를 추가해야 한다.

정답 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void sema_up(struct semaphore *sema)
{
    enum intr_level old_level;

    ASSERT(sema != NULL);

    old_level = intr_disable();
    if(!list_empty(&sema->waiters))
    {
        list_sort(&sema->waiters, thread_compare_priority, 0);
        thread_unbloick(list_entry(list_pop_front(&sema->waiters),
                                  struct thread, elem));
    }
    sema->value++;
    thread_test_preemption();
    intr_set_level(old_level);
}

sema_compare_priority() 함수 구현

• 수정 파일 : threads/synch.c
• 개선 방향
  • 두 인자의 우선순위 비교
  • list_elem을 인자로 받는다.

정답 코드

1
2
3
4
5
6
7
8
9
10
bool sema_compare_priority(const struct list_elem *l, const struct list_elem *s, void *aux UNUSED)
{
    struct semaphore_elem *l_sema = list_entry(1, struct semaphore_elem, elem);
    struct semaphore_elem *s_sema = list_entry(1, struct semaphore_elem, elem);

    struct list *waiter_l_sema = &(l_sema->semaphore.waiters);
    struct list *waiter_s_sema = &(s_sema->semaphore.waiters);

    return list_entry(list_begin(waiter_l_sema), struct thread, elem)->priority > list_entry(list_begin(waiter_s_sema), struct thread, elem)->priority;
}

cond_wait() 함수 수정

• 수정 파일 : threads/synch.c
• 개선 방향
  • condition variable의 wait_list에 우선순위에 맞게 삽입

정답 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void cond_wait(struct condition *cond, struct lock *lock)
{
    struct semaphore_elem waiter;

    ASSERT(cond != NULL);
    ASSERT(lock != NULL);
    ASSERT(!intr_context());
    ASSERT(lock_held_by_current_thread(lock));

    sema_init(&waiter.semaphore, 0);
    list_insert_ordered(&cond->waioters, &waiter.elem, sema_compare_priority, 0);
    lock_release(lock);
    sema_down(&waiter.semaphore);
    lock_acquire(lock);
}

cond_signal() 함수 수정

• 수정 파일 : thread/synch.c
• 개선 방향
  • condition variable의 wait_list를 우선순위대로 재정렬

정답 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void cond_signal(struct condition *cond, struct lock *lock UNUSED)
{
    ASSERT(cond != NULL);
    ASSERT(lock != NULL);
    ASSERT(!intr_context());
    ASSERT(lock_held_by_current_thread(lock));

    if(!list_empty(&cond->waiters))
    {
        list_sort(&cond->waiters, sema_compare_priority, 0);
        sema_up(&list_entry(list_pop_front(&cond->waiters),
                           struct semaphore_elem, elem)-> semaphore);
    }
}

• Previous
  PintOS Project1-1 WIL
• Next
  Pintos 2주차 도입