정의
프로세스가 구동하기 위해서 다양한 시스템자원 (ex..CPU)이 필요한데, 최고의 성능을 내기 위해서는 이 자원들을 어떤 프로세스에 얼마나 할당할지가 매우 중요하다. 이를 결정짓는 것이 CPU 스케줄링이다.
목적
- CPU 사용률, 처리량 최대화
- 반환시간, 대기시간, 응답시간, 오버헤드, 기아현상 최소화
기아현상?
특정 프로세스의 우선순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태.
이를 해결하기 위해서aging기법,PriorityQueue대신 FIFO기반 Queue사용등을 사용한다.
이를 표현한 단어들로
- Batch System : 가능하면 많은 일을 수행하는 것 . 처리량(thoroughout)이 중요
- Interactive System : 빠른응답시간, 적은 대기시간
- Real-time System : 기한(deadline)맞추기
프로세스 상태
프로세스 상태는 다음과 같은 형태를 띈다.
프로세스 상태 표
| 프로세스 상태 | 설명 |
|---|---|
| 생성 상태 | 프로세스가 생성된 상태 |
| 준비 상태 | CPU를 할당받을 수 있는 상태 각각 우선순위를 부여하여 가장 높은 것이 다음 순서에 CPU를 항당 받음 |
| 실행 상태 | CPU를 할당받아 동작 중인 상태 |
| 대기 상태 | 프로세스 실행 중 입출력 등으로 인해 CPU를 반환하고 대기하는 상태 우선순위 x |
| 완료 상태 | 프로세스가 CPU를 할당받아 주어진 시간내에 완전히 수행 완료한 상태 |
프로세스 상태전이 표
| 프로세스 상태전이 | 설명 |
|---|---|
| 디스패치 | 준비상태에 있는 프로세스 중 실행될 프로세스를 선정(Scheduling)하여 CPU를 할당(Context Switching 발생) |
| 타이머 런아웃 | 프로세스는 지정된 시간을 초과하면 스케줄러에 의해 PCB를 저장하고, CPU를 반환 후 다시 준비상태로 간다 |
| 웨이크업 | 어느순간에 입출력이 종료되면 대기 상태 프로세스에게 입출력 종료 사실을 알리고 준비상태로 전이 |
CPU 스케줄링 종류
선정형 스케줄링
1. Priority Scheduling
- 우선순위가 높은 순서대로 처리
- 기아현상 발생할 수 있음 -> Aging방법으로 해결 가능
2. Round Robin
- 각 프로세스에게 동일한 시간만큼 CPU할당
할당시간(Time Quantum)이 작으면 , Context Swtiching이 잦아져 오버헤드 증가한다.
3. Multilevel-Queue(다단계 큐)
- 작업들을 여러 종류의 그룹으로 나누어 여러개의 큐를 이용하여 상위 단계 작업이 선점
- 각 큐는 자신만의
독자적인 스케줄링을 가짐
4.Multilevel-Feedback-Queue(다단계 피드백 큐)⭐️
- 다단계 큐의 단점 보완,,, FCFS + Round Robin
- 현대 CPU 스케줄링 기법 중 가장 일반적인 알고리즘인 동시에, 가장 복잡.
- 새로운 프로세스는 높은 우선순위를 가지다가 실행시간이 지날수록 점점 낮은 우선순위 큐로 이동한다.
우선순위가 높으면시간할당량(Time Quantum)이 작게, 낮으면 크게 - 다단계 큐는 큐사이에 프로세스 이동이 가능해 유연성이 좋을 뿐만 아니라, 에이징 기법을 통해 기아 현상을 예방할 수도 있다.
비선점형 스케줄링
1. FCFS (First Come, First Service)
- 큐에 도착한 순서대로 CPU 할당
- 실행 시간이 짧은 게 뒤로가면 평균 대기 시간이 길어지는 단점
2. SJF (Shortest Job First)
- 수행시간이 가장 짧은 작업 먼저 수행
- 수행시간이 긴 프로세는 기아현상에 발생할 수 있다.
3. HRN (Highest Response-ratio Next)
- 우선순위를 계산하여 SJF의 기아현상 보완한 기법
- 우선순위 = (대기시간 + 실행시간) / 실행시간
CPU 스케줄링 척도
- CPU 이용률
- Throughout(처리율) : 단위시간 당 처리하는 작업의 수 (처리량)
- Turnaround time (반환시간) :
(종료시간 - 도착시간), 짧을수록 좋다 - Waiting Time (대기시간) : ready queue에서 기다린 시간 ,
(반환시간 - 서비스시간) - Response Time (응답시간) : 작업이 처음 실행되기까지 걸린 시간
ㅋ