[CS] 운영체제 3강

사담

공부 방식을 조금 수정했다. 강의를 들음과 동시에 블로그에 옮기는 것보다, 교재와 강의를 동시에 보며 아이패드에 관련 내용을 필기, 교재와 강의에서 뽑아낸 중요한 정보를 블로그에 옮기는 것이 시간이 조금 더 걸릴지 몰라도 학습에 좋을 것 같아서 그렇게 해야 할 것 같다.

프로세스 스케줄링 (3강)

스케줄링 : 여러 작업의 처리 순서 결정하기

스케줄링은 디스크 스케줄링, 프로세스 스케줄링으로 나뉘며 프로세스 스케줄링에 대해 다룬다.

스케쥴링은 작업을 활성화 시킬 때 효율적으로 작동하도록 하며, 상위단계 스케쥴링은 시스템에 들어와 작업 큐에 있는 작업을 선택하여 프로세스 생성 후 프로세스 준비 큐에 전달하는 역할을 한다.

하위 단계 스케줄링은 준비 큐에 있는 프로세스를 선택하여 사용 가능한 CPU를 할당하는 역할을 하며, 이 수행의 주체느느 디스패처(dispatcher)이다.

📌 디스패치 복습 : 프로세스가 준비 큐에 머물고 있다가, 스케쥴러에 의해 선택되어 실행 상태로 바뀔 때
프로세스에 CPU를 할당하는 과정을 디스패치(dispatch)라고 한다.

스케줄링의 목표

스케줄링할 때 고려하는 기본적인 목표 두 가지는 공정성과 균형성이다.

• 공정성 : 모든 프로세스가 적정 CPU 작업을 할 수 있게 한다.
• 균형성 : 시스템 자원이 충분히 활용될 수 있게 한다.

운영체제의 유형에 따른 스케줄링 목표

일괄처리 운영체제

• 처리량 극대화
  📌 처리량 : 주어진 시간 안에 몇 개의 프로세스를 생성 시점부터 처리할 수 있는가?
• 반환시간 최소화
  📌 반환시간 : 종료시점까지의 소요시간
• CPU 활용 극대화

시분할 운영체제

• 빠른 응답시간
  📌 요청 시점부터 반응이 시작되는 시간
• 과다한 대기시간 방지
  📌 대기시간 : 프로세스가 종료될 때까지 준비큐에서 기다린 시간의 합

실시간 운영체제

• 처리기한 맞춤

스케줄링 정책

스케줄링의 목표들은 각각 서로 상반된 경우가 있어, 모두를 한 번에 충족시키는 정책을 세우기는 어렵다.
처리량의 극대화를 위해 시간당 완료되는 프로세스 수가 많아지도록 수행 시간이 짧은 프로세스를 먼저 수행할 수도 있으며,
그저 들어온 순서대로 프로세스를 수행할 수 있지만, 그런 경우에 긴 프로세스는 대기시간과 반환 시간이 길어진다.

선점 스케줄링 정책

• 실행중인 프로세스에 인터럽트를 걸고, 다른 프로세스에 CPU를 할당한다.
• 이 방식은 높은 우선순위의 프로세스를 우선 처리하는데에 유리하다
  ex) 실시간 시스템, 시분할 시스템
• 문맥 교환에 따른 overhead가 발생할 수 있다.
  📌 문맥(context) : CPU의 모든 레지스터와 기타 운영체제에 따라 요구되는 프로세스 상태
  📌 문맥 교환 : CPU가 현재 실행하고 있는 프로세스의 문맥을 PCB에 저장하고, 문맥을 복원하는 작업을 의미한다.

⭐️ 운영체제는 문맥 교환이 매우 빠르게 실행되도록 만들어야 한다.

비선점 스케줄링 정책

• 실행 중 프로세스를 바로 준비상태로 전이 시킬 수 없는 스케줄링 방식이다.
• CPU를 할당 받아 실행이 시작된 프로세스는 대기, 종료가 될 때까지 계속 실행상태에 머무른다.
• 강제 문맥 교환이 없어 오버헤드가 발생하지 않는다.
• 대신, 오랜 시간이 걸리는 프로세스가 있다면 짧은 프로세스가 오래 기다리게 된다.

스케줄링 평가 기준

• 평균 대기 시간
• 평균 반환 시간

⭐️ 스케줄링 알고리즘

1. FCFS 스케줄링
   가장 간단하고, 비선점 방식이다.
   준비 큐에 도착한 순서에 따라 디스패치

• 장점 : 제일 간단하다
• 단점 : 중요한 프로세스가 나중에 실행될 수도 있다.
  📌 시분할 운영체제나 실시간 운영체제에는 부적합하다.
  프로세스의 도착 시간에 따라 평균 시간이 크게 변한다.

2. SJF 스케줄링
   비선점 방식이다.
   준비 큐에서 기다리는 프로세스 중 실행시간이 가장 짧다고 예상되는 것을 디스패치
   

• 장점 : 일괄처리 환경에서 구현하기 쉽다.
• 단점 : CPU 사이클을 예상할 수 없다.
  새로 들어온 짧은 프로세스가 긴 프로세스를 기다리거나, 중요한 프로세스가 나중에 실행될 수 있다.
  📌 따라서, 시분할 운영체제나 실시간 운영체제에 부적합하다.

3. SRT 스케줄링
   SJF 알고리즘의 선점 방식이다.
   준비 큐에서 기다리는 프로세스 중, 남은 실행 시간이 가장 짧은 것을 디스패치한다.

• 장점 : SJF 스케줄링에 비해서 평균 대기 시간이나 반환 시간이 더욱 효율적이다.
• 단점 : CPU사이클(예상시간)을 안다는 것이 사실상 불가능하다.
  각 프로세스 별로 실행 시간 추적, 선점을 위한 문맥교환 등 SJF보다 오버헤드가 크다.

4. RR 스케줄링
   선점 방식이다.
   정해진 시간 할당량에 의해 실행이 제한된다.
   할당량 안에 종료하지 못한 프로세스는 준비큐의 마지막에 배치된다.

• 장점 : CPU를 독점하지 않고 공평하게 이용한다.
  📌 따라서 시분할 운영체제에 적합하다.

• 단점 : 시간 할당량을 너무 크게 잡으면 FCFS 스케줄링과 동일하다.
  시간 할당량이 너무 작으면, 너무 많은 문맥 교환으로 오버헤드가 커진다.

5. HRN 스케줄링
   비선점 방식이다.
   응답 비율이 가장 큰 것을 가장 먼저 디스패치 한다.

• 장점 : SJF 스케줄링의 단점을 보완
  예상 실행시간이 긴 프로세스도 오래 대기하면 응답비율이 커져 나중에 들어오는 짧은 프로세스보다 먼저 디스패치 가능하다.
• 단점 : 사실상 CPU 사이클 시간을 예상하는 게 불가능하다.

6. 다단계 피드백 큐 스케줄링
   선점 방식이다.
   입, 출력 프로세스와 연산 중심 프로세스의 특성에 따라 서로 다른 시간 할당량을 부여한다.
   단계 1부터 단계 n까지 하나씩의 준비 큐가 존재한다.
   단계 k는 단계 k+1에 피드백한다.
   단계가 커질수록 시간 할당량도 커진다.
   입출력 위주의 프로세스는 높은 우선권을 유지한다.
   연산 위주의 프로세스는 낮은 우선권을 갖고, 긴 시간의 할당량을 가진다.

정리하기

1. 프로세서의 스케줄링을 위해 상위단계, 하위단계 및 중간단계 스케줄링이 사용된다.

2. 선점 스케줄링 정책은 실행 중인 프로세스에 인터럽트를 걸고 다른 프로세스에 CPU를 할당할 수 있는 스케줄링 방식이고, 비선점 스케줄링 정책은 실행 중인 프로세스를 바로 준비상태로 전이시킬 수 없는 스케줄링 방식이다.

3. FCFS 스케줄링은 준비 큐에 도착한 순서에 따라 디스패치하는 비선점 방식의 스케줄링 알고리즘이다.

4. SJF 스케줄링은 준비 큐에서 기다리는 프로세스 중 실행시간이 가장 짧다고 예상되는 것을 먼저 디스패치하는 비선점 방식의 스케줄링 알고리즘이다.

5. SRT 스케줄링은 준비 큐에서 기다리는 프로세스 중 남은 실행시간이 가장 짧다고 예상되는 것을 먼저 디스패치하는 선점 방식의 알고리즘이다.

6. RR 스케줄링은 프로세스가 도착한 순서대로 프로세스를 디스패치하지만, 정해진 시간 할당량에 의해 실행을 제한하는 선점 방식의 스케줄링 알고리즘이다.

7. HRN 스케줄링은 준비 큐에서 기다리는 프로세스 중 응답 비율이 가장 큰 것을 먼저 디스패치 하여 실행하는 비선점 방식의 스케줄링 알고리즘이다.

8. HRN 스케줄링의 응답비율은 예상 실행 시간이 짧을수록, 그리고 대기시간이 길수록 커진다.

9. 다단계 피드백 큐 스케줄링은 입출력 위주의 프로세스가 연산 위주의 프로세스보다 우선권을 갖도록 하는 선점 방식의 알고리즘이다.