[PintOS] Thread - Priority Scheduling (Project 1, WIL)

들어가기 전에

운영체제의 동작 과정(Dual-Mode Execution)

• User Mode : 일반적 응용프로그램 구동 환경
• Kernel Mode : 커널 구동 환경(User Mode와 달리 system call(H/W 관련) 호출 가능) ◀️ PintOS 환경

첫 운영체제 구동 시 초기화 작업 및 부팅 작업으로 인해 커널 모드로 시작되고, 곧바로 사용자 모드로 전환된다. 이는 Kernel Mode에서의 작업이 컴퓨터 전반에 영향을 줄 수 있는 작업이기에 일반 사용자의 접근을 제한하기 위함이다.

• User Mode에서 'system call'을 호출
• User Mode에서 작업이 불가능한 것을 운영체제에 위임

Interrupt?

Interrupt(인터럽트)란 컴퓨터 시스템에서 발생하는 '중단 신호'로 CPU가 특정 프로그램 실행 시 '잠깐' 중단시키고 다른 작업 수행 후 기존 작업으로 돌아가게 하는 메커니즘이다. 예를 들어, 일을 하다가 전화가 울리면(인터럽트) 전화를 끝낸 후에 다시 원래 하던일로 돌아가는 것과 유사하다.

 

Interrupt 동작 과정

1. 인터럽트 요청 발생
   • ex. 네트워크 카드에서 데이터 패킷이 도착한 순간에 인터럽트 요청 발생 가능
2. 프로그램 수행 중단
   • 시스템 안정성을 위해 '현 실행 중인 명령어가 완료되는 시점'에 프로그램 중단
3. 상태저장
   • 프로그램 카운터(PC)에 저장된 주소와 상태 레지스터 등의 중요 정보를 주로 '스택'에 저장하는 방식으로 안전하게 저장
4. 인터럽트 전처리 실행
   • 인터럽트 원인 파악
   • CPU는 인터럽트 벡터를 통해 인터럽트 서비스 루틴 위치를 찾아서 루틴 실행
5. 인터럽트 서비스 루틴(ISR) 실행
   • 인터럽트 '원인 처리'
6. 복원 및 실행 재개
   • 스택에 저장되어 있던 PC 값과 상태 레지스터가 복원되며 기존 수행 중단되었던 지점에서 실행 재개

System Call

시스템 콜(System Call)이란?

프로세스가 시스템의 자원이나, 서비스(H/W)를 필요로 할 경우 운영체제에 요청하는 것을 시스템 콜이라고 한다. 유저모드에서는 수행될 수 없고, 반드시 Kernel Mode로 호출(call)하여서 수행되어야 한다. 

시스템 콜의 동작 과정

User application(process)에서 시스템 콜 호출 시

1. Process는 'Kernel mode'로 진입
2. OS는 각 시스템 콜에 고유번호 할당 후 각 번호에 맞는 제어 루틴 정의
3. 커널은 서비스 루틴 처리 후 다시 사용자 모드로 전환하여 기존의 프로세스가 계속 실행되도록 함

시스템 콜 발생 시 기능이나 시스템 환경에 따라 더 많은 정보가 담긴 '매개변수'가 필요할 수 있다. 매개 변수를 전달하는 방법에는 세 가지가 있다.

• 매개 변수를 CPU 레지스터를 통해 전달함
  • 속도가 빠르며, CPU 레지스터에 직접 매개변수를 저장함
  • CPU 레지스터의 개수가 한정되어 있기에 다량 전달에는 부적합
• 메모리를 통해 전달함
  • 매개변수가 많거나 크기가 클 경우 메모리에 매개변수를 저장 후 메모리 주소를 레지스터에 전달
  • 데이터 양에 제한이 없어 효율적
• 스택을 통한 전달
  • 프로그램에서 매개변수를 스택에 push(전달) 후 커널은 이 스택에서 매개변수를 pop하여 사용
  • 스택 순서대로 데이터를 처리하기 용이

Priority Scheduling("우선 순위가 높은 작업이 먼저 실행돼야지!")

용광로가 600도 씨를 넘어가면, 온도를 내려야 하는 작업이 수행되어야 하는 경우를 생각해보자. 이 작업의 우선순위는 매우 높다. 그런데, 다른 하찮은 작업을 하느라 이 작업이 후 순위로 밀리면 어떻게 될까? 온도를 내리지 못 해 대형사고로 이어질 수 있다. 이와 유사한 일이 NASA에서 실제로 있었다(!).

이렇게 중요한 '우선 순위 스케쥴링'에 대해 알아보자.

Priority Inversion Problem

한양대학교 PintOS 강의자료

우선순위가 높은 쓰레드가 우선순위 낮은 쓰레들를 기다리는 현상을 Priority Inversion이라고 한다. 이러한 Inversion 발생 시 위에서 언급한 문제가 발생할 수 있기에 적절한 처리가 필수다. 여러 방법 중 Priority가 높은 Thread의 Priority를 낮은 Thread가 받는 방법이 있다. 이를 'donation'이라고한다.

Multiple Donation

한양대학교 PintOS 강의자료

위 이미지의 Thread M, Thread H와 같이 여러 Thread에서 한 Thread에 여러번 donation하는 상황이다.(Thread L, M, H는 각각 Priority Low, Medium, High)

• Thread M, H와 같이 여러 Thread에서 한 Thread L에 여러번 donation 하는 상황
• Thread L은 우선순위가 가장 높은 Thread H부터 실행 후 다음 우선순위(M)로 넘어감

Nested Donation

한양대학교 PintOS 강의자료

• Thread H는 lock B를 요청하고 ➡️ lock B를 얻을 때까지 대기하고, lock B의 Holder인 Thread M은 Lock A를 요청하고 ➡️ 얻을 때까지 대기
• Thread H ➡️ M ➡️ L 순으로 H의 우선순위가 Thread L, M에게 모두 donation 되어야 함 

 

🐛 구현 중 발생 가능한 버그(사진 첨부 예정)

• Thread가 종료되지 않고(혹은 새로운 Thread가 시작 않고) 무한 loop에 빠지는 버그
  
  • 종료 Thread 다음을 연결해주는 포인터를 확인할 필요가 있음(포인터 없을 경우 무한 loop)
  • Thread가 종료 자체를 못하는 경우는 못 본 거 같음
• 테스트 케이스의 Output이 배열일 경우 행에서 우선순위 변동이 없는 경우
  • init_priority에 Thread의 초기 priority가 할당되어 잘 활용되는지 확인 필요