[OS/운영체제] CPU 스케줄링과 프로세스 상태, 상태 전이

1. CPU 스케줄링이란?

정의

CPU를 잘 사용하기 위해 프로세스를 잘 배정하는 것

목적

• 처리율과 CPU 이용률 ↑
• 오버헤드, 응답시간, 반환시간, 대기시간, 기아 현상 ↓

2. CPU 스케줄링의 종류

선점/비선점 스케줄링이란?

• 선점 스케줄링: 하나의 프로세스가 CPU를 차지하고 있을 때, 우선순위가 높은 다른 프로세스가 현재 프로세스를 중단시키고 CPU를 점유하는 스케줄링 방식 (I/O or Event wait)

• 비선점 스케줄링: 한 프로세스가 CPU를 할당받으면 작업 종료 후 CPU 반환 시까지 다른 프로세스는 CPU 점유가 불가능한 스케줄링 방식 (Interrupt, Scheduler Dispatch)

선점 스케줄링의 종류

• 선점 스케줄링
  • RR (Round Robin)
    • 비선점인 FCFS 알고리즘을 선점 형태로 변형한 기법
    • 할당된 시간 동안만 실행한 후, 실행이 완료되지 않으면 다음 프로세스에게 CPU를 넘겨주고 큐의 가장 뒤로 배치됨
    • 할당 시간이 크면 FCFS와 같게 되고, 작으면 문맥 교환(Context Switching) 잦아져서 오버헤드 증가
  • SRT (Shortest Remaining Time)
    • 비선점인 SJF 알고리즘을 선점 형태로 변경한 기법
    • 남은 실행 시간이 가장 짧은 프로세스가 먼저 수행
  • 다단계 큐 (Multi Level Queue)
    • 프로세스들을 여러 종류의 그룹으로 나누어 여러 개의 큐를 이용하는 기법
      
  • 다단계 피드백 큐 (Multi Level Feedback Queue)
    • 다단계 큐의 단점을 보완한 것으로, 큐마다 time out을 설정하여 시간 초과 시 우선순위가 낮은 다음 단계 큐로 이동하는 기법
      

비선점 스케줄링의 종류

• FCFS (First Come First Served)
  • 큐에 도착한 순서대로 CPU 할당
  • 실행 시간이 짧은 게 뒤로 가면 평균 대기 시간이 길어짐
• SJF (Shortest Job First)
  • 도착하는 시점에 따라 수행 시간이 가장 짧은 프로세스가 먼저 수행
  • FCFS 보다 평균 대기 시간 감소, 짧은 작업에 유리
  • But, 기아 현상 발생 가능
• HRN (Hightest Response-ratio Next)
  • 우선순위를 계산하여 기아 현상을 보완한 방법 (SJF의 단점 보완)
  • 우선순위 = (대기시간 + 실행 시간) / (실행 시간)

💡 현재 컴퓨터 시스템이 사용하는 방법은 '우선순위 + 라운드 로빈' 방식이다!

3. 프로세스 상태

상태 (Status)

• New: 프로세스 생성 중
  프로세스를 생성하고 있는 단계로, 커널 공간에 PCB가 만들어진 상태이다.

• Ready: 프로세스가 CPU를 기다리는 상태
  프로세스가 메모리에 적재된 상태로, 실행하는데 필요한 자원을 모두 얻은 상태이다.

• Running: 프로세스가 CPU를 할당받아 명령어를 수행 중인 상태
  일반적으로 CPU가 하나이기 때문에 여러 프로세스가 동시에 실행되어도 실제로 실행 중인 프로세스는 매 시점 하나뿐이다.

• Waiting: 프로세스가 어떤 사건(event)이 완료되기를 기다리는 상태
  프로세스가 실행되다가 할당받은 CPU를 반납하고 특별한 event가 완료되길 기다린다. (ex. I/O 작업)

• Terminated: 프로세스의 실행 종료
  프로세스의 실행이 완료되고 할당된 CPU를 반납한다.

프로세스 상태 전이

• 승인 (Admitted) : 프로세스 생성이 가능하여 승인받는 것

• 스케줄러 디스패치 (Scheduler Dispatch) : 준비 상태에 있는 프로세스 중 하나를 선택하여 실행시키는 것

• 인터럽트 (Interrupt) : 예외, 입출력, 이벤트 등이 발생하여 현재 실행 중인 프로세스를 Ready 상태로 바꾸고, 해당 작업을 먼저 처리하는 것

• 입출력 또는 이벤트 대기 (I/O or Event wait) : 실행 중인 프로세스가 입출력이나 이벤트를 처리해야 하는 경우, 입출력/이벤트가 모두 끝날 때까지 Waiting 상태로 만드는 것

• 입출력 또는 이벤트 완료 (I/O or Event Completion) : 입출력/이벤트가 끝난 프로세스를 준비 상태로 전환하여 스케줄러에 의해 선택될 수 있도록 만드는 것

출처

https://github.com/haewon-park/csStudy/blob/main/OS/CPU%20%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81.md