스케줄링을 왜할까?
한정된 CPU 자원 내에서 멀티 프로세스 환경의 여러 프로세스를 효율적으로 실행시키기 위함입니다.
주어진 자원 내에서 최대한 효율적으로 자원을 활용하는 것이 당연한 부분입니다.
스케줄링(Scheduling) : 순서를 짠다, 일정 순서를 정합니다.
5가지 목적
- 공평성 : 모든 프로세스가 공평하게 실행되어야 합니다.
- 효율성 : 자원을 효율적으로 사용해야 합니다.
- 안정성 : 높은 우선순위의 프로세스를 먼저 처리하도록 합니다.
- 반응 시간 보장성 : 일정 시간 내에 응답할 수 있도록 스케줄링 해야 합니다.
- 무한 연기 방지 : 프로세스에 대한 처리가 무한히 연기되지 않도록 스케줄링 해야 합니다.
스케줄링은 어떤 단계를 갖고 있는가?
스케줄링은 장기 스케줄, 중기 스케줄, 단기 스케줄링이 있습니다.
장기 스케줄링(long-term scheduling)
디스크에 있는 작업 중 메모리로 올려 준비 큐에 넣을 프로세스를 선택하며, 메모리에 올라갈 프로세스의 수를 조절하여 시스템의 작업 부하를 관리합니다.
디스크의 작업 풀(Job Pool)에 있는 작업 중 일부를 메모리에 올려 준비 큐(Ready Queue)에 넣는 역할을 합니다.
하지만, 요즘 운영체제는 시분할 시스템을 사용하기 때문에 장기 스케줄링을 대부분 사용하지 않습니다.
시분할 시스템은 짧은 시간동안 다수의 프로세스가 CPU를 번갈아가며 사용하는 시스템입니다.
또한, 작업을 디스크에 대기 시키는 것이 아닌 메모리에 바로 올려서 실행합니다.
중기 스케줄링(mid-term scheduling)
프로세스 수를 동적으로 조절해서 메모리 사용을 관리합니다.
메모리가 부족하거나 과부하가 발생했을 때, 일부 프로세스를 스왑 아웃(Swap Out)을 통해 내보내고, 메모리에 공간이 생기면 스왑 인(Swap In)을 통해 다시 가져옵니다.
Swap Out : 프로세스를 메모리에서 디스크로 내보낸다.
Swap In : 프로세스를 디스크에서 메모리로 가져온다.
스왑 아웃(Swap Out)된 프로세스는 중단 상태가 됩니다.
중단 상태도 두 종류가 있습니다.
(1) 준비 상태에서 스왑 아웃된 중단된 준비 상태
준비 상태 : CPU 자원을 할당 받기 전의 상태를 의미합니다.
(2) 대기 상태에서 스왑 아웃된 중단된 대기 상태
대기 상태 : 프로세스가 I/O 작업을 기다리거나 특정 이벤트가 완료되기를 기다리는 상태를 의미합니다.
단기 스케줄링(short-term scheduling)
준비 큐에서 대기 상태인 프로세스중 다음으로 실행할 프로세스를 스케줄링 알고리즘으로 결정하는 역할을 합니다.
(1) 스케줄러가 스케줄링 알고리즘을 이용해 준비 큐에 있는 프로세스 중 하나를 선택해 CPU에 디스패치 합니다.
(2) CPU에서 프로세스를 실행합니다.
A : 프로세스 수행이 완료된 경우, 프로세스를 종료합니다.
B : 일정 시간을 초과하면 인터럽트가 발생해 프로세스가 준비 큐로 들어가고 준비 상태가 됩니다.
C : 입출력 요청이 들어오면 인터럽트가 발생해 대기 큐로 들어가 대기 상태가 됩니다. 입출력 완료시 준비 큐로 들어갑니다.
(3) fork()가 호출되면 자식 프로세스가 생성되고, 자식 프로세스는 준비 큐로 들어갑니다.
스왑 아웃(swap out) : 프로세스 실행시 메모리에 로드됩니다. 많은 프로세스가 메모리 공간에 로드되는 경우, 중기 스케줄러가 이벤트 발생을 기다리고 있는 프로세스를 저장 공간으로 옮겨 저장합니다.
스왑 인(swap in): 스왑 아웃한 프로세스가 특정 이벤트를 통해 활성화 될 필요가 있는 상황인 경우, 프로세스를 통째로 다시 메모리에 로드하는 것입니다.
스와핑(swapping): 메모리 부족 문제를 해결하기 위해 전체 프로세스의 메모리 내용을 디스크(스왑 공간)로 옮기는 작업입니다.
메모리에서 디스크로 데이터를 내보내는 작업과 디스크에서 다시 가져오는 작업 모두를 포함하는 포괄적인 개념입니다.
스케줄링은 어떤 알고리즘을 갖고 있는가?
스케줄링 알고리즘은 CPU스케줄러(단기 스케줄러)가 준비 큐에 있는 프로세스 중 실행시킬 프로세스를 결정하는 데 사용됩니다.
기준
- CPU 사용률: CPU가 실제 작업을 수행하는 시간의 비율을 나타냅니다. 즉, CPU가 유휴 상태로 놀고 있지 않고 얼마나 효율적으로 사용되고 있는지 평가합니다.
- 처리량: 단위 시간당 완료된 프로세스(작업)의 수를 나타냅니다.
- 응답 시간: 프로세스에 요청이 발생했을 때 응답까지 걸리는 시간
- 반환 시간: 프로세스가 로드된 후부터 종료될 때까지 걸리는 시간
- 대기 시간: 프로세스가 대기 큐에서 대기하는 시간의 총합
스케줄링 알고리즘은 비선점형 스케줄링과 선점형 스케줄링으로 나뉘게 됩니다. 비선점형 스케줄링에 대해 먼저 알아보겠습니다.
비선점형 스케줄링은 실행 중인 프로세스가 종료될 때까지 다른 프로세스를 실행할 수 없음을 의미합니다.
크게 비선점형 스케줄링은 FCFS(First Come First Served) 스케줄링, SJF(Shortest Job First), HRRN(Highest Response Ratio Next) 스케줄링이 있습니다. FCFS 스케줄링, SJF 스케줄링, HRRN 스케줄링에 대해 알아보도록 하겠습니다.
FCFS 스케줄링
FCFS 스케줄링은 First Come First Served라는 용어로 먼저 도착한 프로세스를 먼저 처리하는 방식입니다.
자료구조인 Queue를 사용하여 선입선출 방식으로 관리합니다.
SJF 스케줄링
SJF 스케줄링은 Shortest Job First라는 용어로 실행 시간이 가장 짧은 프로세스를 먼저 처리하는 방식입니다.
우선순위를 부여하는 방식은 준비 큐에 대기중엔 프로세스 중 CPU를 점유하는 실행 시간인 Burst Time이 가장 짧은 프로세스부터 실행합니다.
만약, 다음과 같은 상황을 가정하면 어떻게 될까요?
- 실행 시간이 1초인 프로세스 10개가 준비 큐에 대기 중입니다.
- 실행 시간이 2초인 프로세스도 준비 큐에 대기 중입니다.
SJF 스케줄링에 따르면 실행 시간이 짧은 프로세스가 우선적으로 처리되므로, 1초짜리 프로세스 10개가 모두 실행된 후에야 2초짜리 프로세스가 실행됩니다. 실행 시간이 긴 프로세스는 짧은 프로세스들에 의해 계속 뒤로 밀리며 실행 기회를 얻지 못할 수 있습니다. 이러한 상황이 반복되면 실행 시간이 긴 프로세스가 무한정 대기하게 되는 기아 현상(Starvation)이 발생할 수 있습니다. 또한, 각 프로세스의 정확한 실행 시간을 미리 예측하기 어려운 경우가 많아, 정확한 우선순위를 부여하기 어렵다는 한계도 존재합니다.
기아 현상에 대해 조금 더 설명하도록 하겠습니다.
기아 현상은 앞서 나온 예시처럼, 우선순위가 높은 프로세스만 계속 수행되어 우선순위가 낮은 특정 프로세스가 실행되지 못하고 대기 상태에 머무르는 현상을 의미합니다.
HRRN 스케줄링
HRRN 스케줄링은 Highest Response Ratio Next라는 용어로 응답 비율을 기준으로 프로세스의 우선순위를 정해 처리하는 방식입니다.
SJF 스케줄링의 단점의 단점인 기아 현상을 방지할 수 있는 장점을 갖고 있습니다. HRRN 스케줄링은 응답 비율을 기준으로 처리한다 했습니다. 여기서 말한 응답 비율은 무엇일까요? 응답 비율을 나타내는 공식은 다음과 같습니다.
Response Ratio = (대기 시간 + 실행 시간) / 실행 시간
SJF의 단점인 기아 현상은 어떻게 해결할 수 있을까요? 그 핵심은 바로 대기 시간에 있습니다. HRRN 스케줄링에서는 대기 시간에 가중치를 부여하여, 대기 시간이 길어질수록 응답 비율 값이 증가합니다. 이에 따라, 대기 시간이 길어진 프로세스는 높은 우선순위를 가지게 되어 결국 실행될 기회를 얻게 됩니다.
이렇게 3가지의 비선점형 스케줄링 방식에 대해 알아보았습니다.
비선점형 방식은 실행 중인 프로세스가 완료되기 전까지 다른 프로세스를 처리할 수 없다는 단점이 있습니다. 이로 인해, 급히 처리해야 할 프로세스가 등장하더라도 대기할 수밖에 없는 상황이 발생합니다.
그렇다면 이런 문제를 어떻게 해결할 수 있을까요?
이 경우에는 선점형 스케줄링 방식을 도입해 해결할 수 있습니다. 선점형 방식에서는 현재 실행 중인 프로세스를 일시적으로 중단하고, 더 높은 우선순위를 가진 프로세스를 먼저 처리할 수 있습니다. 이를 통해 비선점형 방식의 한계를 보완하고, 시스템의 유연성과 응답성을 높일 수 있습니다.
다음으로 선점형 스케줄링 방식에 대해서 알아보도록 하겠습니다.
'CS' 카테고리의 다른 글
| 데이터베이스 이상 현상의 원인, 속성 간 종속 (0) | 2024.09.25 |
|---|---|
| CPU를 극단적으로 사용하기 (1) | 2024.08.28 |
