[Pintos-KAIST] Project 1 : Priority Scheduling

유선·2024년 5월 1일
pintos정글 7주차
0

Pintos - KAIST

목록 보기
2/16
post-thumbnail

👩🏻‍💻 GITHUB 레포지토리
👩🏻‍💻 GITHUB Priority Scheduling 이슈

과제 설명

현재 핀토스의 스케줄러는 라운드 로빈으로 구현되어 있다. 이를 우선순위를 고려하여 스케줄링 하도록 수정한다.

  • 핀토스의 thread lifecycle

    CPU는 여러 Thread를 번갈아가며 수행한다. 모든 Thread는 Ready List에 들어가 자신의 순서가 오길 기다리는데, 기존 pintOS는 단순히 새로 들어온 Thread를 줄의 맨 뒤에 세우고, 먼저 온 순서대로 처리하는 FCFS(First Come First Served) 방식으로 줄을 세운다.

💡 우선순위가 높은 스레드가 먼저 CPU를 점유할 수 있도록 Priority Scheduling을 구현한다.

구현 목표

1️⃣ Ready list에 새로 추가된 thread의 우선순위가 현재 CPU를 점유중인 thread의 우선순위보다 높으면, 기존 thread를 밀어내고 CPU를 점유하도록 한다.
2️⃣ 여러 thread가 lock, semaphore 를 얻기 위해 기다릴 경우 우선순위가 가장 높은 thread가 CPU를 점유한다.

추가 함수

  • void test_max_priority(void): 현재 수행중인 스레드와 가장 높은 우선순위의 스레드의 우선순위를 비교하여 스케줄링
  • bool cmp_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED):인자로 주어진 스레드들의 우선순위를 비교

수정 함수

  • tid_t thread_create (const char *name, int priority, thread_func *function, void *aux): 새로운 스레드를 생성 (스레드를 생성할 때, 우선순위도 지정하도록 바꾼다.)
  • void thread_unblock (struct thread *t): block된 스레드를 unblock
  • void thread_yield (void): 현재 수행중인 스레드가 사용중인 CPU를 양보
  • void thread_set_priority (int new_priority): 현재 수행중인 스레드의 우선순위를 변경

사전 환경 설정

동작 순서 중 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 alarm-priority

구현

구현할 함수 선언

  • include/threads/thread.h
.
.
.
/** project1-Priority Scheduling */
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

    ▶️ Thread의 unblock 후, 현재 실행중인 thread와 우선순위를 비교하여, 새로 생성된
    thread의 우선순위가 높다면 thread_yield()를 통해 CPU를 양보

tid_t
thread_create (const char *name, int priority,
		thread_func *function, void *aux) {
	struct thread *t;
	tid_t tid;

	ASSERT (function != NULL);

	/* Allocate thread. */
	t = palloc_get_page (PAL_ZERO);
	if (t == NULL)
		return TID_ERROR;

	/* Initialize thread. */
	init_thread (t, name, priority);
	tid = t->tid = allocate_tid ();

	/* Call the kernel_thread if it scheduled.
	 * Note) rdi is 1st argument, and rsi is 2nd argument. */
	t->tf.rip = (uintptr_t) kernel_thread;
	t->tf.R.rdi = (uint64_t) function;
	t->tf.R.rsi = (uint64_t) aux;
	t->tf.ds = SEL_KDSEG;
	t->tf.es = SEL_KDSEG;
	t->tf.ss = SEL_KDSEG;
	t->tf.cs = SEL_KCSEG;
	t->tf.eflags = FLAG_IF;

	/* Add to run queue. */
	thread_unblock (t);

	/** project1-Priority Scheduling */
	if(t->priority > thread_current()->priority)
		thread_yield();

	return tid;
}

thread_unblock() 함수 수정

  • threads/thread.c

    ▶️ Thread가 unblock 될때 우선순위 순으로 정렬 되어 ready_list에 삽입되도록 수정

void
thread_unblock (struct thread *t) {
	enum intr_level old_level;

	ASSERT (is_thread (t));

	old_level = intr_disable ();
	ASSERT (t->status == THREAD_BLOCKED);
	/** project1-Priority Scheduling */
	list_insert_ordered(&ready_list, &t->elem, cmp_priority, NULL);
	//list_push_back (&ready_list, &t->elem);
	t->status = THREAD_READY;
	intr_set_level (old_level);
}

thread_yield() 함수 수정

  • threads/thread.c

    ▶️ 현재 thread가 CPU를 양보하여 ready_list에 삽입 될 때 우선순위 순서로 정렬되어 삽입 되도록 수정

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_push_back (&ready_list, &curr->elem);
		/** project1-Priority Scheduling */
		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

    ▶️ 현재 쓰레드의 우선 순위와 ready_list에서 가장 높은 우선 순위를 비교하여 스케쥴링 하는 함수 호출

void
thread_set_priority (int new_priority) {
	thread_current ()->priority = new_priority;
	/** project1-Priority Scheduling */
	test_max_priority();
}

test_max_priority() 함수 추가

  • threads/thread.c

    ▶️ ready_list에서 우선 순위가 가장 높은 쓰레드와 현재 쓰레드의 우선 순위를
    비교.
    → 현재 쓰레드의 우선수위가 더 작다면 thread_yield()

/** project1-Priority Scheduling */
void 
test_max_priority (void) 
{
    if (list_empty(&ready_list))
        return;

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

    if (thread_get_priority() < th->priority)
        thread_yield();
}

cmp_priority() 함수 추가

  • threads/thread.c

    ▶️ 첫 번째 인자의 우선순위가 높으면 1을 반환, 두 번째 인자의 우선순위가 높으면 0을
    반환
    ▶️ list_insert_ordered() 함수에서 사용

/** project1-Priority Scheduling */
bool 
cmp_priority (const struct list_elem *a, const struct list_elem *b, void *aux UNUSED) 
{
    struct thread*thread_a = list_entry(a, struct thread, elem);
    struct thread*thread_b = list_entry(b, struct thread, elem);

	if (thread_a == NULL || thread_b == NULL)
		return false;

    return thread_a->priority > thread_b->priority;
}

테스트 결과

통과되어야하는 테스트

  • alarm-priority
  • priority-change
  • priority-fifo
  • priority-preempt

참고

[Pintos-KAIST] Project 1 :: Priority Donation
[운영체제] pintOS 프로젝트 - Priority Scheduling

profile
유선
Sunny Day!
이전 포스트

[Pintos-KAIST] Project 1 : Alarm Clock

다음 포스트

[Pintos-KAIST] Project 1 : Priority Scheduling and Synchronization

0개의 댓글