[PintOS 1주차] Day 7

동기화 프리미티브 변경

락, 세마포어, 조건 변수

대기 중인 스레드를 그 스레드의 우선순위에 따라 깨운다.

 

🔹 우선순위

• 스케줄러는 언제나 낮은 우선순위보다 높은 우선순위의 프로세스를 선택한다.
• 각 우선순위 레벨을 나타내는 다중의 레디 큐를 가진다.
• 낮은 우선순위는 기아 문제를 겪을 수 있기 때문에 프로세스가 그것의 오래된 정도나 실행된 기록에 따라 우선순위를 변경하게 할 수도 있다.

🔹 우선순위 스케줄링 (비선점형)

• 프로세스들은 외부적으로 할당된 우선순위(태스크의 중요도)에 기반해 CPU를 할당받는다.
• 낮은 우선순위의 프로세스는 기아 문제를 겪을 수 있다.
• 우선순위가 대기 시간 고려 등으로 내부적으로 우선순위가 재계산되면 해결할 수 있다.

비선점 우선순위 스케줄링 예시

🔹 선점형 전략

• ready list에서 가장 높은 우선순위 프로세스가 CPU를 할당받는다.
• 나머지 우선순위의 프로세스들은 가장 높은 우선순위 프로세스가 CPU를 요청하면 양보해야 한다.
• 높은 우선순위 프로세스에 대한 빠른 응답과 모든 프로세스들이 CPU를 공평하게 사용하도록 보장해야 한다.

🔹 선점형 우선순위 스케줄링

• 알고리즘: H가 실행 중이고 L가 도착하면, L가 선점되어서 디스패치된다.
• 선점형 우선순위 시스템
  • 높은 우선순위 태스크가 낮은 우선순위 태스크에 끼어들면(인터럽트), 높은 우선순위 태스크가 낮은 우선순위 태스크를 선점한다preempt고 한다.
  • FIFO나 RR 스케줄링 대신에 선점 방식을 사용한다.
  • 인터럽트를 초기화하기 위해 타임 슬라이스에 대응하는 고정된 속도의 클락이 사용된다.

• 기아 문제나 우선순위 역전 문제도 고려해야 한다.

우선순위 역전

우선순위 상속

---

우선순위 기부

🔹 우선순위 역전: 높은 우선순위의 스레드가 낮은 우선순위의 스레드를 기다리는 현상

🔹 우선순위 기부(상속): 락의 소유자에게 우선순위를 상속한다.

🔹 중접된 기부

• wait_on_lock: 대기 중인 락

Nested donation을 위한 자료구조

🔹 다중 기부

• Donations: Donors의 리스트

Multiple donation을 위한 자료구조

🔹 수정할 부분

static void init_thread(struct thread *t, const char *name, int priority)
// Initializes data structure for priority donation

void lock_acquire(struct lock *lock)
// If the lock is not available, store address of the lock.
// Store the current priority and maintain donated threads on list (multiple donation).
// Donate priority.

void lock_release(struct lock *lock)
// When the lock is released, remove the thread that holds the lock on donation list and set priority properly

void thread_set_priority(int new_priority)
// Set priority considering the donation.

 

[출처] KAIST OSlab - Alarm Clock and Priority Scheduling

---

Multi-level Queue

• 우선순위 스케줄링 + 각 우선순위마다 분리된 queue를 가짐
• 가장 높은 우선순위 큐 안에 있는 프로세스를 스케줄함

Multi-level Feedback Queue

• 프로세스는 다양한 큐들 사이를 이동할 수 있다: aging은 이 방식으로 구현 가능
• MLFQ 스케줄러는 다음 파라미터들로 정의된다.
  • 큐의 수
  • 각 큐의 스케줄링 알고리즘
  • 프로세스를 언제 승급/강등시킬 지 결정하는 방법
  • 프로세스가 서비스될 때 어떤 큐에 들어갈 지 결정하는 방법

Q0: RR(8ms) / Q1: RR(16ms) / Q2: FCFS

위의 그림에서 FCFS를 수행하는 어떤 태스크 J가 Q0으로 들어오면, CPU를 얻을 때 8ms동안 실행된다. 그 이후에도 끝나지 않으면 Q1으로 이동한다. Q1에서 J는 다시 FCFS를 수행하고 16ms를 받는다. 여전히 완료되지 않으면 선점되어서 Q2로 이동한다.

---

구현 진행 상황

아직 갈길이 멀다😢