프로그램 입장의 성능 최적도

Brust Time이란?

CPU brust + IO Brust

IO Brust

IO 입력을 대기하는 시간

반환 시간 (Turnaround Time)

프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는데까지 걸리는 시간

대기시간(Waiting Time)

대기열에 들어와 CPU를 할당받기까지 기다린 시간

디스패쳐란?

CPU를 누구한테 줄 지 결정했으니 그 프로세스에게 CPU를 넘겨주는 역할을 하는 운영체제 커널 코드

비선점형 프로세스 스케줄링

비선점형 프로세스 스케줄링이란 프로세스가 한 번 CPU를 선점하면 해당 프로세스가 끝날 때까지 CPU를 점유하고 있는 방식을 의미합니다.

FCFS

First Come First Served

프로세스가 대기큐에 들어온 순서대로 실행되는 방법을 의미합니다.

SJF (SPN)

SJF(Shortest Job First ) SPN(Shortest Process Next)

가장 빨리 실행되는 프로세스부터 실행하는 방식이다. 선점형으로 구현이 된 SJF를 SRTF or SRTN, 비선점형으로 구현된 SJF를 SPF(Shortest Process First)이라고 할 수 있다.

선점형 프로세스 스케줄링

선점형 프로세스 스케줄링이란 프로세스 스케줄링 알고리즘에 따라서 교체되야할 프로세스가 있으면 기존 프로세스 실행 도중에 Context Switching을 통해서 다른 프로세스가 CPU를 점유할 수 있는 방식을 말합니다.

장점

• 시스템 응답 속도 향상: 높은 우선순위의 프로세스가 즉시 실행될 수 있어 시스템 응답 속도가 향상됩니다.
• 실시간 시스템 적합: 실시간 시스템처럼 빠른 응답 속도가 중요한 시스템에 적합합니다.

단점

• Context Switching 비용 발생한다.
• Starvatio(기아) 현상이 발생할 수 있다.
  • 프로세스 기아현상이란 우선순위가 낮아서 필요한 자원을 결코 할당받지 못하고 계속 기다리고 있는 상태를 발한다.

Round Robin

FCFS 방식에서 Time Quantum을 부여해서 시분할로 하는 방식이다. Time Quantum이 작으면 응답성이 증가한다는 장점 있지만 Context Switching 비용이 증가한다는 단점이 있고 Time Quantum이 크면 한 프로세스가 지나치게 CPU를 오래 차지하게 되면서 FCFS와 동일한 효과를 낼 수 있다.

SRTF or SRTN

SRTF (Shortest Remaining Time First) SRTN (Shortest Remaining Time Next)

남은 실행 시간이 가장 짧은 프로세스에게 우선순위를 부여하는 알고리즘.

CPU에 다른 프로세스가 도달할 때 실행 시간이 더 짧은 프로세스가 도달하면 SJF(SPN) 방식과 차이점이 있다.

예를 들어서

다음과 같은 프로세스가 SRTF 방식으로 처리된다고 할 때 다음과 같은 대기시간을 가진다.

우선순위 스케줄링

HRRN (Highest Response Ratio Next)

우선순위를 계산해서 우선순위가 높은 것부터 실행하는 프로세스 스케줄링 기법이며 선점형 방식과 비선점형 방식으로 나뉠 수 있다.

SPF와 SRTN의 차이에서도 알 수 있듯이 우선순위가 높은 프로세스가 대기큐에 들어왔을 때 현재 실행 중인 프로세스보다 우선순위가 높은 경우 교체를 하느냐 or 마느냐에 따라서 선점형과 비선점형으로 나뉠 수 있다고 할 수 있습니다.

에이징 (Aging)

우선순위 스케줄링은 시스템에서 특정 프로세스의 우선순위가 낮아 무한정 기다리는 경우를 방지하기 위해서 기다린 시간에 비례해 일정 시간이 지나면 우선순위를 한 단계 높여주는 방법이라고 할 수 있습니다.

MLQ

Multilevel Queue 👉 다단계 큐

특징

작업들을 여러 그룹으로 나누어 여러 개의 큐를 이용하는 기법이다.

프로세스는 예를 들어, 포그라운드 프로세스와 백그라운드 프로세스처럼 큐로 분류할 경우 요구 반응 시간이 다르므로 서로 다르게 스케줄링을 할 수 있다.

각 큐마다 독자적인 스케줄링 알고리즘을 가질 수 있다.

실행방식

첫 번째 방식은 상위 큐에 있는 프로세스가 끝나지 않으면 하위에 있는 프로세스는 실행될 수 없다. 만약, 하위큐의 프로세스가 실행되고 있는 와중에 상위큐의 프로세스가 Ready 상태가 되면 상위큐의 프로세스가 CPU를 선점한다.

또 다른 방법은 큐들 사이에 시간을 나누어 사용하는 것이다. 각 큐는 CPU 시간의 일정량을 받아서 자기 큐에 있는 다양한 프로세스들을 스케줄 할 수 있다. 예를 들어, 위에서부터 40% 30% 20% 10%의 시간을 배정받아서 큐를 동작시키는 방식이다.

단점

하위 단계로 배치된 프로세스가 영원히 하위 단계를 벗어나지 못할 가능성이 있다.

MLFQ

Multi Level Feedback Queue 👉 다단계 피드백 큐

다단계 큐에서 기아현상을 보완하기 위해서 만들어진 방식.

MLFQ가 기아현상을 방지하는 법

다단계 큐와는 다르게 프로세스가 큐들 사이를 이동하는 것을 허용한다.

각 레벨에는 기간이 설정되어 있습니다. 프로세스가 해당 레벨에서 에이징 기간만큼 실행되지 못하면 하위 레벨로 강등됩니다.

하위 레벨로 갈수록 우선순위가 낮아지므로, 오래 기다리는 프로세스가 점차 높은 우선순위를 얻게 됩니다.

이를 통해 모든 프로세스가 CPU를 점유할 수 있는 기회를 얻어 기아 문제를 방지합니다.

요약

비선점형 스케줄링 : FCFS(First Come First Served), SPF(Short Process First)

선점형 스케줄링 : SRTN(Shortest Remaining Time Next), Round Robin(FCFS 시분할 버전)

우선순위큐 스케줄링 :

• HRRN, Highest Response Ratio Next
• 선점형이 될 수도 있고 비선점형이 될 수도 있음

다단계큐(MLQ, Multi Level Queue) :

• 요구 반응속도에 따라서 큐를 여러개 구성하는 것
• 높은큐의 프로세스가 항상 먼저 실행됨
• 낮은큐의 프로세스가 실행이 안될 가능성이 있음
• 각 큐별로 다른 스케줄링 방식을 적용할 수 있음

다단계피드백큐(MLFQ, Multi Level Feedback Queue) :

• 다단계 큐 방식에서 기아현상을 보완하기 위해서 고안된 기법