CS - 2. CPU와 메모리 심화
Sparta 내일배움캠프 학습으로, CS강의에 대한 공부를 위한 필기입니다.
01. 스케줄링
프로그램을 실행해주는 주체, 컴퓨터에서 실행 중인 프로그램 = 프로세스
ex) 카카오톡을 실행하는 프로세스
작업을 처리해주는 주체, 프로세스 내에서 실행되는 작업의 단위 = 쓰레드
ex) 메시지 발송을 처리하는 쓰레드 (쓰레드는 프로세스 안에 포함)
💡 CPU를 잘 사용하기 위해 프로세스를 잘 배정해야 함.
OS는 실행 대기중인 프로그램들에게 CPU 자원 배정을 적절히 하여 시스템의 성능을 끌어올리 수 있음.
공통 배정조건 : 오버헤드 ↓ / 사용률 ↑ / 기아현상 ↓
목표에 따른 배정 조건 :
배치 시스템 : 가능하면 많은 일을 수행, (시간 < 처리량)
- 대화형 시스템 : 빠른 응답 시간, 적은 대기 시간
- 실시간 시스템 : 최소 응답 시간
1-1. 스케줄링 단위
📌 CPU , I/O Burst Cycle
프로세스 실행은 CPU 실행 ↔ 입/출력 대기의 반복
- CPU Burst
- 프로세스의 사용중에 연속적으로 CPU를 사용하는 구간을 의미 ➡ 사용하는 구간을 자원이라고 표현
- I/O Burst
- 프로세스 실행 중에 I/O 작업이 끝날 때까지 Block 되는 구간을 의미
- 프로세스 실행 중에 I/O 작업이 끝날 때까지 Block 되는 구간을 의미
1-2. 스케줄링 종류
📌1. 선점 스케줄링(Preemptive Scheduling)
💡 OS가 CPU의 사용권을 선점할 수 있는 경우, 강제 회수하는 경우 (처리 시간 예측 어려움)
OS가 나서서 CPU사용권을 선점하고 특정 요건에 따라 각 프로세스의 요청이 있을 때 프로세스에게 분배하는 방식
- 가장 자원이 필요한 프로세스에게 CPU를 분배, 상황에 따라 강제 회수 가능
빠른 응답시간을 요하는 대화식 시분할 시스템에 적합, 긴급 프로세스 제어 가능
1️⃣ 우선순위 스케줄링(Prioritiy Scheduling)
: 정적/동적으로 우선순위를 부여하여 우선수위가 높은 순으로 처리
- : 우선 순위가 낮은 프로세스가 무한정 기다리는 기아 현상 발생 가능
- Aging 방법으로 기아현상 문제 해결 가능
기다리는 시간에 따라 우선순위를 지켜주는 방식, 우선순위가 같으면 FCFS를 적용
2️⃣ 라운드로빈(Round Robin)
: 정해진 시간 할당량 만큼 프로세스를 할당한 뒤, 작업이 끝난 프로세스는 준비완료 큐의 가장 마지막에 가서 재할당을 기다리는 방법(회전식)
: 시간 할당량이 중요한데, 너무 작으면 빈번한 문맥 전환이 발생하고 너무 길으면 FCFS와 다를 바 없어짐
- 3️⃣ 다단계 큐(Mutilevel-Queue)
- 준비완료 큐를 여러개의 큐로 분류하여 각 큐가 각각 다른 스케줄링 알고리즘을 가지는 방식.
메모리 크기, 우선순위, 유형 등 프로세스의 특성에 따라 하나의 큐에 영구적으로 할당됨. 따라서 큐와 큐사이에도 스케줄링이 필요함.
📌2. 비선점 스케줄링(Non-Preemptive Scheduling)
💡 프로세스 종료 or I/O 등 이벤트가 있을 때까지 실행 보장 (처리시간 예측 용이)
어떤 프로세스가 CPU를 할당 받으면 그 프로세스가 종료되거나, 입출력 요구가 발생하여 자발적으로 중지될 때 까지 계속 실행되도록 보장하는 방법
- 순서대로 처리되는 공정성, 다음에 처리해야할 프로세스와 상관없이 응답시간을 예상할 수 있음.
- 선점 방식보다 스케줄러 호출 빈도가 낮고, 문맥교환에 의한 오버헤드가 적음
일괄처리 시스템에 적합, CPU사용시간이 긴 프로세스가 다른 프로세스들을 대기시킬 수 있으므로 처리율이 떨어질 수 있다는 단점.
1️⃣ FCFS(First Come, First Serve)
: 큐에 도착한 순서대로 CPU 할당
: 실행 시간이 짧은 게 뒤로 가면 평균 대기 시간 길어짐 ex) 계산대에서 기다리는데 앞에 손님이 엄청 많이 샀으면 내가 아무리 적어도 오래 기다리는 것처럼
2️⃣ SJF(Shorted Job First)
: 수행시간이 가장 짧다고 판단되는 작업 먼저 수행
: FCFS보다 평균 대기 시간 감소, 짧은 작업에 유리 ex) 계산대에서 내가 물병 하나라면 저 먼저 계산할게요 하면서 먼저 할 수 있는
- 3️⃣ Hrn(Highest Response-ratio Next)
- 우선순위를 계산하여 점유 불평등 보완(SJF 단점 보안)
우선 순위 = (대기시간 + 실행시간) / (실행시간)
02. 메모리
2-1. 캐시(SRAM)
캐시 메모리는 컴퓨터가 전원이 꺼지면 지워지지만 제일 빠르게 조회할 수 있는 저장공간
L1 : CPU 안에 있는 캐시 (왼손) L2 : CPU 바깥 메모리 영역에 있는 캐시
- 휘발성, 속도 빠름, 기억 용량이 적다
L3 : L2보다 성능을 더 높이기 위해 메모리 영역에 추가된 캐시
주기억장치 : 컴퓨터 전원이 꺼지면 지워지지만 조금 더 빠르게 조회될 수 있는 저장공간, RAM을 가리킴
보조기억장치 : 컴퓨터 전원이 꺼져도 지워지지 않는 저장공간, HDD, SDD를 가리킴
- 캐시는 데이터를 미리 복사해 놓는 임시 저장소
📌 우리가 보는 화면에 출력되는 데이터는 결국 메인 메모리에 저장된 데이터
1
2
3
1. 프로그램이 실행 -> 디스크를 읽어서 메인 메모리에 복사
2. CPU(MMU)가 메인 메모리에서 데이터를 읽어오며 작업 처리
3. 캐시가 중간에서 한번 더 메인 메모리의 데이터를 복사해두는 것
빠른 장치와 느린 장치에서 속도 차이에 따른 병목 현상을 줄이기 위한 메모리
**병목현상** : 물병을 부어도 한번에 다 나오지 않고 물병의 목 입구의 크기에 따라 물이 나오는 현상즉, 캐시는 계층과 계층 사이에서 속도 차이를 해결하기 위한 임시 저장소
- 레지스터 : 메모리와 CPU 사이의 속도 차이를 해결하기 위한 캐시
- 주기억장치 : 캐시 메모리와 보조기억장치 사이의 속도 차이를 해결하기 위한 캐시
❓ SRAM(L1~3캐시)만 왜 키시라고 부르는가?
1
2
3
1. 레지스터는 CPU의 연산을 위한 저장소
2. 메인 메모리는 실제 프로그램을 실행하기 위한 저장소
3. 그 사이 정말 임시 저장소 역할만 하는 것이 SRAM이기 때문 -> SRAM(L1~3캐시)은 정적 메모리로써 용량은 작지만 속도가 매우 빨라서 캐시 전용 메모리로 많이 쓰임 <br>
- ✅ 지역성의 원리
자주 사용되는 데이터의 특성을 의미, 캐시를 직접 설정할 때는 자주 사용되는 데이터를 기반으로 설정해야 하며 이러한 특성을 지역성이라고 함.
1️⃣ 시간 지역성 - 최근 사용한 데이터에 다시 접근하려는 특성
2️⃣ 공간 지역성 - 최근 접급한 데이터를 이루고 있는 공간이나 그 가까운 공간에 접근하는 특성
2-2. 캐시히트와 캐시미스
✅ 캐시히트 : 캐시에 원하는 데이터를 찾은 것 - 위치도 가깝고 CPU 내부버스를 기반으로 작동하여 빠름 - 캐시히트를 하게 되면 해당 데이터를 제어장치를 거쳐 가져오게 됨
✅ 캐시미스 : 해당 데이터가 캐시에 없다면 주메모리로 가서 데이터를 찾아오는 것 - 메모리를 가져올 때 시스템 버스를 기반으로 작동하기에 느림
✅ 캐시 매핑 : 캐시가 히트되기 위해 매핑되는 방법 1. CPU의 레지스터와 주 메모리(RAM) 간에 데이터를 주고 받을 때를 기반 2. 주 메모리에 비해 굉장히 작은 레지시터가 캐시 계층으로써 역할 -> 매핑이 중요
1️⃣ 직접 매핑
- 메인 메모리가 1~100이 있고 캐시가 1~10이 있다면 1:1~10, 2:1~20…와 같이 매핑
- 처리가 빠르지만 충돌 발생이 잦음
2️⃣ 연관 매핑
- 순서를 일치하지 않고 관련 있는 캐시와 메모리를 매핑
- 충돌이 적지만 모든 블록을 탐색하여 속도가 느림
3️⃣ 집합 연관 매핑
- 직접 매핑 + 연관 매핑
- 순서는 일치하지만 집합을 둬서 저장하며 블록화 되어있어 검색이 효율적
2-3. 메모리 할당
💡 메모리에 프로그램을 할당할 때는 시작 메모리 위치, 메모리의 할당 크기를 기반으로 할당함
1️⃣ 연속 할당 : 메모리에 연속적으로 공간을 할당하는 것 고정 분할 방식과 가변 분할 방식으로 나뉨
- 고정 분할 방식
- 메모리를 미리 나누어 관리하는 방식 한계 : 내부 단편화 발생
- 가변 분할 방식
매 시점 프로그램의 크기에 맞게 동적으로 메모리를 나누어 사용하는 방식 종류
1 2 3 4
1. 최초 적합 : 위에서부터 바로 보이는 공간에 바로 할당 2. 최적적합 : 가장 크기에 맞는 공간부터 채우고 나머지를 할당 3. 최악 접합 : 가장 크기가 큰 공간부터 채우고 나머지 할당 한계 : **외부 단편화** 발생
📌 내부 단편화
메모리를 나눈 크기보다 프로그램이 작아서 들어가지 못하는 공간이 많이 발생하는 현상
즉, 들어갈 수 있는 공간보다 프로그램이 작아서 공간이 남아버리는 것
📌 외부 단편화
- 메모리를 나눈 크기보다 프로그램이 커서 들어가지 못하는 공간이 많이 발생하는 현상
- 즉, 들어갈 공간보다 들어갈 것이 더 커서 들어가지 못하고 남아버리는 것
2️⃣ 불연속 할당
OS에서는 여러개의 작업을 효율적으로 수행해야하기 때문에 불연속 할당 방법을 사용,
단점 : 메모리 공간 할당과 해제 시의 오버헤드가 발생할 수 있음. (불필요 할당), 메모리 공간이 분산되어 있기 때문에, 프로세스가 불연속 공간에 할당될 경우 프로세스의 페이지 교체와 같은 작업이 더 복잡해질 수 있음. (교체 알고리즘 최적화 필요)
페이징
동일한 크기의 페이지 단위로 나누어 메모리의 서로 다른 위치에 프로세스를 할당
빈데이터(홀)의 크기가 균일하지 않은 문제가 없어지지만 주소 변환이 복잡
- 세그멘테이션
의미 단위인 세그먼트로 나누는 방식
- 코드와 데이터 등을 기반으로 나눌 수 있으며, 함수 단위로 나눌 수도 있음을 의미
- 공유와 보안 측면에서 좋음
- 빈데이터(홀) 크기가 균일하지 않는 문제 발생
- 페이지드 세그멘테이션
- 공유나 보안은 세그먼트로 나누고 물리적 메모리는 페이지로 나누는 방식
✅ 페이지 교체 알고리즘
메모리 내에 저장된 페이지 중에서 어떤 페이지를 교체할지 결정하는 알고리즘.
페이지 교체 알고리즘은 물리적인 메모리 공간이 한정되어 있을 때 페이지 부재(page fault)가 발생하는 상황에서 새로운 페이지를 적재하기 위해 기존 페이지 중 어떤 페이지를 제거할지 결정하는 역할
- 오프라인 알고리즘
입력 데이터가 모두 주어진 상태에서만 실행되는 알고리즘, 입력 데이터를 모두 가지고 있기 때문에 실행 중에 새로운 입력이 들어오지 않음
하지만 미래에 사용되는 프로세스는 알 수 없음.
대표적인 예로 정렬 알고리즘이 있음.
시간기반 알고리즘
✔ FIFO(First in First Out) :
가장 먼저 온 페이지를 교체 영역에 가장 먼저 놓는 방법
캐시 메모리에 새로운 데이터가 들어오면 가장 오래전에 들어온 데이터를 제거하고 새로운 데이터를 추가
✔ LRU(Least Recently Used):
- 참조가 가장 오래된 페이지를 교체하는 방법
✔ NUR(Not Used Recently):
일명 clock 알고리즘 최근 사용 여부를 0, 1로 표시하여 교체하는 방법
1은 최근에 참조, 0은 참조되지 않음을 의미
✔ LRU 🆚 NUR
LRU : 데이터를 사용할 때마다 최근 사용 시간을 갱신
NUR : 사용하지 않은 데이터를 주기적으로 스캔하여 최근 사용 여부를 판단
빈도기반 알고리즘
✔ LFU(Least Frequently Used):
- 가장 참조 횟수가 적은 페이지를 교체(=많이 사용하지 않은 것을 교체)
📌 OS에서 불연속 할당을 사용하는 3가지 방법
링크드 리스트(Linked List) : 불연속 공간에 프로세스를 할당할 때, 할당된 공간의 주소를 연결 리스트에 저장하는 방식. 메모리 할당과 해제가 빠르지만 공간 낭비가 발생할 수 있음.
비트맵(Bitmap) : 메모리 공간의 각 블록을 0 또는 1로 표시하여 사용 가능한 블록과 사용 중인 블록을 구분하는 방식. Linked List보다 효율적인 공간 관리를 제공하지만 메모리가 큰 경우 비트맵이 커지는 단점
페이지 테이블(Page Table) : 가상 메모리 시스템에서 사용되는 방식, 물리적인 주소 공간을 페이지라는 작은 블록으로 나누어 사용, 각 프로세스는 자신의 페이지 테이블을 가지며, 페이지 테이블은 물리적인 주소와 가상 주소를 매핑하는 역할을 함. 1,2보다 효율적이며 가상 메모리를 구현하는 데 필요한 기술