시험 준비하면서 정리했습니다. 문제가 되면 삭제하겠습니다.
1. CPU 스케줄링 개요
CPU 스케줄링
- 준비 상태(Ready)에 있는 스레드들 중 하나를 선택하여 CPU를 할당하는 과정이다.
- 오늘날 운영체제에서 실행 단위가 스레드이므로 CPU 스케줄링은 스레드를 대상으로 한다.
1.1. 다중프로그래밍과 스케줄링
다중 프로그래밍의 목적
- CPU 이용률을 최대화하기 위해 항상 실행 중인 프로세스를 가지게 하는데 있다.
- 다중 프로그래밍 도입 이후 운영체제는 작업 스케줄링, CPU 스케줄링을 시행한다.
작업 스케줄링
-메모리에서 적재된 프로세스가 종료하면 디스크에서 기다리는 작업 중 하나를 선택하여
메모리 적재하는 작업.
CPU 스케줄링
-실행 중인 프로세스가 I/O를 실행할 때 메모리에 적재된 다른 프로세스 중 CPU에 실행시킬
프로세스를 선택하는 과정
1.2 CPU burst와 I/O burst
CPU burst
- 프로그램 실행 중 CPU 연산(계산 작업)이 연속적으로 실행되는 상황
I/O burst
- 프로그램 실행 중 I/O 장치의 입출력이 이루어지는 상황
=> 프로그램은 CPU burst – I/O burst를 반복한다.
1.3 CPU 스케줄링의 기본 목표
- CPU 활용률 극대화
- 컴퓨터 시스템 처리율 향상
1.4 CPU 스케줄링 기준(criteria)
스케줄링 알고리즘을 평가하는 기준(척도)
1) CPU 활용률(CPU utilization)
- 전체 시간 중 CPU의 사용 시간 비율, 운영체제 입장
- 10%라는 것은 10시간 중 1시간만 CPU가 스레드를 실행하고 9시간은 놀고 있다는 소리이다.
2) 처리율(throughput)
- 단위시간당 처리하는 프로세스의 개수, 운영체제 입장
3) 공평성(fairness)
- CPU를 스레드들에게 공평하게 배분, 사용자 입장
- 시분할로 스케줄링
- 무한정 대기하는 기아 스레드(starving thread)가 생기지 않도록 스케줄
4) 응답시간(response time)
- 대화식 사용자의 경우, 사용자에 대한 응답 시간, 사용자 입장
5) 대기시간(waiting time)
- 스레드가 준비 큐에서 머무르는 시간, 운영체제와 사용자 입장
6) 소요시간(turnaround time)
- 프로세스(스레드)가 컴퓨터 시스템에 도착한 후 완료될 때까지 걸린 시간, 사용자 입장
- 배치 처리 시스템에서 주된 스케줄링의 기준
7) 시스템 정책(policy enforcement) 우선
- 컴퓨터 시스템의 특별한 목적을 달성하기 위한 스케줄링, 운영체제 입장
-ex) 보안 시스템에서는 안전을 관리하는 스레드를 우선 실행하는 정책
8) 자원 활용률(resource efficiency)
- CPU나 I/O 장치 등의 자원 활용률 극대화
1.5 CPU 스케줄링과 타임 슬라이스
타임 슬라이스(타임 퀀텀, 타임 슬롯)
- 스케줄된 스레드에게 한 번 할당하는 CPU 시간
- 커널이 스케줄을 단행하는 주기 시간
- 타이머 인터럽트의 도움을 받앙 타임 슬라이스 단위로 CPU 스케줄링
2. CPU 스케줄링 기본
2.1 CPU 스케줄링이 실행되는 4가지 상황
1) 스레드가 시스템 호출 끝에 I/O를 요청하여 블록될 때
- 스레드를 블록 상태로 만들고 스케줄링(CPU 활용률 향상 목적)
2) 스레드가 자발적으로 CPU를 반환할 때
- yield() 시스템 호출 등을 통해 스레드가 자발적으로 CPU 반환
- 커널은 현재 스레드를 준비 리스트에 넣고, 새로운 스레드 선택 (CPU의 자발적 양보)
3) 스레드의 타임 슬라이스가 소진되어 타이머 인터럽트 발생
- (균등한 CPU 분배 목적)
4) 더 높은 순위의 스레드가 요청한 입출력 작업 완료, 인터럽트 방생
- 현재 스레드를 강제 중단시켜 준비 리스트에 넣고, 높은 순위의 스레드를 깨워 스케줄링
(우선순위를 지키기 위한 목적)
2.2 CPU 스케줄링과 디스패치(dispatch)
Q. 스케줄링 담당하는 커널 스레드나 프로세스가 있는가?
A. 없다.
Q. 스케줄링 코드는 어디에 위치해 있는가?
A. 커널 내 함수로 위치되어 있다.
Q. 스케줄링 코드가 실행되는 시점은 언제인가?
A. 시스템 호출이나 인터럽트 서비스 루틴이 끝나는 마지막 단계에서 실행된다.
디스패쳐 코드: 컨텍스트 스위칭을 실행하는 커널 코드
- 스케줄러에 의해 선택된 스레드를 CPU가 실행하도록 하는 작업
- 커널 모드에서 사용자 모드로 전환
- 새로 선택된 스레드가 이전에 중단된 곳에서 실행하도록 점프
2.3 스케줄링 타입: 선점 스케줄링과 비선점 스케줄링
실행 중인 스레드의 강제 중단 여부에 따른 CPU 스케줄링 타입
1) 비선점 스케줄링(non-preemptive scheduling)
- 현재 실행 중인 스레드를 강제로 중단시키지 않는 타입
- 일단 스레드가 CPU를 할당 받아 실행을 시작하면, 완료되거나 CPU를 더 이상 사용할 수 없는
상황이 될 때까지 스레드를 강제 중단 시키지 않고 스케줄링도 하지 않는 방식
- CPU를 더 이상 사용할 수 없게 된 경우: I/O로 인한 블록 상태, sleep 등
- 자발적으로 CPU를 양보할 때, 실행 중 종료할 때
- 스케줄링 알고리즘: SRTF, Priority 스케줄링
2) 선점 스케줄링(preemptive scheduling)
- 현재 실행중인 스레드를 강제 중단시키고 다른 스레드 선택
- 타임 슬라이스가 소진되어 타이머 인터럽트가 발생될 때
- 인터럽트나 시스템 호출 종료 시점에서, 더 높은 순위의 스레드가 준비 상태일 때
- 스케줄링 알고리즘: RR, SJF, Priority(preemptive version)
2.4 기아와 에이징
기아(starvation)
-스레드가 스케줄링에서 선택되지 못한 채 오랜 동안 준비 리스트에 있는 상황
사례
- 우선순위를 기반으로 하는 시스템에서, 더 높은 순위의 스레드가 계속 시스템에 들어오는 경우
- 짧은 스레드를 우선 실행시키는 시스템에서, 자신보다 짧은 스레드가 계속 도착하는 경우
- 기아가 발생하지 않도록 설계하는 것이 바람직함
에이징(aging)
- 기아의 해결책
- 스레드가 준비 리스트에 머무르는 시간에 비례하여 스케줄링 순위를 높이는 기법
- 오래 기다릴 수 있지만 언젠가는 가장 높은 순위에 도달하는 것 보장
3. 다양한 CPU 스케줄링 알고리즘
3.1 FCFS(First Come First Served)
비선점 스케줄링. 도착한 순서대로 처리(선입선처리)
1) 스케줄링 파라미터: 스레드 별 도착 시간
2) 스케줄링 타입: 비선점 스케줄링
3) 스레드 우선 순위 : 없음
4) 기아: 발생하지 않음
-스레드가 오류로 인해 무한 루프를 실행한다면, 뒤 스레드 기아 발생
5) 성능 이슈
- 호위효과(Convoy Effect) 발생 : 긴 CPU burst를 실행하는 스레드가 양도나 종료할 때 까지
뒤에 스레드 들은 기다려야함.
- 처리율은 낮지만 단순하고 구현이 용이하다.
3.2 SJF(Shortest Job First)
비선점 스케줄링. 가장 짧은 스레드 우선 처리(최단 작업 우선 스케줄링)
1) 스케줄링 파라미터: 스레드 별 예상 실행 시간(이 시간을 아는 것은 불가능. 비현실적)
2) 스케줄링 타입: 비선점 스케줄링
3) 스레드 우선 순위 : 없음
4) 기아: 발생가능
- 짧은 스레드가 계속 도착하면, 긴 스레드는 실행 기회를 언제 얻을 지 예측할 수 없음
5) 성능 이슈
- 짧은 스레드가 먼저 실행되므로 평균 대기 시간 최소화
- 실행 시간의 예측이 불가능하므로 현실에서는 거의 사용되지 않음
3.3 SRTF(Shortest remaining time first)
선점형 스케줄링. 남은 시간 짧은 스레드 우선 처리
1) 스케줄링 파라미터: 스레드 별 예상 실행 시간과 남은 실행 시간 값(이 시간을 아는 것은 불가능)
2) 스케줄링 타입: 선점 스케줄링
3) 스레드 우선 순위 : 없음
4) 기아: 발생가능
- 짧은 스레드가 계속 도착하면, 긴 스레드는 실행 기회를 언제 얻을 지 예측할 수 없음
- 짧은 스레드가 먼저 실행되므로 평균 대기 시간 최소화
- 실행 시간의 예측이 불가능하므로 현실에서는 거의 사용되지 않음
3.4 Round-robin(preemptive)
선점형 스케줄링. 스레드들을 돌아가면서 할당된 시간(타임 슬라이스)만큼 실행.
1) 스케줄링 파라미터: 타임 슬라이스
2) 스케줄링 타입: 선점 스케줄링
3) 스레드 우선 순위 : 없음
4) 기아: 없음
- 스레드의 우선순위가 없고, 타임 슬라이스가 정해져 있어 일정 시간 후에 스레드는 반드시 실행
5) 성능 이슈
- 잦은 스케줄링으로 전체 스케줄링 오버헤드 (특히 타임 슬라이스가 작을 떄)
- 균형된 처리율: 타임슬라이스가 크면 FCFS에 가까움, 적으면 SJF/SRTF에 가까움
3.5 Priority 스케줄링
우선 순위를 기반으로 하는 스케줄링. 가장 높은 순위의 스레드 먼저 실행
1) 스케줄링 파라미터: 스레드 별 고정 우선 순위
2) 스케줄링 타입: 선점 스케줄링 / 비선점 스케줄링
3) 스레드 우선 순위: 있음
4) 기아: 발생 가능
- 지속적으로 높은 스레드가 큐에 도착하는 경우 스레드에 기아 발생 가능.
- 에이징기법으로 해결 가능
5) 성능 이슈
- 높은 우선순위의 스레드일수록 대기 혹은 응답시간 짧음
- 스레드별 고정 우선 순위를 가지는 실시간 시스템에서 사용
3.6 MLQ(Multilevel queue scheduling)
스레드들을 n개의 우선순위 레벨로 구분하고 레벨이 높은 스레드를 우선 처리
- 고정된 n개의 큐 사용, 각 큐에 고정 우선순위 할당
- 스레드들의 우선순위도 n개의 레벨로 분류
- 각 큐는 나름대로의 기법으로 스케줄링
- 스레드는 도착 시 우선 순위에 따라 해당 레벨 큐에 삽입. 다른 큐로 이동할 수 없음
- 가장 높은 순위의 큐가 빌 때, 그 다음 순위의 큐에서 스케줄링
1) 스케줄링 파라미터: 스레드의 고정 우선 순위
2) 스케줄링 타입: 선점 스케줄링 / 비선점 스케줄링 모두 가능
3) 스레드 우선 순위: 있음
4) 기아: 발생 가능
- 높은 순위의 스레드가 계속 도착하는 경우 실행 기회를 언제 얻을 지 예상할 수 없음
- MLFQ 스케줄링을 이용해 기아 문제 해결
5) 성능 이슈
- 스레드와 큐 모두 n개의 우선순위 레벨로 할당. 스레드는 자신의 레벨과 동일한 큐에 삽입
- 높은 순위를 가진 스레드들의 대기 시간이나 응답 시간이 짧은 장점
3.7 MLFQ(Multi-level Feedback Queue)
CPU burst가 짧은 스레드나 I/O 작업이 많은 스레드, 대화식 스레드를 우선 실행
- 큐만 n개의 우선순위 레벨을 둠. 스레드는 동일한 우선순위
- 스레드는 제일 높은 순위의 큐에 진입하고 큐 timeSlice가 다하면 아래 레벨의 큐로 이동
- 낮은 레벨의 큐에 오래 있으면 높은 레벨의 큐로 이동
- I/O 집중 스레드(대화식 스레드)는 높은 순위의 큐에 있을 가능성 높음
1) 스케줄링 파라미터: 각 큐의 큐 타임슬라이스
2) 스케줄링 타입: 선점 스케줄링
3) 스레드 우선 순위: 없음
4) 기아: 없음
- 큐에 대기하는 시간이 오래되면, 더 높은 레벨의 큐로 이동시킴 (에이징 기법)
5) 성능이슈
- 짧거나 입출력이 빈번한 스레드, 혹은 대화식 스레드를 높은 레벨의 큐에서 빨리 실행
-> CPU 활용률이 높음
4. 멀티 코어 CPU에서의 스케줄링
1. 멀티 코어 시스템의 구조
2. 멀티 코어 시스템에서의 CPU 스케줄링
문제점 1. 컨텍스트 스위칭 오버헤드 증가 문제
- 이전에 실행된 적이 없는 코어에 스레드가 배치될 때떄
- 캐시에 새로운 스레드의 코드와 데이터로 채워지는 긴 경과 시간
=> 해결: CPU 친화성(CPU affinity) 적용 -> 스레드를 동일한 코어에서만 실행하도록 스케줄링
문제점 2. 코어별 부하 불균형 문제
- 스레드를 무작위로 코어에 할당하면, 코어마다 처리할 스레드 수의 불균형 발생
- 부하 균등화 기법으로 해결
=>해결: 푸시 마이그레이션(push migration) 기법
감시 스레드가 짧거나 빈 큐를 가진 코어에 다른 큐의 스레드를 옮겨놓는 기법
=>해결: 풀 마이그레이션(pull migration) 기법
코어가 처리할 스레드가 없게 되면, 다른 코어의 스레드 큐에서 자신이 큐로 가져와 실행시키는 기법
'OS' 카테고리의 다른 글
| [운영체제(OS)] 8장 메모리 관리 (0) | 2023.08.07 |
|---|---|
| [운영체제(OS)] 6장 스레드 동기화 (0) | 2023.08.07 |
| [운영체제(OS)] 4장 스레드와 멀티스레딩 (0) | 2023.08.07 |
| [운영체제(OS)] 3장 프로세스와 프로세스 관리 (0) | 2023.08.07 |
| [운영체제(OS)] 2장 컴퓨터 시스템과 운영체제 (1) | 2023.08.07 |