CU
스케쥴링
- 프로세스 : 프로그램을 실행하는 주체
- 쓰레드: 작업을 처리하는 주체
프로세스 배정조건
-
공통
-
오버헤드 (↓)
- 프로세스가 필요한 자원보다 더 많이 사용하는 것 -
사용률 (↑)
- 프로세스가 최대한 자원을 많이받고 빨리 처리하는 것 -
기아 현상 (↓)
- 프로세스가 자원할당을 못 받고 대기하는 것
-> 오버헤드는 낮게, 사용률은 높게, 기아 현상은 낮게
-
-
목표에 따른 배정조건
-
배치 시스템
- 가능한 많은 일을 수행
- 시간보단 처리량이 중요 -
대화형 시스템
- 빠른 응답 시간
- 적은 대기 시간이 중요 -
실시간 시스템
- 최소 응답시간이 중요
-
- 정책에 따른 3가지 우선순위
- CPU 이용률을 최대화
- 오버헤드를 최소화
- 모든 프로세스가 공평하게 분배
스케쥴링의 단위
-
프로세스의 실행은 CPU 실행과 입/출력 대기의 반복
-
CPU 실행 (CPU Burst)
- CPU를 사용하는 구간
- 실제 CPU를 사용한는 스케쥴링의 단위 -
입/출력 대기 (I/O Burst)
- I/O 작업이 끝날 때까지 Block되는 구간
스케쥴링 평가기준
-
CPU 이용률
- 전체 시간 중, CPU가 작업을 처리하는 시간의 비율
-
처리량
- CPU가 단위 시간 당 처리하는 프로세스 개수
-
총 처리 시간
- 프로세스의 시작부터 끝까지의 시간
-
대기시간
- 프로세스가 준비완료 큐에서 대기하는 시간의 합
-
응답시간
- 요청 후 첫 응답이 오기까지 걸린 시간
스케쥴링 종류
- 선점 스케쥴링 (Preemptive Scheduling)
- 비선점 스케쥴링 (Non-Preemptive Scheduling)
선점 스케쥴링
OS가 나서서 CPU 사용권을 선점하고, 특정 요건에 따라 각 프로세스의 요청이 있을 때 프로세스에게 분배하는 방식
- 가장 자원이 필요한 프로세스에게 CPU를 분배, 강제로 회수도 가능
- 빠른 응답시간을 요구하는 대화식 시분할 시스템에 적합
- 긴급한 프로세스 제어 가능
- 우선순위 스케쥴링 (Priority)
미리 주어진 프로세스의 우선순위에 따라서 스케쥴링
- 기아(Starvation) : 우선순위가 낮은 프로세스는 할당되지 않는 경우
- 해결법
- 노화(Aging) : 기다리는 시간에 따라 우선순위를 증가
-
라운드 로빈 (Round Robin)
정해진 시간 할당량 만큼 프로레스를 할당한 뒤, 작업이 끝난 프로세스는 준비완료 큐(순환 큐)의 가장 마지막에 재할당
-> 형제간 컴퓨터를 사용할 때 몇 시간을 하고 싶어도 정해진 시간(1시간)만 하고 돌아가면서 하는 것
-
다단계 큐 (Multilevel-Queue)
준비완료 큐를 여러 개의 큐로 분류하여 각 큐가 다른 스케쥴링을 가지는 방식
큐와 큐 사이에도 스케쥴링이 필요forground, background queue가 있을 때 foreground가 비어있지 않는 한 background는 먼저 실행될 수 없고, background가 실행 중이라도 forground에 프로세스가 들어오면 선점된다.
비선점 스케쥴링
프로세스가 CPU를 할당받으면 프로세스가 종료되거나, 입출력 요구가 발생하여 자발적으로 중지될 때 까지 계속 실행되도록 보장
- FCFS (First Come, First Serve)
먼저 도착한 프로세스를 먼저 처리하는 스케쥴링
- 호위효과(Convoy Effect) : 긴 처리시간의 프로세스가 선점되면 나머지 프로세스는 끝날 때까지 대기
- 먼저 도착한 프로세스의 버스트 타임에 따라 평균 대기시간의 편차가 큼
- SJF (Shorted Job First)
CPU Burst Time이 가장 짧은, 최단 작업을 우선 스케쥴링
- 가장 적은 평균 대기 시간 달성 가능
- CPU Burst Time이 동일하다면 FCFS (선점형)
- 비선점일 경우 최소 잔여시간 우선법칙을 따름
-> CPU에 할당된 프로세스의 잔여시간과 새로 들어온 프로세스의 CPU Burst Time을 비교하여 더 적을 프로세스에게 할당
-
HRN (Highest Response-ratio Next)
우선순위를 계산하여 점유 불평등을 보완 (SJF 단점을 보완)
우선순위 = (대기시간 + 실행시간) / 실행시간
프로세스 상태변화
- I/O or 이벤트 대기 : I/O 요청이 발생하거나, 자식 프로세스가 종료 대기 할 때
- exit : 프로세스를 종료시킬 때
- interrupt : 인터럽트가 발생했을 때
- I/O or 이벤트 완료 : I/O가 완료될 때
선점 스케쥴링: 프로세스에서 CPU를 강제로 할당, 회수
비선점 스케쥴링: 프로세스가 스스로 CPU를 반환
