“CPU라는 한정적인 자원을 어떻게 하면 최대한 잘 쓸 수 있을까?” 라는 목표를 가지고 프로세스를 잘 배정하기

1. 가능하면 많은 일을 수행
2. 빠른 응답시간, 적은 대기 시간
3. 기아현상 최소화

프로세스 상태

1. New: 새로 생긴 프로세스
2. Ready: CPU 배정 가능
3. Waiting: “Running” 단계에서 이벤트, I/O 처리해야 하는 경우
4. Running: CPU에 배정받아 실행 중
5. Terminated: 프로세스 실행 완료

new, terminated는 제외하고 나머지 세 단계가 헷갈리곤 한다. 특히나 ready, waiting.

일단 new 상태에서 승인되면 ready 상태가 된다. 여기서 스케줄러가 해당 프로세스를 CPU에 올리면 running 상태가 된다. 이때 만약 입출력이나 이벤트가 발생한다면? waiting 상태로 들어간다. 해당 요청을 다 처리하고 나면 다시 ready 상태로 넘어간다. 그럼 ready 상태의 프로세스들 중 하나를 골라 또 running 상태로 넘어간다. 그럼 입출력이나 이벤트 외에 예외가 발생했다면 어떻게 할까? 또 하나의 프로세스가 실행시간이 너무 길 경우도 대비해야하지 않을까? 위와 같은 경우에는 running 상태에서 바로 ready 상태로 넘어가게 된다. 특히 후자의 경우 스케줄러가 timer를 설정하여 할당된 시간동안만 CPU를 점유하도록 하고 시간이 완료되면 interrupt를 발생시켜 운영체제에게 프로세스 제어권을 부여한다. 그리고 뺏는다.

쉽게 설명하면 ready → running이 기본이고, 입출력이나 이벤트 발생하면 running → waiting, 예외적으로 실행 중인 프로세스를 내려야하는 경우에 running → ready로 바로 간다.

선점/비선점 Scheduling

CPU라는 한정적인 자원위에서 프로세스를 효율적으로 실행시키려면 스케줄링이 중요하다. 어떤 프로세스를 먼저 실행시키는 것이 좋을지 고민해야한다는 뜻이다. 이러한 CPU 스케줄링에는 아래와 같이 크게 두 종류가 있고 그 안에서도 알고리즘에 따라 여러 종류로 나뉜다.

• 선점: 뺏기 가능 (OS가 CPU 사용관 선점할 수 있어서 강제 회수하는 경우)
• 비선점: 뺏기 불가능 (프로세스 종료, I/O와 같은 이벤트 전까지 실행 보장함)

선점 스케줄링

• FCFS(First Come First Served)
  • 큐에 도착한 순서대로 CPU 할당
  • 실행 시간이 짧은 프로세스가 나중에 도착해버리면 평균 대기시간 up
• SJF(Shortest Job First)
  • 수행시간이 짧은 순으로 CPU 할당
• HRN (Hightest Response-ratio Next)
  • 우선순위 계산하여 SJF 단점 보완
  • 우선순위 = (대기시간+실행시간)/(실행시간)

비선점 스케줄링

• Priority Scheduling
  • 우선순위를 부여해서 우선순위 높은 순서대로 처리
  • 우선순위가 낮은 프로세스가 무한정 기다리는 아사현상 발생 가능
  • Aging 기법으로 위 문제 해결 가능 (기다리는만큼 우선순위 높여주기)
• SRTF(Shortest Remaining Time First)
  • 현재 수행 중인 프로세스의 남은 시간보다 더 짧은 실행시간이 남은 프로세스가 ready queue에 도착하면 뺏어서 준다.
• Round Robin
  • 기본은 FCFS이고 각 프로세스가 동일한 크기의 할당 시간을 가짐
  • 할당 시간만큼 타이머 걸어놓고 시간 지나면 ready상태로 변경
  • 프로세스의 context (어디까지 실행했는지 등) 저장 가능해서 가능한 방법
  • Response time이 빨라짐
• Multilevel Queue
  • 여러개의 ready 큐를 두고 각 큐마다 할당시간 다르게 설정함
  • 우선순위가 높은 작업(사용자 interaction 등을 다루는 작업)을 넣는 큐와, 우선순위가 낮은 작업(batch 작업 등)을 넣는 큐를 나눔
  • 큐 별로 스케줄링 알고리즘을 다르게 지정해서 우선순위 높은 것이 대체로 먼저 실행되지만, 아사는 발생하지 않도록 설계
• Multilevel-Feedback-Queue
  • 보통 사용자 interactive하지 않은 프로세스는 CPU burst가 큰편 (비례관계 있음)
  • 그렇다면 할당시간(time quantum)을 다 채운 프로세스는 CPU burst process(중요하지 않은 background이면서 CPU 실행 시간 긴 프로세스)일 가능성이 높음
  • 그럼 위와 같은 프로세스를 할당시간이 더 긴 큐로 내림
  • 계속 내리다가 결국 FCFS로 실행시킴

잘 읽었다면 다음 문제를 풀어보세요~!

각 프로세스에 일정시간을 할당하고, 할당된 시간이 지나면 그 프로세스는 잠시 보류한 뒤 다른 프로세스에게 기회를 주고, 또 그 다음 프로세스에게 하는 식으로, 돌아가며 기회를 부여하는 알고리즘을 OOOOO 알고리즘이라고합니다. 이 때, OOOOO에 들어갈 말으로 알맞은 말은 무엇인가요?

정답은 CS Broker - CPU 스케줄링에서 확인~!~!

출처

• https://gyoogle.dev/blog/computer-science/operating-system/CPU%20Scheduling.html
• https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/OS#cpu-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%9F%AC
• https://jhnyang.tistory.com/entry/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-OS-multilevel-feedback-queue%EB%8B%A4%EB%8B%A8%EA%B3%84-%ED%94%BC%EB%93%9C%EB%B0%B1-%ED%81%90-MLFQ-%ED%8A%B9%EC%A7%95-%EB%AC%B8%EC%A0%9C%EC%A0%90