운영체제 5주차 정리 - 2

스케줄링 및 IPC - 스케줄링 기법

---

스케줄링 평가 방법

---

CPU 사용률(%)

- 전체 시스템의 동작 시간 중 프로세스들이 CPU를 사용한 비율을 측정
- 높을 수록 운영체제의 성능이 좋음

처리량

- 단위 시간당 작업을 마친 프로세스의 수
- 수치가 클수록 좋은 알고리즘

 

시간

대기 시간 : 프로세스가 생성된 후 실행되기 전까지 대기하는 시간
- 예: 실행 파일 더블클릭 후 실제 구동시작 시간의 차이

응답 시간 : 첫 작업을 시작한 후 첫 번째 출력(반응, response, feedback)이 나오기까지의 시간

- 예: 실행프로그램 UI 생성된 시간

실행 시간 : 프로세스 작업이 시작된 후 종료되기까지의 시간
- 예: 실행프로그램의 동작시간

반환 시간 : 대기 시간을 포함하여 실행이 종료될 때까지의 시간
- 예: 실행프로그램의 종료시간(전체 시간)

평균 대기 시간

---

FCFS 방식

---

FCFS

- First Come First Served : 선입선출
- 큐에 도착한 순서대로 CPU를 할당

FCFS의 평균 대기시간 계산

FCFS 평가

만약 처리 시간이 긴 프로세스가 CPU를 차지
= 다른 프로세스들은 하염없이 기다려 시스템의 효율성이 떨어짐

만약 작업 중인 프로세스가 입출력 작업을 요청
= CPU가 작업하지 않고 쉬는 시간이 많아져 작업 효율이 떨어짐

---

SJF 방식

---

SJF

- Shortest Job First : 최단 작업 우선
- 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당
- 콘보이 효과를 완화하여 시스템의 효율성을 높임

SJF의 평균 대기시간 계산

SJF의 단점

- 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어려움
- 작업 시간이 길다는 이유만으로 계속 뒤로 밀려 공평성이 현저히 떨어짐 = 아사(starvation) 현상

 

아사 해결 방법
- 에이징(Aging, 나이 먹기)
- 순서를 양보할 때마다 나이를 한 살씩 먹임
- 프로세스가 양보할 수 있는 상한선을 정함

---

HRN 방식

---

HRN

- Highest Response Ratio Next : 최고 응답률 우선
- SJF 스케줄링에서 발생할 수 있는 아사 현상을 해결하기 위해 만들어진 비선점형 알고리즘
- 대기 시간과 CPU 사용 시간을 고려하여 스케줄링을 하는 방식
- 여전히 공평성이 위배되어 많이 사용되지 않음

HRN의 평균 대기시간 계산

① 대기시간 0을 먼저 채택
② 우선순위(가중치)를 추출
③ 우선순위 순으로 프로세스를 나열(가중치가 높은 값이 먼저 채택)

---

라운드 로빈 방식

---

라운드 로빈 스케줄링의 동작 방식

- 한 프로세스가 할당받은 시간(타임 슬라이스, 타임 슬롯) 동안 작업
- 작업을 완료하지 못하면 준비 큐의 맨 뒤로 이동 전환
- 다시 자기 차례를 기다림
- 선점형 알고리즘 중 가장 단순하고 대표적인 방식
- 프로세스들이 작업을 완료할 때까지 계속 순환

효과적으로 작동하려면 문맥 교환에 따른 추가 시간을 고려하여 타임 슬라이스를 적절히 설정해야 함

 

타임 슬라이스가 큰 경우
- 하나의 작업이 끝난 뒤 다음 작업이 시작
- FCFS 스케줄링과 다를 게 없음

타임 슬라이스가 작은 경우
- 문맥 교환이 너무 자주 일어남
- 문맥 교환에 시간을 너무 많이 소모 = 프로세스의 CPU 점유 시간을 단축(성능저하 발생)

---

SRT 방식

---

SRT

- 라운드 로빈 + SJF(Shortest Job First)
- CPU의 할당은 남은 작업 시간이 가장 적은 프로세스를 선택
- 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산
- 프로세스의 종료 시간을 예측하기 어렵고 아사 현상 발생

---

기타 방식

---

우선순위

- 프로세스의 중요도에 따른 우선순위를 반영한 스케줄링 알고리즘
- 우선순위가 낮은 프로세스는 아사 현상이 발생될 수 있음

다단계 큐

우선순위에 따라 준비 큐를 여러 개 사용
- 우선순위에 따라 해당 우선순위의 큐에 삽입

상단의 큐의 모든 작업 완료 후 하단 큐 진행 = 아사 현상 유발

다단계 피드백 큐

프로세스가 실행될 때마다 프로세스의 우선순위를 낮춤

 

다단계 큐의 낮은 우선순위 프로세스의 아사 현상을 해결

우선순위에 따라 타임 슬라이스의 크기가 다름
- 우선순위가 낮아질수록 CPU를 얻을 확률이 낮아짐
- 한번 CPU를 잡을 때 많이 작업하라는 기회를 줌