스케줄링
스케줄링이란 여러 프로세스가 번갈아 사용하는 자원을 어떤 시점에 어떤 프로세스에 할당할지 결정하는 알고리즘이다. 좋은 스케줄링은 프로세서의 효율성을 높이고, 작업의 응답 시간을 최소화해 시스템의 작업 처리 능력을 향상 시킨다.
동시성과 병렬성
- 동시성은 여러 작업을 논리적으로 동시에 처리하는 개념으로 실제로 동시에 실행되는 것이 아니라 여러 작업이 짧은 시간내에 번갈아서 처리한다.
- 병렬성은 여러 작업을 물리적으로 동시에 처리하는 개념으로 N개의 프로세서 또는 코어를 통해 각 작업을 병렬적으로 처리한다.
스케줄링 목적
자원 할당의 공정성을 보장하고 오버헤드를 최소화하거나 단위 시간 당 작업 처리량을 최대화는 등 작업 처리를 효율적으로 하기 위해서 스케줄링을 사용한다.
스케쥴링 큐잉 도표
큐잉 도표는 보통의 프로세스 스케줄링을 설명하는 도표로, 프로세스가 프로세서를 할당 받으면 다음 네 가지 상황 중 하나가 일어난다.
- 프로세스가 입출력 요청을 보내고 입출력 큐에 진입(대기 → 준비 - 준비 큐)
- 프로세스가 새로운 프로세스를 생성(fork)하고 생성한 프로세스의 종료 대기(대기 → 준비 - 준비 큐)
- 프로세스가 시간 할당량 초과하면 준비 큐에 진입
- 인터럽트로 인해 프로세서에서 제거된 프로세스는 다시 준비 큐에 진입
스케줄러 종류와 역할
- 장기 스케줄러(작업 스케줄러)
- 디스크에서 메모리로 작업을 가져와 처리할 순서를 결정한다.(프로세스 생성)
- 새로운 작업이 보통 분 단위로 발생하기 때문에 실행빈도가 낮다.
- 현대 OS에서는 메모리 성능 향상과 가상 메모리 도입 등으로 인해 사용자 요청 시 바로 프로세스가 생성 되기 때문에 장기 스케쥴러를 사용하지 않거나 역할이 적다.
- 중기 스케줄러
- 스와핑 : 너무 많은 프로세스가 메모리에 있을 때 프로세스를 디스크의 스왑 영역 등으로 보내 메모리 공간 조절한다.
- 스왑 아웃 : 일부 프로세스를 메인 메모리에서 제거한 뒤 디스크의 스왑 영역으로 적재
- 스왑 인 : 디스크의 스왑영역에 있는 프로세스를 다시 메모리에 적재
- 단기 스케줄러
- 메모리에 적재된 프로세스 중 프로세서를 할당하여 실행상태가 되도록 결정한다.
- 실행시킬 프로세스를 수시로 선택하기 때문에 실행빈도가 높다.
- 실질적으로 프로세서를 할당하는 모듈인 디스패처를 포함할 수 있다.
실행에서 종료 상태로 변하는 것은 장기 스케줄러와 단기 스케줄러가 처리한다.
장기 스케쥴러의 직접적인 개입은 아니고, 시스템의 전체적인 프로세스 수를 조절하는 관점에서 표현된다.
선점 스케줄링과 비선점 스케줄링
선점 스케줄링
현재 실행 중인 프로세스를 인터럽트할 수 있거나 준비 상태로 이동할 수 있는 스케줄링.
- 자원 독점 방지
- 실행 중인 프로세스 변경에 따른 오버헤드 증가
- 효과적으로 사용하기 위해서는 프로세스가 많아야 하고, 선점 기준(우선순위 등)이 필요함
비선점 스케줄링
현재 실행 중인 프로세스를 인터럽트 할 수 없거나 준비 상태로 이동시킬 수 없는 스케줄링.
- 우선순위가 높은 프로세스가 생성되어도 현재 실행 중인 프로세스에 영향을 주지 못함
- 기아 현상 발생 가능
스케줄링 알고리즘
스케줄링 알고리즘 선택 기준
현재 상황에 적용했을 때 프로세서 사용률과 처리율이 높고 반환시간, 처리시간, 응답시간이 낮은 알고리즘을 선택해야한다.
선입선출(FIFO) 스케줄링 알고리즘
- 먼저 들어온 작업부터 순서대로 처리한다.
- 비선점 방식으로 가장 구현이 단순하다.
- 대부분 성능이 좋지 않고 평균 대기시간이 길다.
구현이 간단한 FIFO 스케줄링 알고리즘은 실시간성이 불필요한 비선점형 일괄 처리 환경에서 사용하기 좋은데, 대표적인 예시로 프린터 작업 큐가 있다.
최소작업(SJF, Shortest Job First) 스케줄링 알고리즘
- 실행시간이 가장 짧은 작업을 우선적으로 처리한다.
- 선점과 비선점 두 방식으로 구현할 수 있지만, 비선점인 경우 시분할 시스템에 적용이 어렵다.
- 선점인 경우 실행 중인 작업보다 작업시간이 더 짧은 작업이 들어오면 더 짧은 작업을 우선적으로 처리시킨다. 이러한 이유로 평균 대기시간이 짧지만, 기아 문제가 생길 수 있고 실행시간을 예측하기 어렵다.
우선순위 스케줄링 알고리즘
- 우선순위에 따라 작업을 처리해 실행 중인 작업의 우선순위보다 큰 작업이들어오면 더 높은 우선순위의 작업을 우선적으로 처리시킨다.
- 선점과 비선점 두 방식으로 구현할 수 있다. 선점인 경우 높은 우선순위의 작업을 우선적으로 처리하고, 비선점인 경우 대기 큐 머리 부분에 우선순위 작업을 추가한다.
- 이 또한 SJF처럼 기아 문제가 생길 수 있지만, 오래 대기한 작업의 우선순위를 높이는 에이징 방식으로 해결할 수 있다.
라운드-로빈 스케줄링 알고리즘
- 시분할 시스템을 위해 설계된 알고리즘으로, 시간 할당량만큼 FIFO 방식으로 작업을 처리한다.
- 시간 할당량 내에 작업이 종료되면 다음 작업이 수행되지만, 작업이 종료되지 않다면 OS(커널)이 인터럽트해 다음 작업으로 이동시킨다. 즉, 선점형 스케줄링으로 구현된다.
- 시간 할당량이 너무 길면 FIFO 스케줄링과 비슷해지고, 너무 짧으면 많은 컨텍스트 스위칭이 일어나 높은 비용이 발생한다.
시간 할당량(Time Slice)가 작다면 반응성이 좋아지고 대기 시간이 짧아지지만, 많은 컨텍스트 스위칭으로 오버헤드가 커진다. 반대로 시간 할당량이 길다면 컨텍스트 스위칭의 빈도가 줄어들어 오버헤드가 작지만, 다른 프로세스의 접근성이 떨어지고 자칫 FIFO 스케줄링 알고리즘과 비슷한 결과가 발생될 수 있다.
그래서 시간 할당량에 따른 Trade-Off를 고려해 적당한 시간 할당량을 선택해야한다.
다단계(MLQ, MultiLevel Queue) 스케줄링 알고리즘
- 서로 다른 묶음으로 분류해 각 큐에 저장하는 스케줄링 알고리즘이기 때문에 각 작업을 서로 다른 묶음으로 분류할 수 있을 때 사용가능하다.
- 이때, 각 큐는 독자적인 스케줄링 알고리즘으로 작업을 처리할 수 있으며, 절대적인 우선순위가 존재해 우선순위가 높은 큐가 전부 비워져야 다음 큐의 작업이 실행된다.
- 반응속도는 빠르지만, 각 큐의 생성으로 인해 오버헤드가 크며 기아가 발생할 수 있다.
다단계 피드백 큐 스케줄링 알고리즘
- 다단계 알고리즘에서 작업이 큐 사이를 이동할 수 있도록 확장한 스케줄링 알고리즘이다.
- 설계와 구현이 복잡한 대신 자동으로 프로세스/입출력 중심 프로세스를 구분해 관리한다.
HRN 스케줄링 알고리즘
- SJF 스케줄링 알고리즘의 단점을 보완한 비선점 우순선위 기반 스케줄링 알고리즘이다.
- 우선순위 : (서비스를 받을 시간 + 대기한 시간) / 서비스를 받을 시간
- 대기한 시간이 길어질수록 우선순위가 높아져 자연스레 기아 문제가 해결된다.
스레드 스케줄링 알고리즘
- 사용자 수준 스레드와 커널 수준 스레드의 차이 중 하나가 스레드 스케줄링 방식의 차이다.
- 사용자 수준 스레드는 같은 프로세스 내의 스레드끼리 CPU를 경쟁하는 프로세스 경쟁 범위를 가지며, 스레드 라이브러리에 의해 스케줄링이 일어난다.
- 스레드 라이브러리가 관리한다고 하지만, 실제로는 CPU에서 실행되기 위해서는 커널의 역할이 필요하긴 하다.
- 커널 수준 스레드는 시스템 전체의 모든 스레드끼리 CPU를 경쟁하는 시스템 경쟁 범위를 가지며, 커널에 의해 스케줄링이 일어난다.
생각 정리
답변에 대한 내용은 스케줄링 알고리즘을 학습한 뒤 고민한 내용을 정리한 답변이므로, 틀린 내용이 있을 수 있습니다.
프로세스 스케줄링과 스레드 스케줄링의 차이점
프로세스 스케줄링은 각각의 프로세스에 CPU를 할당하는 작업인 반면 스레드는 같은 프로세스 내에서 각 스레드에게 CPU를 할당하는 작업이다. 각 프로세스는 독립적인 메모리를 갖고 있어 오버헤드가 크지만, 스레드는 공유하는 메모리가 있어 오버헤드가 적어 스레드 스케줄링이 보다 경량화되어 있다. 또한, 사용자 수준 스레드는 라이브러리 수준에서 직접 스케줄링 되기 때문에 프로세스 스케줄링과 다른 방식으로 구분할 수도 있다.
싱글 스레드 CPU에서 상시로 돌아가는 프로세스는 어떤 스케줄링 알고리즘이 좋을까??
다단계 피드백 큐 스케줄링이 좋다고 생각한다. 상시로 돌아가는 프로세스를 처음에 가장 높은 우선순위를 주어 우선적으로 실행시킬 수 있다. 이후 CPU 점유 시간에 따라 우선순위가 동적으로 조절되어 낮은 우선순위 큐로 이동하게 되지만, 낮은 우선순위로 이동시키면서도 더 긴 시간 할당량을 부여해 상시 실행시키는 효과를 볼 수 있다. 하지만 싱글 스레드 CPU 조건으로 인해 기아 문제를 고려해봐야 되는데 이는 다단계 피드백 큐가 일정 시간이 지나면 우선순위가 낮은 프로세스를 높은 우선순위 큐로 이동시키는 에이징 기법으로 자연스레 해결된다.
학습하며 정리한 글이기 때문에 혼용된 표현 또는 잘못된 내용이 있을 수 있습니다.
만약, 발견하신 경우 댓글을 통해 알려주신다면 진심으로 감사드립니다.
