CS 강의 2. CPU와 메모리 심화

출처 : 내일배움캠프

 

1. CU의 핵심 기능 : 스케줄링

1) 스케줄링 소개

- 프로그램을 실행하는 주체 = 프로세스 ex) 카톡 실행

- 작업을 처리하는 주체 = 스레드 ex) 카톡 메세지 송수신

 

CPU를 잘 사용하기 위해 프로세스를 잘 배정해야 한다. OS는 실행 대기 중인 프로그램들에게 CPU 자원 배정을 적절히 하여 시스템의 성능을 끌어올릴 수 있다

공통 배정조건 : 오버헤드 낮음, 사용률 높음, 기아 현상 낮음

- 오버헤드 : 프로세스가 필요한 자원보다 더 많이 사치부리며 사용하지 않도록

- 사용률 : 프로세스가 최대한 자원을 많이 받고 빨리 처리하도록

- 기아 현상 : 프로세스가 자원할당을 못받아서 배고픈 상태로 대기하지 않도록

목표에 따른 배정조건

- 배치 시스템 : 가능하면 많은 일을 수행. 시간보다는 처리량을 더 중요하게 생각한다.

- 대화형 시스템 : 빠른 응답시간, 적은 대기 시간이 중요

- 실시간 시스템 : 실시간, 최소 응답시간이 중요하다

 

정책에 따라 3가지로 나눌 수 있다

1. CPU 이용률 최대화

2. 오버헤드 최소화

3. 모든 프로세스를 공평하게 분배하는 방식

 

스케줄링의 단위 : CPU와 I/O burst cycle로 나뉜다

~ I/O burst - CPU burst - I/O burst

= 프로세스 실행은 "CPU실행 -> 입출력 대기"의 반복이다

- CPU burst

프로세스의 사용 중 연속적으로 CPU를 사용하는 구간을 의미한다, 즉 실제로 CPU를 사용하는 스케줄링의 단위

- I/O burst

프로세스의 실행 중 I/O작업이 끝날 때까지 Block되는 구간을 의미한다

 

스케줄링 알고리즘 평가 기준

- CPU 이용률 : 전체 시스템 시간 중, CPU가 작업을 처리하는 시간의 비율

- 처리량 : CPU가 단위 시간당 처리하는 프로세스의 개수

- 총 처리 시간 : 프로세스가 시작해서 끝날때까지 걸린 시간

- 대기 시간 : 프로세스가 준비완료 큐에서 대기하는 시간의 총 합

- 응답 시간 : 대화식 시스템에서 요청 후 첫 응답이 오기까지 걸린 시간

 

스케줄링의 종류

1) 선점 스케줄링 : OS가 CPU의 사용권을 선점할 수 있는 경우, 강제 회수하는 경우(처리 시간 예측 어려움)

OS가 나서서 CPU사용권을 선점하고 특정 요건에 따라 각 프로세스의 요청이 있을 때 프로세스에게 분배하는 방식

~ 가장 자원이 필요한 프로세스에게 CPU를 분배하며 상황에 따라 강제로 회수할 수도 있다. 따라서 빠른 응답 시간을 요하는 대화식 시분할 시스템에 적합하며 긴급한 프로세스를 제어할 수 있다

1-1) 우선순위 스케줄링

- 정적/ 동적으로 우선순위를 부여해 우선순위가 높은 순서부터 처리

- 우선순위가 낮은 프로세스가 무한정 기다리는 기아 현상이 발생 가능 ~ Aging 기법으로 대응할 수 있다

 

1-2) 라운드 로빈(FCFS에 의해 프로세스들이 보내지면 각 프로세스는 동일한 시간의 Time Quantum만큼 CPU를 할당

 

 

1-3) Multilevel - Queue(다단계 큐)

2) 비선점 스케줄링 : 프로세스 종료 or I/O 등 이벤트가 있을 때까지 실행보장(처리시간 예측 용이)

어떤 프로세스가 CPU를 할당받으면 그 프로세스가 종료되거나, 입출력 요구가 발생하여 자발적으로 중지될 때까지 계속 실행을 보장하는 방법

~ 순서대로 처리되는 공정성이 있고, 다음에 처리해야할 프로세스와 상관없이 응답시간을 예상할 수 있다. 선점방식보다 스케줄러 호출 빈도가 낮고 문맥교환에 의한 오버헤드가 적다. 일괄처리 시스템에 적합하며 CPU사용시간이 긴 프로세스가 다른 프로세스들을 대기시킬 수 있으므로 처리율이 떨어질 수 있다.

2-1) FCFS

 

 

2-2) SJF

- 수행시간이 가장 짧은(버스트 타임이 가장 짧은), 최단 작업 우선 스케줄링 알고리즘

- FCFS보다 평균 대기 시간이 적어, 짧은 작업에 유리

가장 적은 평균 대기 시간을 달성할 수 있다. 만약 CPU 버스트 시간이 동일하다면, 선점형 스케줄링인 경우 FCFS가 우선된다

 

2-3) HRN

 

 

스케줄링 동작시점

프로세스의 상태변화와 스케줄링

스케줄링 알고리즘에 따라 프로세스들은 상태변화가 일어나며 준비/수행 상태일때 CPU를 사용하게 된다.

1. 수행 -> 대기 : I/O요청이 발생하거나, 자식 프로세스가 종료 대기를 할 때

2. 수행 -> 종료 : 프로세스를 종료시켰을 때

3. 수행 -> 준비 : 인터럽트가 발생했을 때

4. 대기 -> 준비 : I/O가 완료되었을 때

 

1, 2는 프로세스가 스스로 CPU를 반환하므로 비선점 스케줄링이 발생한다

3, 4는 프로세스에서 CPU를 강제로 할당해야 하므로 선점 스케줄링이 발생한다

2. 메모리 심화

메모리 계층은 레지스터(CPU), 캐시, 메모리, 저장장치로 구성 : 계층 위로 올라갈수록 용량은 작아지고 가격이 비싸지만 속도는 빨라진다. 경제성과 캐시 때문에 계층을 구분한다. ex) 로딩중 : 하드디스크 또는 인터넷에서 데이터를 읽어 RAM으로 전송하는 과정 진행중

- 레지스터는 연산에 필요한 데이터를 저장하고 빠른 속도로 접근 가능한 저장공간 : CPU 안 작은 메모리, 휘발성, 속도 가장 빠름, 기억 용량이 가장 적다

- 캐시 메모리는 컴퓨터가 전원이 꺼지면 지워지지만, 제일 빠르게 조회할 수 있는 저장공간이다.

~ L1 : CPU안에 있는 캐시, L2 : CPU 바깥 메모리 영역에 있는 캐시

~ 휘발성, 속도 빠름, 기억 용량이 적다, L3 캐시도 존재한다 : L2보다 성능을 높이기 위해 메모리 영역에 추가된 캐시

- 주 기억장치(RAM)는 컴퓨터가 전원이 꺼지면 지워지지만 조금 더 빠르게 조회할 수 있는 저장공간이다. 하드디스크로부터 일정 데이터를 복사해 임시 저장 후 필요 시마다 CPU에 빠르게 전달하는 역할 : 휘발성, 속도 보통, 기억 용량이 보통

- 보조 기억장치(디스크)는 전원이 꺼져도 지워지지 않는 저장공간이다 : HDD 또는 SDD, 속도 낮음, 기억 용량이 많다

 

캐시란

캐시는 데이터를 미리 복사해놓는 임시 저장소. 화면에 출력되는 데이터는 메인 메모리에 저장된 데이터인데 이는

- 프로그램이 실행되면 디스크를 읽어 메인 메모리에 복사해두고 CPU가 메인 메모리에서 데이터를 읽어와 작업 처리한다. 이 때, 캐시가 중간에서 한 번 더 메인 메모리의 데이터를 복사해둔다.

- 빠른 장치와 느린 장치에서 속도 차이에 따른 병목 현상을 줄이기 위한 메모리

- 데이터 접근에 오래 걸리는 경우를 해결하고 다시 계산하는 시간을 절약

- 캐시는 계층과 계층 사이에서 속도 차이를 해결하기 위한 임시 저장소로 레지스터, 주 기억 장치 등을 모두 포함하는 개념이다 ~ 왜 SRAM(L1~L3)만 '캐시'라고 하는가? -> 레지스터는 CPU 연산을 위함 저장소, 메인 메모리는 실제 프로그램 실행을 위한 저장소로, 각각 다른 주 역할이 있지만 L1~L3는 정말 임시 저장소 역할만을 하기 때문에 여기를 캐시라고 하는 것이다. SRAM은 정적 메모리로서 용량은 작지만 속도가 매우 빨라 캐시 전용 메모리로 많이 사용한다

 

지역성의 원리

지역성이란, 자주 사용되는 데이터의 특성을 의미한다. 캐시를 직접 설정할 때는 자주 사용되는 데이터를 기반으로 설정해야 하며 이런 특성을 지역성이라고 한다

1) 시간 지역성 : 최근 사용한 데이터에 다시 접근하려는 특성

ex) for문 안에 선언된 i는 반복문 안에서 계속 접근이 이뤄지는 변수로 i변수에 대한 시간 지역성이 있다고 할 수 있다.

2) 공간 지역성 : 최근 접근한 데이터를 이루고 있는 공간이나 그 가까운 공간에 접근하는 특성

ex) 배열 arr의 공간에 i가 연속 할당되어 접근하는 경우, arr 요소에 대한 공간 지역성이 있다고 할 수 있다

 

캐시히트와 캐시미스

1) 캐시히트

캐시에서 원하는 데이터를 찾은 것이다.

위치도 CPU 내부이므로 빠르고 해당 데이터를 제어장치를 거쳐 가져오게 된다

2) 캐시미스

캐시에 원하는 데이터가 없는 경우, 주 메모리에 가서 데이터를 찾아와야 한다. 시스템 버스를 기반으로 작동하기 때문에 느리다.

 

캐시매핑

캐시가 히트되기 위해 매핑되는 방법을 의미한다. CPU의 레지스터와 주 메모리 간 데이터를 주고 받을 때를 기반으로 한다. 주 메모리에 비해 굉장히 작은 레지스터가 캐시 계층으로써 역할을 한다. ~ 매핑이 중요하다

1) 직접 매핑

- 메모리가 1~100이 있고 캐시가 1~10이 있다면 1:1 등 직접 매핑 ~ 처리가 빠르지만 충돌 발생이 잦다

2) 연관 매핑

- 순서를 일치하지 않고 관련있는 캐시와 메모리를 매핑 ~ 충돌이 적지만, 모든 블록을 탐색해 속도가 느리다

3) 집합 연관 매핑

- 직접 매핑과 연관 매핑을 합쳐 놓은 것, 순서는 일치하지만 집합을 둬 저장해 블록화되어 검색이 효율적이다

 

메모리 할당

메모리에 프로그램을 할당할 때는 시작 메모리 위치, 메모리의 할당 크기를 기반으로 할당한다. 연속 할당과 불연속 할당으로 나뉜다

1) 연속 할당

메모리에 연속적으로 할당하는 것, 고정 분할과 가변 분할로 나뉜다

1-1) 고정 분할 방식 : 메모리를 미리 나누어 관리 ~ 내부 단편화 발생

1-2) 가변 분할 방식 : 매 시점 프로그램에 크기에 맞게 동적으로 메모리를 나눠 공간 할당

- 최초적합 : 위에서부터 바로 보이는 공간에 할당

- 최적적합 : 크기가 가장 알맞은 공간에 할당 후 나머지 할당

- 최악적합 : 크기가 가장 큰 공간부터 할당하고 나머지 할당

~ 외부 단편화가 발생할 수 있다

최초 : 블록 크기와 공간 크기가 일치하지 않는 경우 남은 공간이 빈 공간으로 남는다. -> 외부 단편화

최적 : 메모리 내 가장 크기가 맞는 가장 작은 공간에 할당하지만 메모리 탐색에 시간이 걸려 성능 저하가 있을 수 있다

최악 : 내부 단편화가 적지만, 빈 공간을 찾는 데 시간이 걸리므로 성능 저하가 있을 수 있다

 

내부 단편화 : 메모리를 나눈 크기보다 프로그램이 작아 들어가지 못하는 공간이 많이 발생하는 것. 공간이 남음

외부 단편화 : 메모리를 나눈 크기보다 프로그램이 커 들어가지 못하는 공간이 많이 발생하는 것. 공간 부족

 

2) 불연속 할당

운영체제에서는 여러 작업을 효율적으로 수행해야 하기 떄문에 불연속 할당을 사용한다

- 단점

메모리 공간 할당과 해제 시 오버헤드 발생 가능(불필요 할당)

메모리 공간이 분산되어 있기 떄문에 프로세스가 불연속 공간에 할당될 경우 프로세스의 페이지 교체와 같은 작업이 더 복잡해질 수 있다(교체 알고리즘 최적화 필요)

 

운영체제에서 불연속 할당을 사용하는 3가지 방법

(1) 링크드 리스트 : 메모리 할당과 해제가 빠르지만 공간 낭비가 발생할 수 있다

(2) 비트맵 : 링크드 리스트보다 효율적이지만, 메모리 크기가 큰 경우 비트맵도 매우 커진다

(3) 페이지 테이블 : 가상 메모리 시스템에서 사용하는 방식으로 물리적인 주소 공간을 페이지라는 작은 블록으로 나누어 사용하는 방식이다. 각 프로세스는 자신의 페이지 테이블을 가지며, 페이지 테이블은 물리적인 주소와 가상 주소를 매핑하는 역할을 한다. 링크드 리스트와 비트맵보다 효율적이며, 가상 메모리를 구현하는 데 필요하다

 

2-1) 페이징

- 동일한 크기의 페이지 단위로 나눠 메모리의 서로 다른 위치에 프로세스를 할당

- 빈 데이터(홀)의 크기가 균일하게 되나, 주소 변환이 복잡하다

2-2) 세그멘테이션

- 의미 단위인 세그먼트로 나누는 방식

- 코드와 데이터 등을 기반으로 나눌 수 있으며, 함수 단위로 나눌 수도 있음을 의미한다

- 공유, 보안 측면에서 좋다

- 빈 데이터(홀)의 크기가 균일하지 않다

2-3) 페이지드 세그멘테이션

- 공유나 보안은 세그먼트로 나누고 물리적 메모리는 페이지로 나누는 방식이다

 

페이지 교체 알고리즘

- 메모리 내 저장된 페이지 중 어떤 페이지를 교체할 지 결정하는 알고리즘, 물리적인 메모리 공간이 한정적일 때 페이지 부재가 발생하는 상황에서 새로운 페이지를 적재하기 위해 기존 페이지 중 어떤 페이지를 제거할 지 결정하는 역할을 한다

알고리즘에 따라 페이지 부재율이나 페이지 교체 오버헤드 등의 성능이 달라진다

(1) 오프라인 알고리즘

- 먼 미래에 참조되는 페이지와 현재 할당되는 페이지를 바꾼다. 입력 데이터가 모두 주어진 상태에서 실행되므로 실행 중 새로운 입력은 없다. 입력 데이터를 한 번에 처리할 수 있으므로 실행 시간과 공간 사용량을 모두 예측할 수 있다. 따라서 입력 데이터의 크기에 따라 적절한 실행시간과 공간을 예약해 처리할 수 있다. 하지만 미래에 사용되는 프로세스를 알 수 없다 ~ 메모리 할당에서 사용할 수 없는 알고리즘이지만 다른 알고리즘과 성능 비교를 위해 기준을 제공한다

ex) 정렬 알고리즘

(2) 시간기반 알고리즘

- FIFO : 가장 먼저 온 페이지를 교체 영역에 가장 먼저 놓는 방법. 구현이 간단하지만 오래된 데이터와 최근 사용 데이터가 비슷할 경우 성능이 저하될 수 있다

- LRU : 참조가 가장 오래된 페이지를 교체하는 방법. 캐시히트율을 높일 수 있으나 데이터 저장에 추가 비용이 발생한다. ~ 참조 시간을 파악하기 위한 계수기, 스택을 두어야 한다

- NUR : Clock 알고리즘은 최근 사용 여부를 0, 1로 표시해 참조되지 않은 페이지를 교체하는 방식. 시계방향으로 돌며 0을 찾고 0을 찾는 순간 교체한 후 사용 여부를 1로 변경한다

 

NUR vs LRU

- LRU : 데이터를 사용할 때마다 최근 사용시간을 갱신

- NUR : 사용하지 않은 데이터를 주기적으로 스캔해 최근 사용 여부를 판단

 

(3) 빈도기반 알고리즘

- LFU : 가장 참조 횟수가 적은 페이지를 교체하는 방식. 캐시히트율을 높일 수 있지만, 특정 데이터만 많이 사용할 경우 성능 저하가 발생할 수 있다