CPU Scheduling
컴퓨터 시스템의 자원을 효율적으로 사용하고 시스템 성능을 최적화하기 위해 운영체제가 여러 프로세스 중 어떤 프로세스를 CPU에 할당할 것인지 결정하는 작업
선점 / 비선점 스케줄링
- 선점형(preemptive) 스케줄링: 운영체제가 현재 실행 중인 프로세스를 중단시키고, 다른 프로세스에게 CPU를 할당할 수 있다.
- 비선점형(nonpreemptive) 스케줄링: 한 번 CPU가 어떤 프로세스에게 할당되면 그 프로세스가 종료되거나 대기 상태(waiting state)에 들어갈 때까지 CPU를 회수하지 않는다.
프로세스 상태
- New: 프로세스가 생성되어 시스템에 등록되는 단계입니다.
- Ready: CPU를 사용할 준비가 된 상태입니다. 이 상태의 프로세스들은 대기 큐에서 CPU 할당을 기다립니다.
- Running: CPU를 할당받아 명령어들이 실행되고 있는 상태입니다.
- Waiting: 특정 이벤트(예: I/O 작업 완료)나 조건을 기다리는 상태입니다. 이 때, CPU는 다른 프로세스에게 할당될 수 있습니다.
- Terminated]: 작업이 완료되거나, 어떤 이유로 종료된 후의 상태입니다.
ready Vs Waiting
- ready: 실행 준비가 모두 완료 된 상태에서 기다리는 것
- waiting: I/O, 다른 event가 발생하기를 기다리는 것 -> I/O, 다른 event가 발생했다면 ready 상태가 됨
- 승인 (Admitted): 새로운 프로세스가 생성되어 시스템에 등록됩니다. 이는 '새로운(New)' 상태의 시작을 의미하며, 프로세스가 메모리에 로드되어 실행을 위한 준비를 완료하게 됩니다.
- Scheduler Dispatch: 운영체제의 스케줄러가 '대기중인(Ready)' 상태의 프로세스 중 하나를 선택하여 CPU를 할당합니다. 이때 해당 프로세스는 '실행 중인(Running)' 상태가 됩니다.
- Interrupt: 현재 실행 중인 프로세스가 예외 처리, 입출력 작업, 또는 특정 이벤트 처리 등으로 인해 일시 중단됩니다. 이 경우, 해당 프로세스는 '대기하는(Waiting)' 상태가 되며 CPU는 다른 준비된 프로세스에게 할당될 수 있습니다.
- I/O or Event wait: 실행 중인 프로세스가 입출력 작업이나 특정 이벤트 처리를 필요로 할 때입니다. 해당 작업이나 이벤트 완료까지 해당 프로세서는 '대기하는(Waiting)' 상태에 머무릅니다.
- I/O or Event Completion: 입출력이나 특정 이벤트 처리가 완료되면, 해당 작업을 대기하고 있던 프ロ세서는 다시 '대기중인(Ready)' 상태가 되어 CPU 할당을 기다립니다.
비선점형(nonpreemptive) 스케줄링
- FCFS (First Come First Served):
- 큐에 도착한 순서대로 CPU 할당
- 실행 시간이 짧은 프로세스가 큐 뒤쪽에 있다면 평균 대기 시간 길어짐
- SJF (Shortest Job first)
- 수행시간이 짧은 프로세스부터 우선 실행
- FCFS 보다 평균대기 시간 짧다.
- HRN (Highest Response Ratio Next)
- 우선 순위를 계산하여 점유 불평등(SJF 의 단점)을 보완한 방법
- 우선순위 = (대기시간 + 실행시간) / (실행시간)
선점형(preemptive) 스케줄링
- Priority Scheduling:
- 정적/동적으로 우선순위를 부여하여 우선순위 높은 순서대로 처리
- 각 프로세스는 우선순위를 부여받으며, CPU는 가장 높은 우선순위를 가진 프로세스에게 할당됩니다. 만약 새롭게 들어온 프로세스의 우선순위가 현재 실행 중인 프로세스보다 높으면, 현재 실행 중인 작업을 중단하고 새롭게 들어온 작업을 시작합니다.
- Round Robin:
- 각 프로세스는 동일한 크기의 할당 시간(time quantum 또는 time slice)을 가지며, 그 시간이 지나면 CPU는 다음 프로세스에게 넘어갑니다. (FCFS에 의해 프로세스들이 보내지면)
- Multilevel-Queue:
- 여러 개의 대기열이 있으며, 각 대기열마다 다른 스케줄링 알고리즘이 사용됩니다. 예를 들어, 하나의 대기열은 RR 알고리즘을 사용하고 다른 대기열은 FCFS 알고리즘이 사용되는 등입니다.
- Multilevel-Feedback-Queue: 프로세서가 서비스 받지 못하는 상황에서 그들이 어떻게 반응하는지 기반으로 큐 사이에서 이동할 수 있습니다.
CPU 스케줄링 척도
- Response Time: 작업이 처음 실행되기까지 걸린 시간
- Turnaround Time: 실행시간과 대기시간을 모두 합한 시간 (작업이 완료될 때까지 걸린 시간)
