CPU 스케줄링 알고리즘

CPU가 어떤 프로세스를 선택할 것인지는 스케줄링 알고리즘을 통해 선택되며 효율적으로 선택하는 것이 중요하다. 효율은 아래와 같은 기준으로 정해진다.

CPU 사용률이 높은가?
단위 시간당 작업을 마친 프로세스의 수(처리량)가 높은가?
작업을 요청한 프로세스가 작업을 시작하기 전 대기하는 시간이 짧은가?

그리고 CPU 스케줄링 알고리즘은 비선점형과 선점형으로 나뉜다.

비선점형 알고리즘

프로세스가 스스로 CPU 소유권을 포기하는 방식이며, 강제로 프로세스를 중지하지 않는다. 따라서 컨텍스트 스위칭으로 인한 부하가 적다.

ex) 프로세스가 10의 시간이 걸리는 작업이면 5쯤에 우선순위가 높은 프로세스가 기존의 프로세스를 중지시키는(인터럽트) 것이 선점형이다. 이 반대가 비선점형인 것이다.

FCFS(First Come, First Served)

가장 먼저 온 것을 가장 먼저 처리하는 알고리즘이다.

길게 수행되는 프로세스 때문에 준비 큐에서 오래 기다리는 현상 (convoy effect)이 발생할 수 있다는 단점이 있다.

SJF(Shortest Job First)

실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘이다.

긴 시간을 가진 프로세스가 실행되지 않는 현상(starvation)이 일어날 수 있으며 평균 대기 시간이 가장 짧다.

실제 실행 시간을 알 수 없기 때문에 과거의 실행했던 시간을 토대로 추측해 사용한다.

우선순위 알고리즘

기존 SJF 스케줄링의 경우 긴 시간을 가진 프로세스가 실행되지 않는 현상이 있었다.

이를 오래된 작업일수록 우선순위를 높이는 방법(aging)을 통해 단점을 보완한 알고리즘이다.

우선순위는 작업의 시간, 프로세스의 메모리 요구사항, 열린 파일 수, 평균 CPU 사용량 등을 고려해 설정된다.

참고

우선순위 알고리즘은 무조건 SJF + 우선순위 인 것이 아닌, FCFS의 활용도 있을 수 있고, 선점형, 비선점형적인 우선순위 스케줄링 알고리즘을 말하기도 한다.

선점형 알고리즘

현대 운영체제가 채택한 방식이다. 지금 사용하고 있는 프로세스를 알고리즘에 의해 중단시키고 강제로 다른 프로세스에 CPU 소유권을 할당할 수 있는 방식이다.

라운드 로빈 (RR, Round Robin)

현대 컴퓨터가 사용하는 스케줄링 방법이자 단순한 선점형 알고리즘이다.

각 프로세스에 동일한 할당 시간을 주고 작업이 그 시간 안에 끝나지 않으면 다시 준비 큐의 뒤로 가는 알고리즘이다.

즉 각각 q만큼의 할당 시간이 부여되고 N개의 프로세스가 운영되고 있다면 자신의 다음 차례는 (N-1) * q 인 것이다.

특징

할당 시간이 너무 크면 FCFS가 되고, 짧으면 컨텍스트 스위칭이 잦아져 오버헤드, 즉 비용이 커진다.
일반적으로 전체 작업 시간은 길어지지만 평균 응답 시간은 짧아진다는 특징이 있다.

참고

로드밸런서에서 트래픽 분산 알고리즘으로도 사용되는 알고리즘이다.

SRF (SRTF, Shortest Remaining Time First)

SJF를 선점형으로 바꾼 방식이라고 봐도 된다.

SJF는 중간에 실행 시간이 더 짧은 작업이 들어와도 기존 짧은 작업을 모두 수행하고 그 다음 짧은 작업을 이어나간다.

SRF는 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행하는 알고리즘이다.

다단계 큐

우선순위에 따른 준비 큐를 여러 개 사용하고, 큐마다 라운드 로빈이나 FCFS 등 다른 스케줄링 알고리즘을 적용한 것을 말한다.

큐 간의 프로세스 이동이 안되므로 스케줄링 부담이 적지만 유연성이 떨어지는 특징이 있다.

우선순위가 높은 큐부터 처리되기 때문에 우선순위가 낮은 큐의 프로세스가 처리되지 않는 기아현상(starvation)이 발생할 수 있다.

캐시

데이터를 미리 복사해놓는 임시 저장소이자 빠른 장치와 느린 장치에서 속도 차이에 따른 병목 현상을 줄이기 위한 메모리를 말한다.

이를 통해 데이터 접근시간의 단축, 데이터를 다시 계산하는 시간 등의 시간을 절약할 수 있다.

캐시의 예시로는 CPU 레지스터가 대표적이다. CPU가 메모리 (RAM)로부터 데이터를 가져올 때 시간이 너무 크기 때문에 그 중간에서 레지스터 계층을 두고 속도 차이를 만들어 해결한다.

지역성의 원리

캐시를 설정할 때는 자주 사용하는 데이터를 기반으로 하는데 이 때 지역성을 기반으로 설정된다. 이 지역성은 시간 지역성과 공간 지역성으로 나뉜다.

시간 지역성 : 최근 사용한 데이터에 다시 접근하려는 특성
공간 지역성 : 최근 접근한 데이터를 이루고 있는 공간이나 그 가까운 공간에 접근하는 특성.

캐시히트와 캐시미스

캐시에서 원하는 데이터를 찾은 것을 캐시히트라고 말하고,

캐시에서 원하는 데이터를 찾기 못한 것이 캐시미스이다.

즉, 위의 이미지로 보면 캐시미스가 발생하면 제어장치가 메모리에 가서 CPU의 레지스터에 해당 데이터를 미리 세팅을 해두는 것이고, 캐시히트가 일어나는 것은 원하는 데이터가 CPU의 레지스터에 미리 세팅되어있는 데이터인 것이다.

캐시 예시

캐시는 꼭 CPU에만 해당되는 것이 아니다. 데이터베이스도 캐시 계층을 둘 수 있다.

위의 사진은 데이터베이스에서 redis 데이터베이스를 캐시계층으로 둔 것이다.

MySQL DB를 메인 DB로 사용하고 자주 사용하는 데이터는 redis 데이터베이스에 담아 메인 DB에 접근하지 않고도 자주 사용하는 데이터는 빼 쓸 수 있는 구조인 것이다.

캐시매핑

캐시의 크기는 메모리보다 항상 작기 때문에 메모리의 모든 정보를 캐시에 넣을 수 없어 효율적으로 매핑하는 것이 중요하다.

매핑방식에는 직접 매핑, 연관 매핑, 집합-연관 매핑이 있다.

직접 매핑 (direct mapping)

메모리의 특정 블록은 특정 캐시 라인에만 매핑할 수 있는 것을 말한다.

스와핑이 빈번하게 일어난다.

예시

메모리가 A개의 페이지, 캐시가 B개의 페이지로 구성되어있다고 가정해본다.

이러면 메모리의 페이지 수인 A를 캐시의 페이지 수인 B로 나누는 것이다.

이렇게 되면 메모리의 페이지 수는 B * 블록의 수가 된다. 메모리가 1에서 100을 가지고 있고 캐시가 1~5를 가지고 있다면 캐시 1은 메모리의 1에서 20을, 캐시 2는 메모리의 21에서 40을..

이러한 방식으로 매핑하는 것을 말한다.

내부 구성

운영체제는 메모리를 똑같은 크기의 페이지(보통 4kb)로 나누어 관리를 하며 <P, D> 로 나누어 관리한다.

P는 Page Number, D는 Page Offset으로 D는 페이지 번호로부터 해당 주소까지의 거리를 의미한다.

위의 사진을 보면 가상주소는 20bits로 주소를 관리해 실제주소인 16bits보다 더 많은 주소를 할당한다.

이러한 가상 주소가 페이지 테이블을 통해 실제 주소로 변환되는데 여기서 D인 Page Offset은 변환되지 않고 변환되는 것은 P인 Page Number이다.

매핑되는 부분은 P이기 때문에 P만 보면 되는데 P를 직접 매핑에서는 [tag, bd]로 세분화해 직접매핑을 구현한다.

여기서 bd(block distance)를 기반으로 <tag, bd, D>로 세분화하여 bd가 같은 라인만 매핑이 되도록 한다.

이렇게 구성되어 있다면 주홍철이 들어있는 캐시영역에는 bd가 같은 김건우와 구성천만 들어올 수 있는 것이다. (swap이 일어나는 것이다.)

즉 직접매핑은 swap이 빈번하게 일어날 수 있다. 캐시 영역이 남아있어도 그 영역은 사용하지 못하기 때문.

연관 매핑 (associative mapping)

순서를 일치시키지 않고 관련 있는 캐시와 메모리를 매핑하여 메모리의 컨텐츠가 캐시의 어느 위치에도 올라갈 수 있는 방법을 말한다.

스와핑이 덜 일어나지만 캐시의 모든 블록을 탐색해야해 속도가 직접 매핑보다 느리다.

이성준 구성천 주홍철 박종선을 다 넣었다. 위처럼 상관없이 캐시라인 전체를 사용할 수 있는 것이다.

참고로 연관매핑을 설명할때는 bd와 tag를 합한 P로 설명한다.

집합-연관 매핑 (set associate mapping)

집합을 나누고(직접매핑) 해당 집합에는 bd만 같으면 들어올 수 있도록 하는데 이 때 어떤 블럭에도 들어올 수 있도록 하는 것이다.

이를 통해 모든 블럭을 찾을 필요 없이 특정 블럭을 찾게 해 탐색비용을 낮춘 직접매핑의 장점과 스와핑을 완화시키는 연관매핑의 장점을 모두 지니게된다.

직접매핑에서 어떤 집합을 정해 블럭을 나눴었는데 그 집합에 속하지 않아 그 블럭에 해당이 안되어도 bd값만 같다면 어느 블럭이던 사용할 수 있도록 하는 것이다.

CPU 스케줄링 알고리즘, 캐시