728x90
반응형
Chapter 11 CPU 스케줄링
1. CPU 스케줄링 개요
프로세스 우선순위/ 스케줄링 큐/ 선점형과 비선점형 스케줄링
CPU 스케줄링(CPU scheduling)
- 운영체제가 프로세스에게 공정하고 합리적으로 CPU 자원을 배분하는 것
- 컴퓨터 성능하고 직결
프로세스 우선순위
프로세스마다 우선순위가 다름
-> 우선순위 ↑ 프로세스 = 빨리 처리해야 하는 프로세스(ex. 입출력 프로세스)
프로세스는 실행 상태, 대기 상태 반복하며 실행
- 입출력 집중 프로세스(I/O bound process)
- 입출력 작업 ↑ 프로세스
- ex. 비디오 재생, 디스크 백업 작업
- 실행 상태 < 입출력 위한 대기 상태
- *입출력 버스트 ↑ 프로세스
- CPU 집중 프로세스(CPU bound process)
- CPU 작업 ↑ 프로세스
- ex. 복잡한 수학 연산, 컴파일, 그래픽 처리
- 실행 상태 > 입출력 위한 대기 상태
- *CPU 버스트 ↑ 프로세스
- 입출력 버스트(I/O burst): 입출력장치 기다리는 작업
- CPU 버스트(CPU burst): CPU 이용하는 작업
=> 프로세스 중요도 맞게 프로세스가 CPU 이용 -> 우선순위(priority) 부여
프로세스의 PCB에 우선순위 명시, PCB에 적힌 우선순위 기준 -> 먼저 처리할 프로세스 결정
스케줄링 큐(scheduling queue)
운영체제가 매번 모든 PCB 검사하여 먼저 자원 이용할 프로세스 결정 -> 비효율적
=> (CPU 사용하고 싶은 프로세스/ 메모리에 적재되고 싶은 프로세스/ 특정 입출력장치 사용하고 싶은 프로세스) 줄 세움
-> 스케줄링 큐로 구현하고 관리(효율적 스케줄링)
*큐: 선입선출(First In First Out) 자료 구조 But, 스케줄링에서 반드시 X
- 준비 큐(ready queue)
- CPU를 이용하기 위해 기다리는 줄
- 대기 큐(waiting queue)
- 입출력장치 이용하기 위해 기다리는 줄
선점형과 비선점형 스케줄링
- 선점형 스케줄링(preemptive scheduling)
- 하나의 프로세스가 자원 사용 O -> 운영체제) 자원 강제로 빼앗아 다른 프로세스에 할당
- 하나의 프로세스가 자원 사용 독점 X
- 프로세스마다 정해진 시간만큼 CPU 사용, 타이머 인터럽트 발생 -> 운영체제) 자원 빼앗아 다음 프로세스에 할당
- (+) 한 프로세스의 자원 독점 막고 프로세스들에 자원 골고루 배분 O
- (-) 문맥 교환 과정에서 오버헤드 발생할 수 있음
- 비선점형 스케줄링(non-preemptive scheduling)
- 하나의 프로세스가 자원 사용 O -> 종료 or 스스로 대기 상태 전에 다른 프로세스가 끼어들 수 X
- 하나의 프로세스가 자원 사용 독점 O
- (+) 문맥 교환 과정에서 발생하는 오버헤드 ↓
- (-) 모든 프로세스 골고루 자원 사용 X
2. CPU 스케줄링 알고리즘
선입 선처리 스케줄링/ 최단 작업 우선 스케줄링/ 라운드 로빈 스케줄링
/ 우선순위 스케줄링/ 다단계 큐 스케줄링/ 다단계 피드백 큐 스케줄링
선입 선처리 스케줄링(FCFS; First Come First Served Scheduling)
- 준비 큐에 삽입된 순서대로 프로세스 처리(비선점형 스케줄링 방식)
- CPU를 먼저 요청한 프로세스부터 CPU를 할당하는 스케줄링 방식
- 공정해보이지만, 프로세스가 기다리는 시간 ↑ 확률 O
- 호위 효과(convoy effect): CPU 버스트가 ↑ 프로세스가 준비 큐 앞에 오면 그 뒤에 ↓ 프로세스도 기다려야 함
- ex. 프로세스 A: 17ms/ B: 5ms/ C: 2ms -> 프로세스 C는 2ms 실행하기 위해 22ms(17 + 5) 기다려야 함
최단 작업 우선 스케줄링(SJF; Shortest Job First Scheduling)
- 준비 큐에 삽입된 프로세스 중 CPU 이용 시간의 길이가 가장 ↓ 프로세스부터 실행
- 비선점형 스케줄링 알고리즘
- But, 선점형으로 구현 O -> 선점형 최단 작업 우선 스케줄링: 최소 잔여 시간 우선 스케줄링
라운드 로빈 스케줄링(round robin scheduling)
- 선입 선처리 스케줄링 + 타임 슬라이스
타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간- 타임 슬라이스 ↑ -> ~= 선입 선처리 스케줄링 => 호위 효과
- 타임 슬라이스 ↓ -> 문맥 교환에 발생하는 비용 ↑ => CPU) 프로레스 처리 < 프로세스 전환
- 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용(선점형 스케줄링)
최소 잔여 시간 우선 스케줄링(SRT; Shortest Remaining Time)
- 최단 작업 우선 스케줄링 알고리즘(: 작업 시간 ↓ 프로세스부터 처리)
+ 라운드 로빈 알고리즘(: 정해진 타임 슬라이스만큼 돌아가며 CPU 사용) - => 정해진 타임 슬라이스만큼 CPU 사용, 다음 프로세스는 남아있는 작업 시간 가장 ↓ 프로세스 선택
우선순위 스케줄링(priority scheduling)
- 프로세스에 우선순위 부여, 가장 ↑ 우선순위 가진 프로세스부터 실행
- 우선순위 같은 프로세스 -> 선입 선처리
- 최단 작업 우선 스케줄링(: 작업 시간 ↓ 프로세스에 ↑ 우선순위)
, 최소 잔여 시간 우선 스케줄링(: 남은 시간 ↓ 프로세스에 ↑ 우선순위)
=> 우선순위 스케줄링의 일종 - (-) 기아(starvation) 현상: 우선순위 ↓ 프로세스는 (준비 큐에 먼저 삽입되었어도) 실행 계속 연기될 수 있음
- (해결) 에이징(aging): 오랫동안 대기한 프로세스 우선순위 높이는 방식
다단계 큐 스케줄링(multilevel queue scheduling)
- 우선순위별로 준비 큐를 여러 개 사용(우선순위 스케줄링의 발전된 형태)
- 우선순위 가장 ↑ 큐에 있는 프로세스 먼저 처리, 비면 그 다음 우선순위 큐에 있는 프로세스 처리
- (+) 프로세스 유형별로 우선순위 구분하여 실행
- (+) 큐별로 타임 슬라이스 여러 개 지정, 다른 스케줄링 알고리즘 사용
- (-) 프로세스들이 큐 사이 이동 X(= 기아 현상) -> (해결) 다단계 피드백 큐 스케줄링
다단계 피드백 큐 스케줄링(multilevel feedback queue scheduling)
- 다단계 큐 스케줄링의 발전된 형태
- 프로세스들이 큐 사이를 이동 O -> 에이징 기법(: ↓ 우선순위 큐에서 오래 기다리는 프로세스 -> 점차 우선순위 ↑ 큐로 이동)
- 새로 준비 상태가 된 프로세스 O -> 우선순위 가장 ↑ 우선순위 큐에 삽입, 일정 시간(타임 슬라이스) 동안 실행
- IF. 프로세스가 해당 큐에서 실행 끝 X -> 다음 우선순위 큐에 삽입되어 실행
- => CPU를 비교적 오래 사용해야 하는 CPU 집중 프로세스 자연스럽게 우선순위 ↓
, CPU를 비교적 적게 사용하는 입출력 집중 프로세스들 자연스럽게 우선순위 ↑ 큐에서 실행
출처
[한빛미디어] 혼자 공부하는 컴퓨터 구조+운영체제
좋은 개발자는 컴퓨터를 분석의 대상으로 바라볼 뿐, 두려워하지 않는다!‘전공서가 너무 어려워서 쉽게 배우고 싶을 때’, ‘개발자가 되고 싶은데 뭐부터 봐야 하는지 모를 때’ ‘기술 면접
hongong.hanbit.co.kr
728x90
반응형
'Computer Science > 컴퓨터구조 | 운영체제' 카테고리의 다른 글
[혼자 공부하는 컴퓨터구조+운영체제] Chapter 13 교착 상태 (0) | 2024.07.25 |
---|---|
[혼자 공부하는 컴퓨터구조+운영체제] Chapter 12 프로세스 동기화 (0) | 2024.07.25 |
[혼자 공부하는 컴퓨터구조+운영체제] Chapter 10 프로세스와 스레드 (0) | 2024.07.09 |
[혼자 공부하는 컴퓨터구조+운영체제] Chapter 09 운영체제 시작하기 (0) | 2024.07.09 |
[혼자 공부하는 컴퓨터구조+운영체제] Chapter 08 입출력장치 (0) | 2024.01.08 |