24.07.10 day22 스케줄링 알고리즘 학습

1. 스케줄링 알고리즘에는 어떤 것들이 있나요?

스케줄링에는 비선점/선점 스케줄링 두 가지의 종류가 있다.

• 비선점 스케줄링은 이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법이며, 프로세스가 CPU를 할당 받으면 해당 프로세스가 완료될 때까지 CPU를 사용하지 않는다.
• 선점 스케줄링은 하나의 프로세스가 CPU를 차지하고 있을 때, 우선 순위가 높은 다른 프로세스가 현재 프로세스를 중단시키고 CPU를 점유하는 스케줄링 방식이다.

비선점 스케줄링 종류

선입선출 스케줄링(First-Come, First-Served Scheduling - FCFS)

• CPU를 먼저 요청한 프로세스가 먼저 CPU를 배정 받는 스케줄링 방식
• 프로세스가 대기 큐에 도착한 순서에 따라 CPU를 할당한다.
• 긴 작업이 먼저 들어오면 뒤에서 기다리는 짧은 작업들이 오래 기다리게 되는 호흡성 문제가 발생한다.

최단 작업 우선 스케줄링(Shortest Job Next Scheduling- SJN) 혹은 (Shortest Job First Scheduling - SJF)

• 준비 큐에서 가장 짧은 작업부터 CPU를 배정받는 스케줄링 방식
• 가장 짧은 작업부터 수행하기에 평균 대기시간이 최소화 된다.
• CPU 요구시간이 긴 작업과 짧은 작업 간의 차이가 심해 CPU 요구시간이 긴 프로세스는 기아 현상이 발생한다.

우선순위 스케줄링(Priority Scheduling)

• 각 프로세스에 우선순위를 부여하여, 우선순위가 높은 작업을 CPU에 배정하는 스케줄링 방식
• 우선순위는 중요도, 요청 시간 등의 다양한 기준에 따라 결정될 수 있으며, 이 방식은 선점형 스케줄링이 되기도 한다.
• 우선순위 스케줄링도 우선순위가 낮은 프로세스들이 무한정 대기하는 기아 현상이 발생한다.

최상 응답률 순서 스케줄링(Highest Response Ratio Next - HRRN)

• 대기시간과 실행시간을 고려한 응답 비율을 계산해 우선순위를 정하는 스케줄링 방식
• 응답률은 "(대기시간 + CPU요구랑) / CPU요구랑" 으로 계산되며, 대기시간이 올라갈수록 응답률이 높아진다.
• 이 방식은 프로세스가 기다리는 시간이 길어질수록 우선순위가 높아지기 때문에 기아 현상을 완화할 수 있다.

선점 스케줄링 종류

라운드 로빈 스케줄링(Round Robin - RR)

• 각 프로세스에 동일한 시간 할당량(time quantum)을 부여해 할당된 시간이 지나면 프로세스를 중단하고 대기열의 마지막으로 넘어간 후 다음 프로세스가 실행된다.
• 공정성을 보장하며, 응답 시간을 예측할 수 있다.
• 시간 할당량의 크기에 따라 스케줄링의 성능이 영향을 받을 수 있다.

우선순위 스케줄링(Priority Scheduling)

• 비선점 방식의 우선순위 스케줄링과 동일해 기아현상이 발생할 수 있으나 우선순위를 동적으로 조정하는 에이징(aging)이라는 방식이 사용될 수 있다.

최소 잔여 시간 우선 스케줄링(Shortest Remaining Time First - SRTF)

• 현재 남아있는 실행 시간이 가장 짧은 프로세스를 선택하여 실행하는 스케줄링 방식
• 새로운 프로세스가 도착할 때마다 남은 실행 시간을 비교하여 더 짧은 프로세스로 교체할 수 있다.
• 평균 대기 시간을 최소화하는 데는 효과적이지만, 작업의 실행 시간을 미리 알아야 하는 단점이 있다.

멀티레벨 큐 스케줄링(Multilevel Queue - MLQ)

• 프로세스를 여러 개의 큐로 나누어 처리하는 스케줄링 방식
• 각 큐는 서로 다른 우선순위를 가질 수 있으며, 각 큐 내에서는 FCFS 또는 RR 등의 스케줄링 알고리즘을 사용할 수 있다.
• 작업의 종류나 우선순위에 따라 적절한 큐로 분류하여 처리하기 때문에 효율이 좋다.

멀티레벨 피드백 큐 스케줄링(Multilevel Feedback Queue - MLFQ)

• 여러 개의 큐를 사용하며, 프로세스의 행동에 따라 큐를 이동할 수 있는 스케줄링 방식
• 새로운 프로세스는 높은 우선순위의 큐에서 시작하며, 시간이 지남에 따라 낮은 우선순위의 큐로 이동한다.
• 우선순위가 높은 큐는 작은 시간 할당량을 가지며, 낮은 우선순위의 큐는 큰 시간 할당량을 가질 수 있기 때문에, 동적으로 작업의 우선순위를 조정하여 공정성을 유지할 수 있다.

---

 

2. RR을 사용할 때, Time Slice에 따른 trade-off를 설명해 주세요.

라운드로빈 스케줄링에서 Time Slice는 각 프로세스가 CPU를 점유하는 시간 단위를 의미한다.

짧은 Time Slice

1. 장점:
   • 응답 시간 단축: 짧은 Time Slice는 각 프로세스가 빠르게 CPU를 할당받을 수 있게 하여, 응답 시간이 짧아진다.
   • 공정성 증가: 프로세스들이 공평하게 CPU 시간을 할당받으므로 공정성이 높아진다.
2. 단점:
   • 문맥 교환 오버헤드 증가: 짧은 Time Slice는 문맥 교환을 자주 발생시켜 오버헤드가 증가하는데, 이는 시스템의 전체 성능을 저하시키는 원인이 될 수 있다.
   • 처리 효율 저하: 문맥 교환에 소요되는 시간이 증가하여 실제 프로세스에 할당되는 시간이 줄어들게 된다.

긴 Time Slice

1. 장점:
   • 문맥 교환 오버헤드 감소: 긴 Time Slice는 문맥 교환의 빈도를 줄여 오버헤드를 감소시키는데, 이는 시스템의 처리 효율을 높이는 데 도움이 된다.
   • 효율적인 작업 처리: CPU 자원을 많이 사용하는 프로세스들은 더 긴 시간 동안 실행되므로, 프로세스 완료 시간이 단축될 수 있다.
2. 단점:
   • 응답 시간 증가: 긴 Time Slice는 대화형 작업의 응답 시간을 증가시킬 수 있기 때문에, 사용자 응답 시간이 많은 시스템에서는 비효율적일 수 있다.
   • 공정성 저하: 긴 Time Slice로 인해 낮은 우선순위의 작업이나 짧은 작업들이 CPU를 할당받기까지 오래 걸릴 수 있다.

적절한 Time Slice의 선택은 시스템의 특성과 요구사항에 따라 다른데, 대화형 시스템에서는 사용자 응답성이 중요하기 때문에 짧은 Time Slick가 유리하고, 배치처리 시스템에서는 문맥교환 오버헤드를 줄이고 CPU 자원을 효율적으로 사용할 수 있어야 하기 때문에 긴 Time Slice가 유리하다.

 

결론적으로, Time Slice 크기는 시스템의 응답 시간, 공정성, 처리 효율성 등에 큰 영향을 미치기 때문에, 이를 적절히 조정하여 시스템의 성능을 최적화하는 것이 중요하다.

---

3. 싱글 스레드 CPU 에서 상시로 돌아가야 하는 프로세스가 있다면, 어떤 스케쥴링 알고리즘을 사용하는 것이 좋을까요? 또 왜 그럴까요?

싱글 스레드 CPU에서 상시로 돌아가야 하는 프로세스를 선택할 때 주로 고려해야 할 요소는 우선순위, 공정성, 중요도 등의 요소가 있다.

해당 요소를 고려했을 때 우선순위 스케줄링과 멀티 피드백 큐 스케줄링을 사용할 수 있다.

 

우선순위 스케줄링(Priority Scheduling)

• 상시로 돌아가야 하는 프로세스에 가장 높은 우선순위를 부여하여, 항상 CPU 시간을 할당받을 수 있다. 이를 통해 실시간 처리가 보장된다.
• 각 프로세스에 적절한 우선순위를 부여하여, 중요도에 따라 CPU 시간을 배분할 수 있다. 이를 통해 공정성을 유지할 수 있다.
• 상시로 돌아가야 하는 프로세스에 가장 높은 우선순위를 부여하여, 빠른 응답 시간을 보장할 수 있다.

하지만 우선순위 스케줄링은 낮은 우선순위의 프로세스가 CPU를 할당받지 못하는 기아현상이 발생할 수 있으며 프로세스의 중요도를 결정하는데 어려움이 있을 수 있다.

 

멀티레벨 피드백 큐 스케줄링(Multilevel Feedback Queue - MLFQ)

• 우선순위 기반 스케줄링의 단점인 기아 현상을 해결하기 위한 스케줄링이며, 여러 개의 준비 큐를 사용해 프로세스의 우선순위를 동적으로 조정한다.
• 낮은 우선순위의 프로세스도 일정 시간 동안 CPU 시간을 할당받을 수 있어, 기아 현상을 방지할 수 있다.

전체적인 시스템 성능으로 봤을 땐 멀티레벨 피드백 큐 스케줄링을 고려할 수 있지만, 상시로 돌아가야 하는 중요한 프로세스가 있을 땐 우선순위 스케줄링이 더 적합할 수 있다.

---

4. 타 스케쥴러와 비교하여, Multi-level Feedback Queue는 어떤 문제점들을 해결한다고 볼 수 있을까요?

멀티레벨 피드백 큐 스케줄링의 장점

1. 기아 현상 해결:
   • 기존 우선순위 스케줄링은 높은 우선순위 프로세스에 CPU 시간을 독점당할 수 있어, 낮은 우선순위 프로세스가 CPU 시간을 받지 못하는 기아 현상이 발생할 수 있지만, MLFQ는 프로세스의 우선순위를 동적으로 변경하여, 낮은 우선순위 프로세스도 일정 시간 동안 CPU 시간을 할당받을 수 있어 기아 현상을 방지할 수 있다.
2. 프로세스 특성 반영:
   • 기존 스케줄링 알고리즘은 프로세스의 특성을 고려하지 않고 고정된 우선순위를 사용했으나, MLFQ는 프로세스의 특성(CPU 집중도, I/O 집중도 등)을 반영하여 동적으로 우선순위를 변경할 수 있어, 프로세스의 특성에 맞는 스케줄링이 가능하다.
3. 응답 시간 향상:
   • 기존 스케줄링 알고리즘은 프로세스의 특성을 고려하지 않아, 대화형 프로세스의 응답 시간이 느릴 수 있었지만, MLFQ는 대화형 프로세스의 우선순위를 높게 유지하여, 응답 시간을 향상시킬 수 있다.
4. 공정성 향상:
   • 기존 스케줄링 알고리즘은 프로세스의 중요도에 따른 공정성이 부족할 수 있었지만, MLFQ는 프로세스의 특성을 반영하여 동적으로 우선순위를 변경함으로써, 전체적인 시스템 성능과 공정성을 향상시킬 수 있습니다.

MLFQ는 기존 스케줄링 방식의 문제점들을 해결하여, 프로세스의 특성을 반영하고 공정성을 향상시킬 수 있는 스케줄링 기법이라고 볼 수 있다.

---

5. 유저 스레드와 커널 스레드의 스케쥴링 알고리즘은 똑같을까요?

유저 스레드와 커널 스레드 스케줄링의 차이점

1. 주체

• 커널 스레드의 스케줄링은 운영체제 커널에 의해 관리된다.
• 유저 스레드의 스케줄링은 사용자 수준 스레드 라이브러리에 의해 관리된다.

2. 방식

• 커널 스레드는 운영체제의 프로세스 스케줄러에 의해 직접 스케줄링된다.
• 유저 스레드는 사용자 수준 스레드 라이브러리에 의해 간접적으로 스케줄링되는데, 이 라이브러리는 커널 스레드에 유저 스레드를 매핑하여 스케줄링한다.

3. 정책

• 커널 스레드의 스케줄링 정책은 운영체제마다 다를 수 있다
  • 예) 라운드로빈, 선입선출, 우선순위 스케줄링 등
• 유저 스레드의 스케줄링 정책은 사용자 수준 스레드 라이브러리에 따라 다를 수 있다.

4. 오버헤드

• 커널 스레드의 스케줄링은 운영체제 내부에서 이루어지므로 오버헤드가 상대적으로 낮다.
• 유저 스레드의 스케줄링은 사용자 수준 라이브러리에서 이루어지므로 오버헤드가 상대적으로 높다.

따라서 유저 스레드와 커널 스레드의 스케줄링 알고리즘은 서로 다르며, 이에 따른 성능 차이가 있기 때문에 중요하다.

 

 

사용자 수준 스레드 라이브러리

• 사용자 수준 스레드는 운영체제가 직접 관리하는 커널 스레드와 달리, 사용자 프로그램 수준에서 구현되는 스레드이며 해당 스레드를 생성, 관리, 스케줄링 해주는 기능을 제공하는 라이브러리이다.
• 대표적인 사용자 수준 스레드 라이브러리는 POSIX Threads(Pthreads), Windows 스레드 라이브러리, Java 스레드 라이브러리 등이 있다.

특징

• 운영체제 커널의 개입 없이 사용자 공간에서 스레드를 관리하므로 오버헤드가 적다.
• 커널 스레드와 달리 시스템 전반의 스케줄링 우선순위를 지원하지 않는다.
• I/O 작업으로 인한 블록 문제, CPU 코어 사용률 저하, 보안 취약성 등의 단점이 있다.

활용

• 운영체제가 멀티스레드를 지원하지 않을 때 사용자 수준 스레드 라이브러리를 활용하여 멀티스레딩을 구현할 수 있다.
• 사용자 수준 스레드 라이브러리는 프로그래밍 언어 수준에서 스레드 기능을 제공하는 데 활용된다.

따라서 사용자 수준 스레드 라이브러리는 운영체제 수준의 스레드 관리 기능을 사용자 공간에서 구현하여 멀티스레딩을 지원하는 소프트웨어 라이브러리라고 할 수 있다.