4. CPU 스케줄링

1. CPU 스케줄링

스케줄링의 단계

고수준 스케줄링: 전체 시스템의 부하를 고려하여 작업을 시작할지 말지 결정

중간수준 스케줄링: 시스템에 과부하가 걸려서 프로세스 수를 조절해야 한다면 이미 활성화된 프로세스 중 일부를 보류 상태로 보냄

저수준 스케줄링: 실제 작업 수행

스케줄링의 목적

• 공평성: 모든 프로세스가 자원을 공평하게 배정받아야 함
• 효율성: 시스템 자원이 유휴 시간없이 사용되도록 해야하고, 유휴 자원을 사용하려는 프로세스에 우선권을 줘야함
• 안정성: 우선순위를 사용하여 중요 프로세스가 먼저 작동하도록 배정함으로써 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호해야함
• 확장성: 프로세스가 증가해도 안정적으로 작동하게 해야함
• 반응 시간 보장: 시스템은 적절한 시간안에 프로세스의 요구에 반응해야함
• 무한 연기 방지: 특정 프로세스의 작업이 무한히 연기되면 안됨

---

2-1. 선점형 스케줄링, 비선점형 스케줄링

선점형 스케줄링

• 운영체제의 판단하에 실행 상태에 있는 프로세스를 중단시키고 새로운 작업을 시작할 수 있는 방식
• 프로세스가 CPU를 독점할 수 없어 대화형 시스템, 시분할 시스템에 적합
• 대부분의 저수준 스케줄러는 선점형 사용

비선점형 스케줄링

• 프로세스가 실행 상태에 들어가면 프로세스가 종료되거나 자발적으로 대기 상태에 들어가기 전에는 계속 실행되는 방식
• 스케줄러의 작업량이 적고 문맥 교환 적음
• CPU 사용이 긴 프로세스가 있다면 사용시간이 짧은 프로세스가 기다리기 되어 전체 시스템의 처리율이 떨어짐
• 일괄 작업 방식 스케줄링에 사용

---

2-2. 프로세스 우선 순위

• 커널 프로세스 > 일반 프로세스
• 우선순위가 높은 프로세스가 CPU를 먼저, 오래 차지

---

2-3. CPU 집중 프로세스, 입출력 집중 프로세스

CPU 집중 프로세스

수학 연산같은 CPU를 많이 사용하는 프로세스, CPU 버스트가 많은 프로세스

입출력 집중 프로세스

저장장치에서 데이터를 복사하는 일 같이 입출력을 많이 사용하는 프로세스, I/O 버스트가 많음

우선 배정

• 스케줄링할 때, 입출력 집중 프로세스의 우선순위를 CPU 집중 프로세스보다 높이면 시스템 효율 향상

---

2-4. 전면 프로세스, 후면 프로세스

전면 프로세스

• GUI를 사용하는 OS에서 가장 앞에 있는 프로세스
• 현재 입출력을 사용하는 프로세스
• 사용자와 상호작용 가능한 프로세스

후면 프로세스

• 사용자와 상호작용이 없는 프로세스
• 사용자의 입력없이 동작하므로 일괄 작업 프로세스라고도 함

---

2-5. 정리

---

3-1. 준비 상태의 다중 큐

준비 상태의 다중 큐

• 프로세스는 준비 상태에 들어올 때마다 자신의 우선순위에 해당하는 큐의 마지막에 삽입
• CPU 스케줄러는 우선순위가 가장 높은 큐의 맨 앞에 있는 프로세스에 CPU 할당
• 0번큐, 1번큐, 2번큐에 각각 프로세스 (1, 2, 3) (4, 5, 6) (7, 8, 9)로 3개의 프로세스가 있다면 0번 큐의 1번 프로세스가 가장먼저 CPU에 할당됨

프로세스 우선순위 배정 방식

1. 고정 우선순위 방식
   1. 운영체제가 우선순위를 부여하면 프로세스가 끝나기 전까지 변하지 않음
   2. 구현은 쉽지만, 작업 효율이 떨어짐
2. 변동 우선순위 방식
   1. 생성시 부여받은 우선순위가 작업 중간에 변하는 방식
   2. 구현은 어렵지만, 작업 효율이 좋다

---

3-2. 대기 상태의 다중 큐

대기 상태의 다중 큐

• 효율을 위해 같은 입출력을 요구한 프로세스끼리 모아 놓음
• 준비 상태 큐는 한번에 하나의 프로세스를 CPU에 할당하지만, 대기 상태 큐는 여러 개의 PCB를 동시에 꺼내어 준비 상태로 옮김
• 대기 상태 큐에서 동시에 끝나는 인터럽트를 처리하기 위해 인터럽트 벡터라는 자료구조 사용

---

4. 스케줄링 알고리즘

스케줄링 알고리즘 평가 기준

대기 시간: 프로세스가 생성된 후 실행전까지 대기하는 시간

응답 시간: 첫 작업을 시작한 후 첫 번째 출력이 나오기까지의 시간

실행 시간: 프로세스 작업이 시작된 후 종료까지 걸리는 시간

반환 시간: 대기 시간을 포함해서 실행이 종료될 때까지의 시간

평균 대기 시간: 모든 프로세스 대기시간의 평균

---

FCFS 스케줄링

• 준비 큐에 도착한 순서대로 CPU에 할당하는 비선점형 방식
• 큐가 하나라 모든 프로세스 우선순위가 동일

FCFS 스케줄링 평가

• 처리시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들이 기다리는 시간 증가 → 효율 ↓
• 현재 작업중인 프로세스가 입출력을 요청하면 CPU가 쉬는 시간이 많아짐 → 효율 ↓

---

SJF 스케줄링(Shortest Job First)

• 준비 큐에 있는 프로세스 중 가장 실행시간이 짧은 것부터 CPU를 할당하는 비선점형 방식
• FCFS의 문제점 완화

SJF 스케줄링 평가

• OS가 프로세스의 종료시간을 정확하게 예측하기 어려움
• 작업시간이 길다는 이유로 뒤로 밀려 공평성이 떨어짐 → 아사(기아) 현상
• 에이징 → 아사 현상 완화, 양보할 수 있는 상한선을 정하는 방식, 양보할때마다 나이를 먹어 양보의 상한선에 다다르면 더 이상 양보 X

  ---

 

HRN 스케줄링(Highest Response Ratio Next)

• SJF의 아사 현상 해결하기 위한 비선점형 알고리즘
• 기다린 시간과 CPU 사용 시간을 고려해서 스케줄링
• 우선순위 = (대기시간 + CPU 사용 시간) / CPU 사용 시간

HRN 스케줄링 평가

• 실행시간이 짧은 프로세스를 우선으로 하면서도 대기 시간을 고려하여 아사현상 완화
• 그럼에도 공평성에 위배됨

  ---

 

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

• 한 프로세스가 할당받은 시간(타임 슬라이스/타임 퀀텀)동안 작업을 하고 완료하지 못하면 준비 큐의 맨 뒤로 가서 대기하는 방식
• 선점형 알고리즘 중 가장 단순하고 대표적인 방식
• 모든 프로세스가 작업을 완료할 때까지 순환하며 실행

라운드 로빈 스케줄링 평가

• RR과 FCFS의 평균 대기시간이 같다면 RR이 더 비효율
• RR과 같은 선점형 방식에서는 문맥 교환 시간이 필요하기 때문

  ---

 

SRT 우선 스케줄링(Shortest Remaining Time)(First)

• 프로세스가 도착했을 때 실행중인 프로세스를 멈추고 스케줄링을 재실행
• 가장 남은 시간이 적은 프로세스를 실행함
• 선점형 방식

SRT 우선 스케줄링 평가

• 현재 프로세스와 큐에 남아있는 프로세스의 남은 시간을 계산하여 더 적은 프로세스와 문맥교환할 때 SJF에 없는 추가적인 계산이 들어감
• OS가 프로세스 종료 시간을 예측하기 어렵고 아사현상이 일어날 수 있어서 사용 잘 안함

  ---

 

우선 순위 스케줄링

• 미리 정해놓은 우선 순위에 따라 스케줄링
• 비선점형, 선점형 모두 적용 가능
• 고정 우선 순위 알고리즘: 한번 정한 우선 순위가 변동 X, 효율 떨어짐
• 변동 우선 순위 알고리즘: 일정 시간마다 우선 순위를 새로 계산해서 반영, 효율 증가

우선 순위 스케줄링 평가

• 아사현상 유발
• 준비 큐의 순서를 무시하고 우선 순위에 따라 바꿔야하기 때문에 오버헤드 발생, 효율 ↓

  ---

다단계 큐 스케줄링

• 우선 순위에 따른 큐를 여러 개 사용하는 방식
• OS로부터 부여받은 우선 순위에 따라 프로세스가 삽입
• 고정형 우선 순위 사용
• 상단 큐의 작업이 모두 끝나야 그 다음 큐의 작업 실행

다단계 피드백 큐 스케줄링(MLFQ; Multi-Level Feedback Queue)

• 프로세스가 CPU를 할당받을 때마다 프로세스 우선 순위를 낮춤
• 우선 순위에 따라 타임 슬라이스 크기가 다름
• 우선 순위가 낮은 큐는 타임 슬라이스가 큼
• 마지막 큐의 타임 슬라이스는 무한대 + FCFS 스케줄링 방식으로 동작

---

5. 인터럽트

폴링

입출력을 요청하면 OS가 주기적으로 입출력 장치를 직접 확인해서 처리하는 방식

인터럽트

입출력을 요청하고 입출력이 완료되면 이벤트를 발생시켜 알림

동기적 인터럽트

• 프로세스가 실행중인 명령어로 발생

비동기적 인터럽트

• 하드웨어적 오류로 발생

인터럽트 처리 과정

1. 인터럽트가 발생하면 현재 실행중인 프로세스는 일시정지 상태, 재시작을 위한 정보 저장
2. 인터럽트 컨트롤러가 인터럽트 실행 순서 결정
3. 정해진 순서에 따라 인터럽트 벡터에 등록된 인터럽트 핸들러가 이를 실행
4. 인터럽트 처리를 마치면 일시정지된 프로세스 재실행 or 종료