(Dispatch)
제출(submit) →→ 접수(Hold) →→ 준비(Ready) ↔↔ 실행(Run) →→ 완료(Complete)
↓ ↖ ↙
(spooling)↓ 입출력종료 ↖ ↙입출력 발생
↓ (wake up) ↖ ↙
디스크 대기(wait, Block)
* 제출 : 작업을 처리하기 위해 사용자가 작업을 시스템에 제출한 상태
* 접수 : 제출된 작업이 스풀 공간인 디스크의 할당 위치에 저장된 상태
* 준비 - 프로세스가 프로세서를 할당받기 위해 기다리고 있는상태
- 프로세스는 준비상태 큐에서 실행을 준비하고 있다.
- 접수 상태에서 준비 상태로의 전이는 Job 스케줄러에 의해 수행된다.
- 준비 리스트에 있는 프로세스는 각각 우선순위가 주어진다.
* 실행 - 준비상태 큐에 있는 프로세스가 프로세서를 항당받아 살행되는 상태
- 실행중인 프로세스에 입출력 처리가 필요하면 실행중인 프로세스는 대기 상태로 전이된다.
- 프로세스 수행이 완료되기 전에 프로세스에게 주어진 할당 시간이 종료되면 프로세스는 준비 상태로 전이된다.
* 대기, 보류, 플록
- 프로세스에 입출력 처리가 필요하면 현재 실행 중인 프로세스가 중단되고, 입출력 처리가 완료될 때까지 대기하고 잇는 상태
- 대기 리스트에 있는 프로세스는 우선순위가 주어지지 않는다.
* 완료 - 프로세서를 할당받아 주어진 시간 안에 수행을 완료한 상태
- 스케줄링(Scheduling)
* 프로세스가 생성되어 실행될 때 필요한 시스템의 여러 자원을 해당 프로세스에게 할당하는 작업을 의미한다.
* 목적 : CPU나 자원을 효율적으로 사용하기 위한 정책
- 비선점 스케줄링(Non-Preemptive)
* 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할수 없는 기법
* 한번 CPU를 할당 받으면 작업이 완료될때 까지 CPU를 사용
->문제점 : 짧은 작업(중요한 작업)이 긴 작업(중요하지 않은 작업)을 기다리는 경우 발생
* 종류 : FCFS(FIFO), SJF, 우선순위, HRN, 기한부(Deadline)
- 선점 스케줄링(Preemptive)
* 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 기법
* 빠른 응답 시간을 요구하는 대화식 시분할 시스템(Time Sharing System)에 사용
* 많은 오버헤드 초래
* 인터럽트용 타이머 클럭 필요( 프로세스가 자원을 독점하는것을 방지)
* 종류 : RR(Round Robin, SRT, 선점 우선순위, 다단계 큐(MQ), 다단계 피드백큐(MFQ)
- 비선점 스케줄링 종류
* FCFS(First Come First Service, 선입 선출)
- 준비 상태 큐에 도착한 순서에 따라 차례로 CPU를 할당하는 기법
* SJF(Shortest Job First, 단기작업 우선)
- 실행 시간이 가장 짧은 프로세스에게 먼저 CPU할당
- 평균 대기시간이 가장 적은 알고리즘
- 실행시간이 긴 프로세스가 순위기 밀려 무한 연기상태가 발생될 수 있다.
* HRN(Highest Response-ratio Next)
- 실행시간이 긴 프로세스가 불리한 SJF기법 보완
- 우선순위 공식을 이요하여 실행시간이 짧은 프로세스나 대시 시간이 긴 프로세스에게 우선순위를 줌
- 우선순위를 계산하여 술자가 높은것부터 우선순위가 부여됨
- 우선순위 계산식 = (대기시간+실행시간)/실행시간
* 기한부(Deadline)
- 일정시간동안 프로세스 완료하는 기법
- 제한된 시간 안에 완료되지 않을 경우 제거 되거나 처음부터 다시 실행해야함
- 여러 프로세스들이 동시에 실행되면 스케줄링이 복잡해지며, 프로세스 실행 시 집중적으로 요구되는
자원관리에 오버헤드가 발생한다.
* 우선순위(Priority)
- 프로세스마다 우선순위 부여
- 우선순위가 동일한경우 FCFS 기법으로 할당
- 가장 낮은 순위를 부여받은 프로세스는 무한 연기 또는 기아상태가 발생할 수 있다.
- 선점 스케줄링 종류
* Round Robin
- 시분할 시스템을 위해 고안된 방식, FCFS 기법 변형
- 각 프로세스는 시간 할당량 동안만 실행한 후 완료되지 않으면 다음 프로세스에게 CPU를 넘겨주고
준비상태 큐의 가장 뒤로 배치
- 할당된 시간이 클수록 FCFS와 같다.
- 시간이 작을 수록 문맥교환과 오버헤드가 자주 발생
* SRT(Shortest Remaining Time)
- SJF 기법을 변형, 선점 SJF라고도 한다.
- 실행중인 프로세스의 남은 시간과 준비상태 큐에 새로 도착한 프로세스의 실행 시간을 비교하여 짧은
실행 시간을 요구하는 프로세스에게 CPU를 할당.
- 준비상태 큐에 있는 프로세스의 실행 기간 추적으로 오버헤드 증가
* 다단계 큐
- 프로세스를 특정 그룹으로 분류할 수 있을 경우 그룹에 따라 각기 다른 준비단계 큐 사용
- 시스템, 대화형, 편집, 일괄처리 프로세스 등으로 분류
- 준비상태 큐 마다 다른 스케줄링 기법 사용가능
- 다른 준비상태 큐로 이동 불가
- 하위단계 준비 큐에 있는 프로세스를 실행하는 도중이라도 상위 단계 준비상태 큐에 프로세스가 들어오면
상위단계 프로세스에게 CPU를 할당
* 다단계 피드백 큐
- 다단계 큐 기법 개선하여 다른 준비상태 큐로 이동 가능
- 각 큐마다 시간 할당량부여 시간동안 완료 되지 못한 프로세스는 다음 단계 큐로 이동
- 마지막 단계 큐에서는 RR스케줄링으로 할당
* Dispatch : 준비 상태에서 대기하고 있는 프로세스 중 하나가 프로세서를 할당받아 실행 상태로 전이되는 과정
* 실행 시간 = 서비스 시간 = 버스트 시간
* 에이징(Aging)기법 : 대기 시간 등에 따라 우선순위를 높여주는 것을 의미