Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 배열
- 안드로이드
- BOJ
- 분할정복
- 생명주기
- 동적계획법
- 코딩
- Android
- GIT
- 코딩테스트
- BFS
- 세그먼트트리
- 알고리즘
- 스택
- 그래프
- 자바
- 이분탐색
- 프로그래머스
- component
- 카카오블라인드
- 완전탐색
- activity
- 문자열다루기
- 백준
- 운영체제
- 트리
- 다이나믹프로그래밍
- 코틀린
- dfs
- 문자열
Archives
- Today
- Total
HS_development_log
CPU 스케줄링 본문
반응형
CPU 스케줄링
CPU 스케줄링 이란?
- 준비 큐의 프로세스들 중에서 CPU를 할당할 순서를 정하는 것
- 운영체제의 단기 스케줄러가 수행함
언제 CPU 스케줄링을 할까?
- 실행 상태에서 대기 상태로 전환될 때
- 실행 상태에서 준비 상태로 전환될 때
- 대기 상태에서 준비 상태로 전환될 때
- 종료할 때
CPU 스케줄링 기준
- CPU 사용률(Utilization)
- 단위 시간당 CPU 사용시간의 비율
- 처리량(Throughput)
- 단위 시간당 완료된 프로세스의 개수
- 반환시간(Turnaround time)
- 특정 프로세스를 실행하는데 걸린 총 시간
- 대기시간(Waiting time)
- 프로세스가 준비 큐에서 대기하면서 기다린 시간의 합
- 응답시간(Response time)
- 작업을 요청한 후 첫번째 응답이 나올 때까지의 시간
선점(preemptive)과 비선점(nonpreemptive)
- 선점 : CPU를 사용하던 프로세스가 CPU를 빼앗김
- 비선점 : CPU가 한 프로세스에 할당되면, 프로세스가 CPU를 반환할 때까지 CPU를 사용함
CPU 스케줄링 알고리즘
FCFS(First-Come, First-Served) : 비선점식
- 프로세스가 준비큐에 도착한 순서대로 처리하는 알고리즘
- Convoy effect 발생가능
- 실행시간이 짧은 프로세스가 긴 프로세스 뒤에서 기다리는 것
- 비선점식 방식이므로 자신이 CPU를 반납하기 전까지는 CPU를 계속 점유함
- 시분할 시스템에 사용할 수 없음
SJF(Shortest-Job-First) : 비선점식
-
각 프로세스의 다음 CPU 버스트 크기를 비교하여 가장 작은 것을 가진 프로세스에게 CPU를 할당함
- 버스트 크기가 작은 프로세스 부터 처리해야 평균 대기시간이 작아지기 때문
SRTF(Shortest-Remaining-Time-First) : 선점식
- 선점식 SJF
- 새로 도착하는 프로세스가 생겼을때, 새 프로세스의 CPU 버스트 크기가 현재 실행 중인 프로세스의 남아있는 CPU 버스트보다 작다면 새 프로세스에게 CPU를 할당함
<다음 CPU 버스트 크기 결정>
- 정확한 값은 알 수 없고, 예측해서 사용한다
- 이전 CPU 버스트의 크기를 이용하여 지수 평균(exponential averaging) 방법을 사용해서 추정
RR(Round Robing) : 선점식
- 시분할 시스템을 위해 만들어짐
- 각 프로세스는 시간할당량 동안 CPU를 할당 받는다. 시간량은 보통10~100 밀리초이다. 이 시간이 지나면 프로세스는 CPU를 빼앗기고 준비 큐의 끝에 들어간다
- 준비큐는 선입 선출 방식이다.
- 운영체제는 타이머 인터럽트를 설정하여 주기적으로 인터럽트를 일으킨다. 인터럽트가 발생하면 , 운영체제가 실행되므로 이때 스케줄러를 실행한다
시간 할당량 : 2
<RR 스케줄링의 시간할당량>
- 시간 할당량이 크면 FCFS 방식이 된다
- 시간 할당량이 적다면, Context Switch의 부담이 증가한다
- 대부분의 CPU버스트 시간은 10밀리초 미만이므로 시간할당량을 10정도로 설정하면 스스로 CPU를 반환하므로 Context Switch 부담이 줄어든다.
Multilevel Queue : 선점식
-
준비 큐를 여러 개의 큐로 나눈다
- 전면 작업(대화식) : 빠른응답 시간을 요구함 - RR
- 후면 작업(일괄처리) : FCFS
-
각 큐는 낮은 우선순위의 큐보다 절대적인 우선순위를 가진다.
-
우선순위가 높은 큐의 프로세스가 처리되지 않으면 낮은 우선순위 큐에 있는 프로세스는 처리될 수 없다
-
문제점 : 기아상태
- 우선순위가 낮은 큐의 프로세스가 영영 실행되지 못하는 경우 발생
-
해결법 : 각 큐는 CPU의 일정량을 분배 받음
- 전면 작업은 CPU의 80%, 후면 작업은 CPU의 20%
Multilevel Feedback Queue : 선점식
- 프로세스가 큐 사이를 이동하는 Multilevel Queue 방식
- CPU를 많이 사용하는 프로세스는 낮은 우선순위 큐로 이동시킨다
- 입출력 중심, 대화식 프로세스들은 높은 우선순위 큐로 이동시킨다
- 높은 우선순위의 큐가 비어야 낮은 우선순위의 큐의 프로세스가 실핼 될 수 있다. 낮은 우선순위의 큐의 프로세스가 실행되는 도중, 높은 우선순위의 큐에 프로세스가 들어오면 선점된다
- 문제점 : 기아상태
- 우선순위가 낮은 큐의 프로세스가 영영 실행되지 못하는 경우 발생
- 해결법 : 에이징
- 낮은 우선순위의 큐에서 오래 대기하는 프로세스들을 높은 우선순위의 큐로 이동
HRN(Hightest Response-rate Next) : 비선점식
- 가변식 우선순위의 비선점식 스케쥴링
- 우선순위가 높은 프로세스에게 먼저 CPU를 할당
- 우선순위 = (대기시간+CPU burst) / CPU burst
- 따라서 CPU burst가 짧을수록 우선순위가 높고, 오래 대기할수록 우선순위가 높다
반응형