[크래프톤 정글 Week 08 ] Pintos-project1-Priority Scheduling 키워드 정리

Pintos-project1-Priority Scheduling 키워드 정리

이 포스트 는 Pintos-Project1 의 과제중 Priority Scheduling 구현 에 필요한 내용을 담고있습니다.

---

" Project 1 에서 구현하게될 Alaram clock , Priority scheduler , MLFQS 전부 스케쥴링 방법 이라기 보다 스케쥴러가 실행 시킬 스레드를 선택 하기위한 ready 큐 에 스레드를 어떤 순서로 삽입 할지에 대한 방법론 인 것이다."

Alaram Clock 에서는 스레드를 Ready 큐 에 정렬 하기 위해 기준을 시간을 사용하여 일정 간격으로 스레드를 재우고 깨웠다면 Priority scheduler 에서는 우선순위를 사용하여 스레드의 우선순위 가 높은 순으로 정렬 하여 Ready 큐에 삽입하는 방법이다.

일단 이 글에서 모든 개념에서 예시를 들기에는 시간도 없고 내용도 너무 많다. 그래서 일단 기술적 정의 만 우선 적어두고 구현 과정에서 더 자세히 알아보려고 한다.

---

알아볼 키워드

• Process, Thread
• PU Scheduling 알고리즘
  • FCFS (First Come First Served)
  • SJF (Shortest Job First)
  • SRTF (Shortest Remaining Time First)
  • Round Robin
  • Multilevel Queue Scheduling
• Semaphore와 Mutex
• Race Condition
• Deadlock
• Context Switching
• Multi-Level Feedback Queue Sched

---

1. Process와 Thread

• Process:
  • 프로세스는 운영체제에서 실행 중인 프로그램의 인스턴스로, 각 프로세스는 독립된 메모리 공간(코드, 데이터, 힙, 스택)을 가진다.
  • 운영체제는 프로세스를 각각의 독립적인 작업 단위로 취급하며, 프로세스 간에는 메모리가 공유되지 않아 안전한 실행이 가능하다.
• Thread:
  • 스레드는 프로세스 내에서의 실행 단위로, 같은 프로세스 안에서 여러 개의 스레드가 생성될 수 있으며 메모리 공간을 공유한다.
  • 스레드 간에는 코드, 데이터, 힙을 공유하여 효율적이고 빠른 통신이 가능하지만, 동시에 공유 자원 사용에 따른 동기화 문제가 발생할 수 있다.

---

2. CPU Scheduling 알고리즘

- FCFS (First Come First Served)

• 가장 먼저 도착한 프로세스부터 순차적으로 CPU를 할당받는 방식.
• 대기 시간이 길어질 수 있으며, 특히 긴 작업이 먼저 들어오면 전체 프로세스의 대기 시간이 증가하는 Convoy Effect가 발생할 수 있다.

- SJF (Shortest Job First)

• 실행 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식.
• 평균 대기 시간을 줄일 수 있지만, 실행 시간을 예측하기 어렵고 짧은 프로세스가 계속 들어올 경우 긴 작업이 기아 상태에 빠질 수 있다.

- SRTF (Shortest Remaining Time First)

• 현재 남은 실행 시간이 가장 짧은 프로세스에 CPU를 할당하는 방식으로, SJF와 유사하나 현재 실행 중인 작업보다 더 짧은 작업이 들어오면 CPU를 교체한다.
• 평균 대기 시간 최적화에 좋으나, 잦은 문맥 교환(Context Switching)이 발생할 수 있다.

- Round Robin

• 프로세스들이 일정한 시간(시간 할당량)을 정해 순차적으로 CPU를 할당받는 방식.
• 각 프로세스에 공평한 기회를 제공하고, 작업 응답 시간을 개선하는 효과가 있지만, 할당량이 짧으면 문맥 교환 비용이 늘어나고 할당량이 길면 응답성이 떨어질 수 있다.

- Multilevel Queue Scheduling

• 프로세스들을 성격에 따라 여러 개의 큐로 나누고, 각 큐마다 다른 스케줄링 알고리즘을 적용하는 방식.
• 예를 들어, 대화형 작업을 위해 높은 우선순위 큐에 짧은 대기 시간 알고리즘을, 배치 작업을 위한 큐에는 FCFS와 같은 알고리즘을 적용하여 CPU 할당의 효율을 높인다.

---

3. Semaphore와 Mutex

• Semaphore:
  • 특정 자원을 동시에 사용할 수 있는 프로세스나 스레드의 수를 제한하는 동기화 도구. 일반적으로 카운터로 표현되며, P(wait)와 V(signal) 연산을 사용해 자원의 접근을 제어한다.
• Mutex:
  • 하나의 자원에 대해 단 하나의 프로세스 또는 스레드만 접근할 수 있도록 하는 동기화 도구로, Binary Semaphore의 일종이다.
  • Mutex는 자원을 소유한 스레드가 작업을 완료한 후에만 해제할 수 있어 소유권을 기반으로 하는 락(Lock)을 제공한다.

---

4. Race Condition

• Race Condition은 두 개 이상의 프로세스나 스레드가 동시에 공유 자원에 접근할 때, 실행 순서에 따라 예기치 않은 결과가 발생할 수 있는 상황을 말한다.
• 예를 들어, 두 스레드가 동시에 같은 변수 값을 변경할 때 실행 순서에 따라 변수 값이 달라지는 현상이 발생할 수 있다. 이를 해결하기 위해 Semaphore, Mutex 등을 사용해 동기화 메커니즘을 적용한다.

---

5. Deadlock

• Deadlock은 두 개 이상의 프로세스가 서로의 자원을 점유한 상태에서 다른 프로세스의 자원을 기다리며 무한정 대기하는 상태를 말한다.
• 교착 상태가 발생하려면 상호 배제, 점유 및 대기, 비선점, 환형 대기라는 4가지 조건이 모두 만족되어야 한다.
• 교착 상태를 방지하기 위해 자원 할당 방지나 자원 회수 기법 등이 사용된다.

---

6. Context Switching

• Context Switching은 CPU가 현재 실행 중인 프로세스 또는 스레드의 상태를 저장하고, 다음 실행할 프로세스나 스레드의 상태를 불러오는 작업을 말한다.
• 프로세스의 문맥에는 CPU 레지스터, 프로세스 상태, 프로그램 카운터 등이 포함되며, 스케줄러에 의해 새로운 작업이 할당될 때마다 문맥 교환이 발생한다.
• 문맥 교환은 필수적이지만, 그 과정에서 오버헤드가 발생하기 때문에 효율적인 스케줄링이 필요하다.

---

7. Multi-Level Feedback Queue Scheduler (MLFQS)

• MLFQS는 여러 개의 큐를 사용해 스레드의 CPU 점유 패턴에 따라 우선순위를 동적으로 조정하고, 각 큐에 스레드를 배치하는 방식이다.
• 주기적으로 스레드의 우선순위를 재평가하며, 높은 우선순위 큐는 CPU를 많이 점유하지 않는 대화형 작업, 낮은 우선순위 큐는 장시간의 CPU 작업이 필요한 배치 작업을 위한 것으로 구분된다.
• 각 큐에 다른 스케줄링 알고리즘을 적용해 유연하고 효율적인 자원 할당이 가능하며, 기아 방지를 위해 일정 시간 후 낮은 큐에서 높은 큐로 이동하는 방식도 적용할 수 있다.