[운영체제] 쉽게 배우는 운영체제 4장 CPU 스케줄링 (2/2)

03 다중 큐

준비 상태의 다중 큐

각 프로세스는 자신의 pcb에 우선순위 정보를 포함한다.

준비 상태에 있는 프로세스들은 실행 상태로 넘어가기 전까지 큐에 순서대로 대기하는데,

우선순위 파악과 스케줄링의 효율성 제고를 위해 우선순위별로 큐를 구성한다. (다중 큐, multiple queue)

프로세스의 우선순위를 배정하는 방식

• 고정 우선순위 방식(static priority) : 운영체제가 프로세스에 부여한 우선순위가 프로세스 작업이 끝날 때까지 변하지 않음. 구현하기 쉬우나, 고정된 우선순위로 인해 시스템의 변화에 대응하기 어렵다는 단점 존재.
• 변동 우선순위 방식(dynamic priority) : 프로세스 작업 중간에 우선순위가 변하는 방식. 구현의 어려움은 있으나 시스템 효율성 제고에는 도움이 된다. 
  • 반전 우선순위(priority inversion) : 낮은 우선순위의 프로세스에 높은 우선순위를 부여해서 빨리, 자주 CPU를 사용하도록 하여 작업을 빨리 끝내도록 하는 것. 낮은 우선순위 프로세스가 CPU를 too much로 잡아놓지 않기 위해 사용하는 전략

대기 상태의 다중 큐

대기 상태에는 : 입출력을 기다리는 프로세스들이 모여있다.

관리의 효율성을 위해 : 같은 입출력을 요구하는 프로세스들끼리 모아둠

 

+) 준비 상태의 다중 큐 / 대기 상태의 다중 큐 비교

준비 큐는 한 번에 하나의 PCB만 실행 상태로 CPU에 넘길 수 있음 🆚 대기 큐는 여러 개의 PCB를 준비 상태로 옮길 수 있음

why? 시스템의 많은 입출력 장치 때문. 입출력이 동시에 완료되면 여러 인터럽트가 한꺼번에 처리됨. 인터럽트 벡터 구조를 따라 완료된 PCB들은 모두 준비 상태로 이동함

"인터럽트 벡터 Interrupt vector" : 동시에 끝나는 인터럽트를 처리하기 위해 사용하는 자료 구조. 동시에 완료된 입출력 정보와 처리 방법이 담겨 있음.

🦧 CPU 스케줄러가 전체적으로 관리하는 과정
PCB는 준비 상태의 다중 큐에 삽입됨 ➡️ 스케줄러가 PCB를 실행 상태로 옮김
➡️ 입출력 요청이 들어오면 대기 상태의 다중 큐에 삽입됨 ➡️ 입출력이 완료되면 준비 상태의 다중 큐로 다시 삽입됨.

---

04 스케줄링 알고리즘

스케줄링 알고리즘의 선택 기준

• CPU 사용률 : 전체 시스템의 동작 시간 중 CPU가 사용된 시간
• 처리량 : 단위 시간당 작업을 마친 프로세스의 수. 클수록 좋음
• 대기 시간 : 작업을 요청한 프로세스가 작업 시작 전까지 대기하는 시간. 짧을수록 좋음
• 응답 시간 : 프로세스 시작 후 첫번째 출력(반응)이 나올 때까지 걸리는 시간. 짧을수록 좋음
• 반환 시간 : 프로세스가 종료되어 사용하던 모든 자원을 반환하는 데 걸리는 시간. [ 반환시간 = 대기시간 + 실행시간 ]

CPU 알고리즘의 효율성 평가 시 고려되는 요소들 : 대기 시간, 응답 시간, 반환 시간

스케줄링 알고리즘 성능 비교 기준 : 평균 대기 시간 [ 평균 대기 시간 = 모든 프로세스의 대기 시간의 합 / 프로세스의 수 ]

 

이해를 돕기 위해 설정한 프로세스 도착 순서와 작업 시간의 예

도착 순서	도착 시간	작업 시간
P1	0	30
P2	3	18
P3	6	9

FCFS 스케줄링

- FCFS : First Come First Served

준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식.

하나의 큐에 프로세스가 도착한 순서대로 실행. 모든 프로세스의 우선순위는 동일하다.

- 성능 : ( 0 + 27 + 42 ) / 3 = 23 밀리초

- 평가 : 단점1) 콘보이 효과 : 컨베이어 벨트에 작업물이 늘어서 있을 때 앞의 작업이 오래 걸려 뒤의 작업이 지연되는 현상

            단점2) 현재 작업 중인 프로세스의 입출력 작업이 요청됐을 때 CPU가 작업하지 않고 쉬는 시간이 많아져 작업효율 떨어짐

---

SJF 스케줄링

- SJF : Shortest Job First

준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식

- 성능 : ( 0 + 24 + 36 ) / 3 = 20 밀리초

P1이 작업할 동안 큐에 들어온 P2, P3 중 작업시간이 짧은 P3를 P1 다음으로 CPU에 할당한다. (대기시간 : 30 - 6 = 24 밀리초)

- 평가 : FCFS스케줄링의 단점인 콘보이 효과를 개선하여 효율성을 높였다.

단점 1) 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어려워 프로세스 작업 길이를 명확하게 결정지을 수 없음.

단점 2) 아사 현상(starvation), 무한 봉쇄 현상(infinite blocking) : P3같은 작업물이 계속 들어와 P2의 작업이 계속해서 연기되는 현상. 공평성을 해치는 요소가 됨.

---

HRN 스케줄링

- HRN : Highest Response Ratio Next

서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 스케줄링을 하는 비선점형 방식

우선순위 결정 기준 : 우선순위 = ( 대기 시간 + CPU 사용 시간 ) / CPU 사용 시간

- 성능 : ( 0 + 24 + 36 ) / 3 = 20 밀리초

P2의 우선순위 : ( 27 + 18 ) / 18 = 2.5 밀리초

P3의 우선순위 : ( 24 + 9 ) / 9 =  3.67 밀리초

숫자가 클수록 우선순위가 높으므로 P3의 우선순위가 높다. P3 먼저 실행

- 평가 : SJF의 starvation 현상을 개선하였다. 대기 시간이 긴 프로세스의 우선순위를 높여 CPU를 할당받을 확률을 높임

(여전히 공평성은 해결되지 않는 문제)

---

라운드 로빈 스케줄링

- Round Robin (RR) : 프로세스가 타임 슬라이스 동안 작업을 완료하지  못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식.

우선순위가 적용되지 않은 가장 단순한 선점형 스케줄링 방식

선점형 알고리즘 중 가장 단순, 대표적인 방식. 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행됨.

- 성능 : ( 0 + 7 + 14 + 19 + 19 + 8 ) / 3 = 22.33 밀리초

p1은 가장 먼저 도착하므로 대기시간 없이 바로 타임 슬라이스 동안 작업 (0)

p2는 3 밀리초 이후 도착하여 7 밀리초 동안 대기 후 작업 시작 (7)

p3는 6 밀리초 이후 도착하여 4 밀리초(p1 작업 시간) + 10 밀리초 (p2 작업 시간) 동안 대기 후 작업 시작 (14)  // 이후 p3는 작업 완료

p1은 p2, p3 작업이 끝나길 기다린 후(10 + 9) 다시 작업 시작 (19)

p2는 p3, p1 작업이 끝나길 기다린 후(9 + 10) 다시 작업 시작 (19) // 이후 p2는 작업 완료

p1은 p2 작업이 끝나길 기다린 후 다시 작업 시작(8)

- 평가 : FCFS 스케줄링과의 차이점 ) 타임 슬라이스의 존재. 타임 슬라이스 동안만 작업이 가능하다. 콘보이 효과의 완화.

효과적인 라운드 로빈 스케줄링을 위해서는 적절한 타임 슬라이스 크기의 설정이 필요하다.

 

+ 타임 슬라이스의 중요성

너무 크면) 하나의 작업이 끝나고 다음 작업이 시작되는 것 같아 보임. 프로세스가 뚝뚝 끊기고 반응 속도가 느릴 것.

너무 작으면) 여러 프로그램이 동시에 실행되는 것처럼 보이지만 시스템의 전반적인 성능 저하됨. 문맥 교환이 너무 자주 일어나 문맥 교환 시간이 실제 작업시간보다 커질 수 있으며 이는 시간 낭비. 실제 작업을 제대로 못하는 문제가 발생한다.

그럼 어떻게 설정?) 되도록 작게 설정하되, 문맥 교환에 걸리는 시간을 고려해 적당한 크기로 하는 것이 중요

---

SRT 우선 스케줄링

- SRT : Shortest Remaining Time

라운드 로빈 스케줄링을 기본적으로 사용, 프로세스 할당 시 잔여 작업 시간이 가장 적은 프로세스를 먼저 할당

- 성능 : ( 0 + 4 + 16 + 27 ) / 3 = 15.66 밀리초

p1 작업 후 ( 대기시간 0 ) p2, p3이 순서대로 도착하지만 p3의 작업 시간이 더 짧아서 p3를 p1 다음으로 실행 ( 대기시간 10-6 = 4 )

p1 잔여 작업 시간 (20), p2 작업 시간 (18) 중 p2의 것이 더 작으므로 p2를 다음으로 실행 ( 대기시간 10 + 9 - 3 = 16 )

p1 잔여 작업 시간 (20), p2 잔여 작업 시간 (8) 중 p2의 것이 더 작으므로 p2를 또 다음으로 실행 ( 대기시간 0 )

p1만 작업하면 됨 ( 대기시간 9 + 10 + 8 = 27 ) //p3, p2, p2 작업을 모두 기다렸으므로

- 평가 : 잘 사용하지 않음.

현재 실행 중인 프로세스, 큐에 있는 프로세스의 남은 시간을 계속 계산해야 하므로 작업이 추가되는 셈. 프로세스의 종료 시간 예측하기 어렵고 starvation 현상 발생 가능성 높으므로

---

우선순위 스케줄링

프로세스의 우선순위를 반영한 스케줄링 알고리즘

• 고정 우선순위 알고리즘 : 프로그램 실행 - 종료 시까지 변하지 않는 우선순위. 실시간으로 변하는 시스템의 상황을 반영하지 못해 효율성 떨어짐
• 변동 우선순위 알고리즘 : 일정 시간마다 우선순위를 다시 계산하여 반영. 시스템의 상황을 잘 반영하기 때문에 효율성 좋음

- 평가 : 공평성을 위배, starvation 현상 발생 가능(준비 큐에 있는 순서를 고려하지 않으므로)

            오버헤드 발생(프로세스 우선순위를 매번 바꿔야 하므로 효율성 저하)

---

다단계 큐 스케줄링

- Multilevel queue : 우선순위에 따라 준비 큐를 여러 개 사용하는 선점형 방식

라운드 로빈 방식으로 운영되는 큐, 우선순위는 고정형 우선순위를 사용

- 평가 : 우선순위에 따라 다양한 스케줄링이 가능 (ex_우선순위에 따라 타임 슬라이스를 조절, 프로세스의 작업 형태를 고려해 스케줄링...)

우선순위가 높은 상위 큐 프로세스의 작업이 끝나기 전에는 하위 큐의 프로세스가 작업을 할 수 없음.

우선순위가 높은 프로세스때문에 우선순위가 낮은 프로세스의 작업이 연기되는데, 이를 막기 위해 만든 것이 다단계 피드백 큐 스케줄링.

---

다단계 피드백 큐 스케줄링 // 오늘날 운영체제가 일반적으로 사용하는 CPU 스케줄링 방식 

- Multilevel feedback queue : 다단계 큐 스케줄링과 기본적인 형태는 동일. 각기 다른 우선순위의 큐를 사용.

특징) 프로세스가 CPU를 사용하고 나면 한단계 낮은 우선순위의 준비 큐로 돌아간다 ☜ 낮은 우선순위 프로세스의 실행이 연기되는 문제를 완화

특징) 우선순위에 따라 타임 슬라이스의 크기가 다르다. 낮은 우선순위에게 더 큰 타임 슬라이스 ☜ 어렵게 얻은 작업 기회. CPU를 좀 더 오래 사용할 수 있도록 해주는 것. 가장 마지막 우선순위의 큐는 FCFS 스케줄링 방식으로 동작.

---

05 인터럽트 처리

동기적 vs 비동기적 인터럽트

• 동기적 인터럽트(synchronous interrupt) : 사용자 인터럽트. 프로그램상의 문제로 인한 인터럽트, 의도적으로 프로세스를 중단하기 위한 인터럽트, 입출력장치 같은 주변 장치의 조작에 의한 인터럽트, 산술연산 중 발생하는 인터럽트
• 비동기적 인터럽트(asynchronous interrupt) : 하드웨어적인 오류로 발생하는 인터럽트, 키보드 인터럽트, 마우스 인터럽트 등

인터럽트 처리 과정

- 각 인터럽트에는 고유 번호, IRQ가 존재. 시스템에 인터럽트가 발생하면 IRQ로 인터럽트를 식별함.

- 인터럽트 벡터 : 동시에 발생하는 인터럽트를 하나로 묶어서 처리하는 개념. 인터럽트와 인터럽트 핸들러를 일대일로 연결한 자료 구조.

- 인터럽트 핸들러 : 인터럽트를 처리를 위해 미리 정의된 함수(해당 인터럽트가 발생하면 어떤 일을 처리할 것인지)

1. 인터럽트 발생 시 : 현재 실행 중인 프로세스 → 일시 정지 상태. 재시작하기 위해 현재 프로세스 관련 정보를 임시 저장
2. 인터럽트 컨트롤러 실행 → 인터럽트의 처리 순서를 결정.
   동시에 여러 개의 인터럽트가 발생한 경우 : 인터럽트의 우선순위를 고려하여 중요한 인터럽트부터 실행되도록 조절
3. 처리할 인터럽트가 결정되면 : 인터럽트 벡터에 등록된 인터럽트 핸들러가 실행됨. 함수가 실행되며 인터럽트를 처리.
4. 핸들러가 인터럽트를 처리하면 : 일시 정지된 프로세스가 다시 실행되거나 종료됨.

인터럽트와 이중 모드

- 프로세스의 구분 : 커널 프로세스 / 사용자 프로세스

• 커널 모드 : 운영체제와 관련된 커널 프로세스가 실행되는 상태
• 사용자 모드 : 사용자 프로세스가 실행되는 상태
• 이중 모드 : 운영체제가 커널 모드, 사용자 모드를 전환하며 일 처리를 하는 것
  사용자 모드에서 사용자 프로세스가 커널 프로세스가 작업을 요청한 경우 ☞ 사용자 프로세스는 대기 상태로 전환 ☞ 사용자 모드에서 커널 모드로 전환 ☞ 커널 프로세스가 요청받은 작업을 처리 ☞ 다시 사용자모드로 전환 ...

- 이중 모드를 사용하는 이유 : 운영체제가 자원을 보호하기 위하여

커널은 시스템 호출을 통해서만 자원에 접근 하도록 제한. 사용자 프로세스는 커널 모드에서 실행될 수 없는 것.

- API (Application Programming Interface) : 운영체제가 제공하는 것. 커널의 시스템 호출은 사용하기 어렵고 제한적이기 때문에 API의 다양한 함수들을 통해 사용자가 좀더 편리하게 시스템 자원에 접근할 수 있도록 한 것

 

- 사용자가 커널 모드로 진입하는 경우

1. 시스템 호출을 사용한 경우
   사용자가 원하는 것이므로 자발적
2. 인터럽트를 발생시킨 경우
   프로세스가 인터럽트를 발생시켰다는 것은 잘못된 명령을 수행하여 동기적 인터럽트가 발생했다는 것. 프로세스가 강제 종료됨. 따라서 비자발적