[CS] 운영체제 - CPU 스케줄링, 캐시, 메모리할당

안녕하세요! 하마코입니다. 😊

 

개발자에게 필요한 운영체제 공부 마지막을 달리고 있는데요!

가상메모리를 공부했던 1탄, 프로세스와 스레드를 공부했던 2탄에 이어

CPU 스케줄링과 캐시, 메모리할당을 공부해보겠습니다. 📚

 

---

CPU 스케줄링 알고리즘

CPU가 어떤 프로세스를 선택할 건지는 스케줄링 알고리즘을 통해 선택되며 효율적으로 선택하는 게 중요합니다.

여기서 '효율적'이란 아래 내용을 만족하는 상황입니다.

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

다양한 상황에 따라 스케줄링 알고리즘은 나누어지며, 방식은 크게 비선점형/선점형으로 나뉩니다.

 

 

비선점형 방식(non-preemptive)

비선점형 방식은 프로세스가 스스로 CPU 소유권을 포기하는 방식입니다.

강제로 프로세스를 중지하지 않기에 컨텍스트 스위칭으로 인한 부하가 적습니다.

1️⃣ FCFS (First Come, First Served)

가장 먼저 온 것을 가장 먼저 처리하는 알고리즘입니다. (FIFO가 생각난다면 정답!)

단점으로는, 길게 수행되는 프로세스 때문에 준비 큐에서 오래 기다리는 현상(Convey Effect)이 발생한다는 점이 있습니다.

2️⃣ SJF (Shortest Job First)

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

그래서 평균 대기 시간이 가장 짧다는 장점이 있습니다.

단점으로는, 긴 시간을 가진 프로세스가 실행되지 않는 현상이 일어날 수 있다는 점입니다.

 

SJF는 실행 시간을 안다면 좋겠지만,

실제로는 실행 시간을 알 수 없기에 과거의 실행했던 시간을 토대로 추측해서 사용합니다.

3️⃣ 우선순위 (Aging)

오래된 작업일수록 우선순위를 높이는 Aging을 통해 단점을 보완한 알고리즘입니다.

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

 

우선순위 알고리즘은 앞서 설명한 SJF+우선순위를 말하는 것뿐만 아니라

FCFS를 활용하여 만들기도 하며 선점형, 비선점형적인 우선순위 스케줄링 알고리즘을 말하기도 합니다.

 

선점형 방식(preemptive)

선점형 방식은 현대 운영체제가 쓰는 방식으로, 사용하고 있는 프로세스를 알고리즘에 의해 중단시켜버리고

강제로 다른 프로세스에 CPU 소유권을 할당할 수 있는 방식입니다.

1️⃣ 라운드로빈 (RR, Round Robin)

라운드 로빈은 현대 컴퓨터가 쓰는 스케줄링 방법이며, 단순 선점형 알고리즘입니다.

각 프로세스에 동일한 할당 시간을 주고,

그 시간에 끝나지 않으면 다시 준비 큐(Ready Queue)의 뒤로 가는 알고리즘입니다.

 

예를 들어, q만큼의 할당 시간이 부여되었고 N개의 프로세스가 운영된다고 하면

(N-1)*q 시간이 지났을 때 자기 차례가 오게 됩니다.

 

할당 시간이 너무 크면 FCFS가 되고, 짧으면 컨텍스트 스위칭이 잦아져서 비용이 커집니다(오버헤드).

일반적으로 전체 작업 시간은 길어지지만 평균 응답 시간은 짧아진다는 특징이 있습니다.

또한, 라운드로빈은 로드밸런서에서 트래픽 분산 알고리즘으로도 쓰입니다.

2️⃣ SRF (Shortest Remaining Time First)

SRF는 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고,

해당 프로세스를 수행하는 알고리즘입니다.

 

반면, 위에서 설명한 SJF는 중간에 실행 시간이 더 짧은 작업이 들어와도

기존 짧은 작업을 모두 수행하고 그 다음 짧은 작업을 이어나갑니다.

3️⃣ 다단계 큐 

다단계 큐는 우선순위에 따른 준비 큐를 여러개 사용하고,

큐마다 라운드로빈이나 FCFS 등 다른 스케줄링 알고리즘을 적용한 알고리즘입니다.

 

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

우선순위가 높은 큐부터 처리되기에

낮은 큐의 프로세스가 처리되지 않는 기아현상(starvation)이 발생할 수도 있습니다.

 

캐시

캐시는 데이터를 미리 복사해 놓는 임시 저장소이자

빠른 장치와 느린 장치에서 속도 차이에 따른 병목 현상을 줄이기 위한 메모링비니다.

데이터 접근 시간 단축, 데이터 계산 시간 절약 등의 장점이 있습니다.

 

예로는, CPU 레지스터가 대표적인데 CPU가 메모리로부터 데이터를 가져올 때

시간이 너무 많이 들어서 중간에 레지스터 계층을 둬서 속도 차이를 해결합니다.

캐시 히트 & 캐시 미스

캐시 히트란 캐시에서 원하는 데이터를 찾은 것을 말하며

캐시 미스란 캐시에서 원하는 데이터를 찾지 못한 것을 의미합니다.

만약, 캐시 미스가 일어나면 메모리로 가서 원하는 데이터를 레지스터에 등록합니다.

지역성

캐시를 설정할 때는 자주 사용하는 데이터를 기반으로 설정해야 히트가 잘 날 수 있는데요.

이 때 '지역성'을 기반으로 설정하고, 지역성은 시간 지역성과 공간 지역성으로 나뉩니다.

 

1) 시간 지역성

: 최근 사용한 데이터에 다시 접근하려는 특성입니다.

2) 공간 지역성

: 최근 접근한 데이터를 이루고 있는 공간이나 그 가까운 공간에 접근하는 특성입니다.

 

캐시매핑

캐시의 크기는 메모리보다 항상 작기 때문에 효율적으로 매핑하는 것이 중요하며

매핑 방식에는 직접 매핑, 연관 매핑, 집합-연관매핑이 있습니다. (매핑을 사상이라고도 합니다!)

1️⃣ 직접 매핑 (Direct Mapping) - "직접 블록별 매핑"

직접 매핑이란 메모리의 특정 블록을 특정 캐시 라인에만 매핑할 수 있는 것입니다.

 

예를 들어, 메모리가 A개의 페이지, 캐시가 B개의 페이지로 구성된다고 했을 때

메모리가 페이지 수 A를 B개로 나눠서 메모리의 페이지 수는 B*블록수가 됩니다.

메모리가 1~100이 있고, 캐시가 1~5가 있다면 1:1~20, 2:21~40 같은 방식으로 매핑됩니다.

 

🤔 내부적으로 어떻게 구성되어 있을까?

 

운영체제는 메모리를 똑같은 크기의 페이지로 나눠서 관리를 하며 <P,D>로 나누어 관리하는데

P(Page Number)는 페이지 번호, D(Distance)는 페이지번호로부터 해당 주소까지의 거리입니다.

어떤 페이지인지에 따라 변환되는 것은 P이며, D는 변환되지 않고 유지됩니다.

 

2️⃣ 연관 매핑 (Associative Mapping) - "자유로이 연관 매핑"

연관 매핑이란 순서를 일치시키지 않고 관련있는 캐시와 메모리를 매핑하며

메모리의 컨텐츠가 캐시의 어느 위치에도 올라갈 수 있는 방법을 의미합니다.

정해두는 위치가 없기에 스와핑은 덜 일어나지만,

캐시의 모든 블록을 탐색해야해서 속도가 직접 매핑보다 느립니다. 

 

3️⃣ 집합-연관매핑 (Set Associate Mapping)

집합을 나누고 해당 집합에는 bd(block distance)만 같으면 들어올 수 있게 하는데,

이 때 어떤 블록에도 들어올 수 있게 하는 매핑 방법입니다.

이를 통해 모든 블록을 찾을 필요 없이 특정 블록을 찾게 해

탐색 비용을 낮춘 직접 블록의 장점과 스와핑을 완화시키는 연관매핑의 장점을 모두 지닙니다.

 

메모리 할당

프로그램에 필요한 메모리를 할당할 때 시작 메모리 위치, 메모리 할당 크기를 기반으로 할당합니다.

연속 할당 (Contiguous Memory Allocation)

메모리에 연속적으로 공간을 할당하는 것을 의미합니다.

사용 가능한 모든 메모리 공간이 같은 위치에 함께 있습니다.

즉, 메모리 파티션이 전체 메모리 공간에서 여기저기에 분산되어있지 않습니다.

 

연속 할당의 방식에는 고정분할방식과 가변분할방식이 있습니다.

1️⃣ 고정분할방식 (Fixed Partition Allocation)

메모리를 미리 같은 크기로 분할해서 할당하는 방법입니다.

다만, 같은 크기로 분할해서 할당하기에 정해둔 칸 안에 모두 차지 않는 내부단편화가 발생할 수 있습니다.

2️⃣ 가변분할방식 (Fixed Partition Allocation)

프로그램에 필요한 만큼 동적으로 할당하는 방법입니다.

메모리를 고정된 크기 블록으로 나누지 않고, 프로그램이 필요한 만큼의 메모리를 동적으로 할당합니다.

 

프로그램이 할당 된 후 남은 공간은 새로운 가변 분할로 남겨지며,

이는  다른 프로그램에 할당될 수 있어서 내부단편화를 줄일 수 있지만

연속한 곳들을 할당하다가 남는 곳이 생길 수 있기에 외부단편화가 발생할 수 있습니다.

 

가변 분할 방식에는 아래 방법들이 있습니다.

• 최초적합(first fit) : 위쪽이나 아래쪽부터 시작해 홀을 찾으면 바로 할당
• 최적적합(best fit) : 필요한 메모리 크기 이상인 공간 중 가장 작은 홀부터 할당
• 최악적합(worst fit) : 프로세스의 크기와 가장 많이 차이가 나는 홀에 하당

만약 10 크기의 프로세스가 있을 때, 아래 크기에 맞게 들어갑니다.

12	최초적합
10	최적적합
25	최악적합

 

불연속 할당 (Non-Contiguous Memory Allocation)

메모리를 연속적으로 할당하지 않는 방법으로, 현대 운영체제가 쓰는 방법입니다.

프로그램에 필요한 메모리를 쪼개어 서로 다른 위치에 있는 메모리 공간에 할당합니다.

1️⃣  페이징 (Memory Paging)

페이징은 동일한 크기의 페이지 단위로 나누어 메모리의 서로 다른 위치에 프로세스를 할당합니다.

홀의 크기가 균일하지 않은 문제가 없어지지만

주소 변환을 페이지별로 해야하기 때문에 주소 변환이 복잡해지는 단점이 있습니다.

2️⃣  세그멘테이션 (Memory Segmentation)

페이지 단위가 아닌 의미 단위인 세그먼트(segment)로 나누어는 방식입니다.

공유와 보안 측면에서는 좋지만, 홀 크기가 균일하지 않게 됩니다.

3️⃣  페이지드 세그멘테이션 (Paged Segmentation)

세그멘테이션으로 나누되 해당 세그멘테이션을 동일한 크기의 페이지로 나누는 방법입니다.

 

---

 

 

3번에 걸쳐 운영체제 공부를 해보았는데요!

학교에서도 배우고 있는 내용이다보니 배우고 있는 내용이랑 연계해서도 많이 정리해본 것 같습니다.

도움이 되셨다면 좋아요, 댓글 남겨주세요!

 

긴 글 읽어주셔서 감사합니다. :)

HAMACO