[PintOS Project 1 - Threads] 2번 Priority Scheduling

높은 우선순위

• 쓰레드가 양보
• 락 세마포어 또는 조건변수 대기할 때 우선순위가 가장 높은 대기 스레드를 꺠움
• 우선순위 063 (PRI_MIN PRI_MAX)
• 초기 쓰레드 우선순위는 thread_create()에 인수에 우선순위 저장
• 우선순위 선택 이유 없으면 PRI_DEFAULT(31) 사용
• 우선순위 역전(Priority inversion)
  • 높은 우선순위의 스레드가 낮은 우선순위의 스레드가 소유한 락(lock)을 기다릴 때, 그 낮은 우선순위의 스레드가 일시적으로 높은 우선순위를 "기부받아" 실행 우선순위를 높이는 개념

구현 계획

1. 기존 코드 분석:

   • thread.c 파일을 열어 현재 스레드 우선순위 관리 방식과 실행 순서에 대한 구조를 이해합니다. 특히 스레드가 준비 리스트에 추가되는 부분과 우선순위 비교를 중점적으로 확인하세요.

2. 우선순위 스케줄링 구현:

   • 새로운 스레드가 준비 리스트에 추가될 때, 현재 실행 중인 스레드보다 우선순위가 높으면 CPU를 양보하도록 코드를 수정합니다. 이를 위해 thread_yield 또는 스케줄러를 수정해야 할 수 있습니다.

3. 우선순위 기부 구현:

   • 락을 소유한 스레드가 락을 기다리는 높은 우선순위 스레드가 있을 경우, 락 소유 스레드의 우선순위를 올리는 로직을 추가합니다.
   • 중첩 기부를 위해 여러 스레드 간 우선순위 기부를 관리할 수 있는 자료구조를 만들고, 기부를 처리하는 함수를 구현합니다.

4. 우선순위 변경 함수:

   • 스레드가 자신의 우선순위를 변경할 수 있도록 하는 함수를 작성합니다. 우선순위를 낮추는 경우 CPU를 즉시 양보하는 로직도 포함해야 합니다.

5. 테스트 케이스 작성:

   • 다양한 상황에서 우선순위 스케줄링과 기부가 잘 작동하는지 확인하기 위해 테스트 케이스를 작성하세요. 여러 스레드가 동시에 실행되는 시나리오를 시뮬레이션하는 것이 좋습니다.

해야할것

1. 주요 목표

   • Pintos는 FIFO(선입선출) 스케줄링 방식을 사용합니다.
   • PintOS의 스케줄러를 우선순위 스케줄링으로 수정합니다.
     • 스레드의 우선순위에 따라 준비 리스트를 정렬합니다.
     • 동기화 원시(세마포어, 조건 변수)에 대한 대기 리스트를 정렬합니다.
     • 프리엠프션(Preemption)을 구현합니다.
       • 프리엠프션 포인트: 스레드가 준비 리스트에 추가될 때(타이머 인터럽트가 호출될 때마다가 아님).

2. 수정할 파일

   • threads/thread.* : 스레드 관련 기능을 관리하는 파일.
   • threads/synch.* : 동기화 원시 관련 기능을 관리하는 파일.

자세한 설명

1. 우선순위 스케줄링 구현

• FIFO에서 우선순위 스케줄링으로: 기본적으로 Pintos는 FIFO 방식을 사용하지만, 우선순위 스케줄링을 적용하려면 준비 리스트를 스레드의 우선순위에 따라 정렬해야 합니다. 즉, 높은 우선순위를 가진 스레드가 준비 상태일 때, 현재 실행 중인 스레드는 즉시 CPU를 양보해야 합니다.

2. 대기 리스트 정렬

• 동기화 원시의 대기 리스트 정렬: 세마포어 또는 조건 변수를 사용하여 대기 중인 스레드도 우선순위에 따라 정렬해야 합니다. 즉, 우선순위가 높은 스레드가 먼저 깨어나야 합니다.

3. 프리엠프션 구현

• 프리엠프션: 스레드가 준비 리스트에 추가될 때, 스케줄러가 현재 실행 중인 스레드와 새로 추가된 스레드의 우선순위를 비교하여, 새 스레드의 우선순위가 더 높으면 CPU를 양보하게 합니다. 이 과정을 통해 더 높은 우선순위를 가진 스레드가 즉시 실행될 수 있도록 합니다.

4. 수정해야 할 파일

• threads/thread.* 파일은 스레드 생성 및 관리, 우선순위 조정과 관련된 함수들이 정의되어 있습니다. 여기에 우선순위 기반 스케줄링 로직을 추가해야 합니다.

• threads/synch.* 파일은 동기화 원시의 구현이 포함되어 있으며, 이곳에서 대기 리스트의 정렬 및 우선순위 기부와 같은 추가 기능을 구현해야 합니다.