프로세스 우선순위

• 입출력 작업이 많은 프로세스의 우선순위는 CPU 작업이 많은 프로세스의 우선순위보다 높다.
  • 입출력 작업이 많은 입출력 집중 프로세스는 대기 상태에 많이 머물기 때문에 CPU 자원을 사용하는 빈도가 낮기 때문에 우선순위를 높이면 입출력 장치를 끊임없이 작동시킬 수 있다.

스케줄링 큐

• 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것

• CPU를 사용할 다음 프로세스를 찾기 위해 모든 프로세스의 PCB를 확인하는 것은 비효율적이기 때문에 각 자원을 사용하고 싶어하는 프로세스들을 줄을 세워서 관리한다. 이 줄을 스케줄링 큐라고 부른다.

Ready Queue

• CPU를 이용하고 싶은 프로세스들이 서는 줄

대기 큐

• 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄

선점형과 비선점형 스케줄링

• CPU가 점유되어 있는 상황에서 처리가 급한 프로세스가 나타나면 이에 대한 처리 방식은 선점형과 비선점형 스케줄링으로 나뉜다

Preemptive Scheduling(선점형 스케줄링)

• 적극적, 강제적, 빠른 응답성, 데이터 일관성 문제
• 급한 프로세스가 CPU를 이용할 수 있도록 하는 스케줄링
• 정해진 시간만큼 프로세스가 CPU를 점유할 수 있도록 하고 정해진 시간을 모두 소비하면 인터럽트를 발생시켜 다른 프로세스가 CPU를 점유할 수 있도록 한다.
• 프로세스의 자원 독점을 막을 수 있지만 문맥 교환이 자주 발생하여 이에 대한 오버헤드가 발생한다.
• 한 프로세스가 공유 자원(critical section)에 접근하여 편집하다가 context switching에 진입했을 때 cpu를 점유한 다른 프로세스가 편집 중인 공유 자원에 접근하여 편집하면 데이터 일관성에 문제가 생길 수 있다.

Nonpreemptive Scheduling(비선점형 스케줄링)

• 신사적, 협력적(Cooperative), 느린 응답성
• CPU를 점유한 프로세스가 스스로 대기상태에 진입하거나 종료되기 전까지 다른 프로세스가 CPU를 사용할 수 없도록 하는 스케줄링

협력적인 이유
다른 프로세스가 CPU를 사용하도록 스스로 대기상태에 진입하는 경우 → 프로그램 레벨에서 서로 협력해야 번갈아가면서 CPU를 사용하는 것이 가능하기 때문

CPU 스케줄링 알고리즘

스케줄링 알고리즘의 종류

선입 선처리 스케줄링, FCFS(first-come, first-served)

• 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링
• 먼저 CPU를 요청한 프로세스부터 CPU 할당
• 프로세스들이 기다리는 시간이 매우 길어질 수 있다(=호위 효과)
  • 앞의 프로세스의 실행시간이 길수록 후순위의 프로세스의 실행시간이 길어진다.

최단 작업 우선 스케줄링, SJF(shortest-job-first)

• 호위 효과를 방지하기 위해 CPU 사용이 긴 프로세스는 나중에 실행하는 스케줄링

라운드 로빈 스케줄링, RR(round-robin)

• 선입 선처리 스케줄링 + 타임 슬라이스
• 타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
• 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링
  • 큐에 삽입된 프로세스들은 순서대로 CPU를 이용하되 정해진 만큼만 이용
  • 정해진 시간을 모두 사용하고 나서도 프로세스가 완료되지 않으면 큐의 맨 뒤에 삽입
• 타임 슬라이스의 크기가 중요하다
  • 너무 커지면 선입 선처리 스케줄링과 같아진다.
  • 너무 작으면 Context Switching으로 인한 Overhead가 너무 커진다.

최소 잔여 시간 우선 스케줄링, SRTF(shortest-remaining-time-first)

• 최단 작업 우선 스케줄링 + 라운디 로빈 스케줄링
• 정해진 시간만큼 CPU를 이용하면서 다음으로 CPU를 사용할 프로세스는 남은 작업시간이 가장 적은 프로세스 선택

우선순위 스케줄링, Priority

• 프로세스들에 우선순위를 부여하고, 우선순위 높은 프로세스부터 실행
• 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링

기아 현상
우선 순위가 높은 프로세스만 계속 실행되어 우선 순위가 낮은 프로세스는 계속 후순위로 밀려 실행되지 못하는 현상

에이징
기아 현상을 방지하기 위해 오랫동안 대기한 프로세스의 우선 순위를 점차 높여서 실행될 수 있도록 하는 기법

다단계 큐 스케줄링, Multilevel queue

• 우선순위 스케줄링의 발전된 형태
• 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식
  • 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리
  • 우선순위가 가장 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스 처리
• 큐 간의 이동이 불가능하기 때문에 기아 현상이 다시 발생할 수 있다.

다단계 피드백 큐 스케줄링

• 큐 간의 이동이 가능한 다단계 큐 스케줄링

1. 새롭게 준비 상태가 된 프로세스를 가장 높은 우선순위 큐에 삽입한다.
   
2. 일정 시간(타임 슬라이스) 프로세스를 실행하고 해당 큐에서 실행이 완료되지 않으면 다음 우선순위 큐에 삽입한다.
   즉, CPU를 비교적 오래 사용하는 CPU 집중 프로세스들은 점점 우선 순위가 낮은 큐에 삽입된다.
3. 이렇게 낮은 우선 순위로 밀려나는 프로세스들은 다시 에이징 기법을 적용하여 높은 우선순위 큐로 이동하게 하여 기아 현상을 방지할 수 있다.

참고자료

CPU 스케줄러는 프로세스를 어떻게 스케줄링 하는 걸까요? 선점/비선점의 차이는 뭘까요? 디스패처는 또 뭐죠? 이 모든 궁금증을 이 영상으로 간결하게 해결하세요!