#6 운영체제 스케줄링 알고리즘 | 선점형과 비선점형

결정 시점

CPU 스케줄링의 결정 시점은 다음과 같은 프로세스의 상태 변화가 있을 때이다.


1. 수행 → 대기
2. 수행 → 준비
3. 대기 → 준비
4. 수행 → 종료

스케줄링 적용 시점에 따라 비선점형과 선점형의 2가지로 구분할 수 있다. 비선점형은 위의 결정 시점 중 1번과 4번의 상황에서만 수행되며, 선점형은 1번에서 4번까지 모든 상황에서 수행된다.

비선점형 스케줄링(Non-preemptive Scheduling) : 어떤 프로세스가 CPU를 할당 받으면 그 프로세스가 종료되거나 입출력 요구가 발생하여 자발적으로 중지될 때까지 계속 실행되도록 보장한다. 순서대로 처리되는 공정성이 있고 다음에 처리해야 할 프로세스와 관계없이 응답 시간을 예상할 수 있으며 선점 방식보다 스케줄러 호출 빈도가 낮고 문맥 교환에 의한 오버헤드가 적다. 일괄 처리 시스템에 적합하며, CPU 사용 시간이 긴 하나의 프로세스가 CPU 사용 시간이 짧은 여러 프로세스를 오랫동안 대기시킬 수 있으므로, 처리율이 떨어질 수 있다는 단점이 있다.

선점형 스케줄링(Preemptive Scheduling) : 어떤 프로세스가 CPU를 할당받아 실행 중에 있어도 다른 프로세스가 실행 중인 프로세스를 중지하고 CPU를 강제로 점유할 수 있다. 모든 프로세스에게 CPU 사용 시간을 동일하게 부여할 수 있다. 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합하며 긴급한 프로세서를 제어할 수 있다. 운영 체제가 프로세서 자원을 선점하고 있다가 각 프로세스의 요청이 있을 때 특정 요건들을 기준으로 자원을 배분하는 방식이다.
출처 : 위키백과

사실 선점형과 비선점형의 차이는 위의 내용이 전부라고 할 수 있다. 앞의 포스팅 내용을 대부분 이해했다면 이러한 결과가 당연하다고 생각되기 때문에 복잡하게 생각할 필요도 없다.

선점형 스케줄러(Preemtive Scheduling)

• 하나의 프로세스가 다른 프로세스 대신에 프로세서(CPU)를 차지할 수 있다.

비선점형 스케줄러(Non-Preemtive Scheduling)

• 하나의 프로세스가 끝나지 않으면 다른 프로세스는 CPU를 사용할 수 없다.

시분할 시스템을 프로세스의 관점에서 보면?

시분할 시스템의 특징은 CPU에 있는 프로세스가 다른 작업(시스템 리소스 요청등)이 없더라도 해당 프로세스를 강제로 다른 프로세스로 바꿔서 실행합니다. 다시 말해 처음에 동작하던 프로세스는 계속 동작할 수 있음에도 불구하고 스케줄러에 의해 강제로 교체당하는 겁니다. 일정한 규칙 혹은 방법에 의해서 말이죠. 이러한 방법이 선점형 스케줄러라고 할 수 있습니다.

배치 처리 시스템을 프로세스의 관점에서 보면?

배치 처리 시스템의 특징은 CPU에 있는 프로세스가 다른 작업(시스템 리소스 요청등)이 없다면 계속해서 CPU에 점유해 있을 수 있습니다. 교체되는 시점은 점유해 있는 프로세스에 다른 작업이 생겼을때 혹은 종료되었을때를 제외하고는 없기 때문에 비선점형 스케줄러라고 할 수 있습니다.

스케줄러의 구분

FIFO(FCFS), SJF, Priority-based와 같은 스케줄러는 어떤 프로세스를 먼저 실행시킬지에 대한 알고리즘이고 Round Robin은 시분할 시스템을 위한 기본적인 선점형 스케줄러 알고리즘입니다.

앞에도 이야기 했지만 이러한 스케줄링 알고리즘을 구현할 때 중요한것은 목적이라고 할 수 있습니다. 그리고 고려해야하는 부분도 있는데 일괄 처리인가? 대화형인가? 혹은 우선 순위를 부여할것인가 아닌가, I/O 장치의 사용 비율은 어떤가? 어느정도로 프로세스를 선점해야 하는가 등 많인 고려사항이 있습니다.

비선점 프로세스 스케줄링

• FCFS 스케줄링(First Come First Served Scheduling)
• SJF 스케줄링(Shortest Job First Scheduling)
• HRRN 스케줄링(Highest Response Ratio Next Scheduling)

선점 프로세스 스케줄링

• RR 스케줄링(Round Robin Scheduling)
• SRTF 스케줄링(Shortest Remaining-Time First Scheduling)
• 다단계 큐 스케줄링(Multilevel Queue Scheduling)
• 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)
• RM 스케줄링(Rate Monotonic Scheduling)
• EDF 스케줄링(Earliest Deadline First Scheduling)

위와 같이 많은 스케줄링이 존재하는데 한 가지만 사용해서 만들어야 할 필요는 없습니다. 스케줄링은 하나의 프로그램이고 나의 사용목적에 맞게 필요한 여러가지 고려사항들을 조합해서 만들 수 있다는 말입니다.