🗂️ 메모리 관리

운영체제의 가장 중요한 임무 중 하나가 바로 '메모리 관리'입니다. 컴퓨터의 한정된 '작업 공간'(메모리)을 최대한 쥐어짜서 알뜰하게 활용해야 하거든요.

---

🪄 가상 메모리(virtual memory)

메모리 관리 기술 중 하나예요. 컴퓨터에 실제 꽂혀있는 메모리(RAM) 크기와 상관없이, 마치 엄청나게 큰 메모리가 있는 것처럼 프로그램을 '속여서' 편하게 쓰게 해주는 기술입니다.

이때 프로그램이 사용하는 '가짜 주소'를 가상 주소(logical address)라고 하고, 실제 메모리(RAM) 부품 위의 '진짜 주소'를 실제 주소(physical address)라고 불러요. 가상 주소는 MMU(메모리 관리 장치)라는 하드웨어가 진짜 주소로 '번역'해줍니다. 덕분에 프로그래머는 '실제 4GB 램의 1,234,567번지에...' 같이 복잡하게 신경 쓸 필요 없이 편하게 프로그램을 만들 수 있죠.

가상 메모리는 '가상 주소'와 '실제 주소'를 짝지어 놓은 '페이지 테이블'이라는 '주소록'을 통해 관리됩니다. 그리고 이 '주소록'을 더 빨리 찾기 위한 '초고속 캐시(TLB)'를 사용합니다.

• 용어 설명: 
  
  • TLB (Translation Lookaside Buffer):
    '주소 변환(번역) 정보'만을 전문으로 저장하는 '초고속 캐시'입니다. CPU가 매번 느린 메모리에 있는 '페이지 테이블'(주소록)을 뒤지지 않고, 바로 TLB에서 주소 변환 정보를 찾아내어 속도를 높여줍니다.

🔄 스와핑(swapping)

만약 프로그램이 '가상 주소'에는 있는데 '실제 RAM'에는 당장 없는 데이터를 달라고 하면 '페이지 폴트'가 발생합니다. 이때 운영체제는 RAM에서 당장 안 쓰는 데이터를 '하드디스크'로 쫓아내고, 하드디스크에 있던 필요한 데이터를 RAM으로 불러옵니다. 이렇게 RAM과 하드디스크 간에 데이터를 맞바꾸는 것을 스와핑(Swapping)이라고 해요. 이 과정을 통해 프로그램은 페이지 폴트가 없었던 것처럼 자연스럽게 계속 돌아갑니다.

 

🚨 페이지 폴트(page fault)

프로그램이 '내 주소 공간(가상 메모리)에는 분명히 있는데, 지금 당장 RAM(실제 메모리)에는 올라와 있지 않은' 데이터를 달라고 할 때 발생합니다. 페이지 폴트와 그로 인한 스와핑은 보통 이런 순서로 일어납니다:

1. 유효한 가상 주소에 접근했지만, 해당 데이터(페이지)가 RAM에 없으면 CPU가 '트랩'(긴급 신호)을 발생시켜 운영체제에 알립니다.
2. 운영체제는 하드디스크(보조기억장치)에서 필요한 데이터를 찾습니다.
3. RAM에서 '사용하지 않는 공간(프레임)'을 찾습니다. (만약 꽉 찼다면? '페이지 교체 알고리즘'을 사용해 희생양을 골라 쫓아냅니다. 이때 스와핑이 발생!)
4. 하드디스크의 데이터를 비어있는 RAM 공간(프레임)으로 가져옵니다.
5. '페이지 테이블'(주소록)을 '이제 이 데이터는 RAM의 OOO 번지에 있어!'라고 최신 정보로 업데이트합니다.
6. 멈췄던 명령어를 다시 시작합니다. (이제 RAM에 있으니 정상 작동!)

• 용어 설명: 
  
  • 페이지(page):
    가상 메모리를 나누는 '고정된 크기의 조각' (예: 4KB)
  • 프레임(frame):
    실제 메모리(RAM)를 나누는 '페이지와 똑같은 크기의 빈칸'

💼 작업 세트(working set)

프로그램이 '최근에 자주 사용했던' 데이터(페이지)들을 미리 파악하는 것입니다. 이 '자주 쓰는 세트'를 '작업 세트(Working Set)'라고 부릅니다. 이 세트를 미리 RAM에 올려두면 페이지 폴트와 스와핑이 훨씬 줄어들겠죠?

📈 PFF(Page Fault Frequency)

페이지 폴트가 '얼마나 자주' 일어나는지(빈도)를 보고 동적으로 관리하는 방법입니다. '이것보다 더 자주 발생하면 안 돼!'(상한선), '이것보다 적게 발생하면 낭비야!'(하한선) 기준을 정해두는 거죠. 상한선을 넘으면 (페이지 폴트가 너무 잦으면) RAM에 공간(프레임)을 더 주고, 하한선 밑으로 내려가면 (너무 안 쓰면) 공간을 뺏습니다.

---

📊 메모리 할당

메모리에 프로그램을 올릴 때는 '어디서부터(시작 위치)', '얼마나(할당 크기)'를 정해줘야 합니다. 할당 방식은 크게 '연속 할당'과 '불연속 할당'으로 나뉩니다.

📏 연속 할당

프로그램을 '통째로' 메모리의 '연속된 공간'에 딱 붙여서 할당하는 옛날 방식입니다. 메모리를 미리 똑같은 크기로 나눠두는 '고정 분할 방식'과, 프로그램 크기에 맞게 딱 맞춰 잘라 쓰는 '가변 분할 방식'이 있습니다.

📦 고정  분할 방식(fixed partition allocation)

메모리를 '100MB짜리 방 4개'처럼 미리 나눠두는 방식입니다. 융통성이 없고, 30MB짜리 프로그램이 100MB짜리 방에 들어가면 70MB가 낭비되는 '내부 단편화'가 발생합니다.

🧩 가변 분할 방식(variable partition allocation)

프로그램이 '30MB 필요해요' 하면 딱 30MB만, '70MB 필요해요' 하면 70MB만 잘라서 주는 방식입니다. '내부 단편화'는 없지만, 프로그램들이 들어왔다 나가기를 반복하면... 5MB, 10MB, 7MB 같은 '자투리 공간'들이 많이 생겨서, 100MB짜리 프로그램이 못 들어오는 '외부 단편화'가 발생할 수 있습니다. 이는 최초 적합(first fit), 최적 적합(best fit), 최악 적합(worst fit) 같은 알고리즘으로 빈 공간(홀)을 찾습니다.

이름	설명
최초적합(First Fit)	메모리 '처음(위)'부터 뒤져서, 프로그램이 들어갈 수 있는 '첫 번째' 빈 공간(홀)에 바로 할당합니다.
최적적합(Best Fit)	빈 공간을 다 뒤져서, 프로그램 크기와 '가장 딱 맞는'(제일 작은) 공간에 할당합니다. (자투리를 적게 남김)
최악적합(Worst Fit)	빈 공간을 다 뒤져서, '가장 큰' 공간에 할당합니다. (남는 공간을 크게 만들어서 다른 프로그램이 또 쓸 수 있게)

 

용어 설명: 

• 내부 단편화(internal fragmentation):
  방(할당된 공간)은 큰데, 프로그램이 작아서 '방 안에' 공간이 남아도는 현상.
• 외부 단편화(external fragmentation):
  자투리 공간(홀)들은 많은데 다 합쳐도 프로그램 크기보다 작아서, '방 사이에' 공간이 낭비되는 현상.
• 홀(hole):
  아직 아무도 쓰지 않는 '비어있는 메모리 공간'.

🔀 불연속 할당

프로그램을 '통째로'가 아니라 '여러 조각으로 쪼개서' 메모리 여기저기 '흩뿌려' 할당하는 현대적인 방식입니다. '페이징' 기법이 대표적입니다. (그 외에 세그멘테이션, 페이지드 세그멘테이션도 있습니다.)

📖 페이징(paging)

프로그램을 똑같은 크기(예: 4KB)의 '페이지'로 쪼개서, 실제 메모리(RAM)의 빈 '프레임'에 흩어져서 집어넣는 방식입니다. '페이지 테이블'(주소록)만 있으면 어디 있는지 다 찾을 수 있죠. 자투리 공간(외부 단편화) 문제가 해결되지만, 주소 변환(번역)이 복잡해집니다.

📂 세그멘테이션(segmentation)

페이지처럼 '크기'로 쪼개는 게 아니라, '의미 단위'(세그먼트)로 쪼개는 방식입니다. 예를 들어 프로그램의 '코드 영역', '데이터 영역', '스택 영역'처럼 의미 있는 덩어리로 나누는 거죠. '코드 영역'은 '공유'하거나 '보안(읽기 전용)'을 걸기 좋아지지만, 조각(세그먼트)들 크기가 제각각이라 '외부 단편화' 문제가 다시 생길 수 있습니다.

📑 페이지드 세그멘테이션(paged segmentation)

두 방식의 장점을 합친 겁니다. 먼저 '의미 단위(세그먼트)'로 나누고(세그멘테이션), 그렇게 나뉜 각 세그먼트를 다시 '똑같은 크기(페이지)'로 잘게 쪼개는(페이징) 방식입니다. 복잡하지만 강력하죠.

---

♻️ 페이지 교체 알고리즘

RAM은 한정되어 있어서 스와핑(교체)은 필연적입니다. '누구를 쫓아낼지' 결정하는 규칙이 바로 '페이지 교체 알고리즘'입니다. 이 알고리즘이 똑똑해야 스와핑이 덜 일어나고 성능이 좋아집니다.

🔮 오프라인 알고리즘(offline algorithm)

'미래'를 내다보고, '앞으로 가장 오랫동안 안 쓰일 놈'을 쫓아내는 가장 완벽한 알고리즘입니다. 하지만... 당연히 '미래를 예측할 수 없으니' 실제로는 못 씁니다. 그럼 왜 배우냐고요? 다른 알고리즘들이 이 '완벽한 알고리즘'에 비해 얼마나 성능이 떨어지는지 비교하는 '기준점(상한선)'이 되기 때문입니다.

➡️ FIFO(First In First Out)

가장 단순한 방법. '가장 먼저 들어온 놈'이 '가장 먼저 쫓겨납니다.' (줄 서기랑 똑같죠.)

⏳ LRU(Least Recently Used)

"'가장 오랫동안 안 쓰인 놈'을 쫓아냅니다." (FIFO보다 훨씬 합리적이죠.) 다만, '누가 가장 오래됐는지'를 기록하기 위해 페이지마다 시간을 재거나(계수기) 순서를 기록해야(스택) 해서 좀 귀찮습니다. (비용이 듭니다.)

LRU를 프로그래밍으로 구현할 땐 보통 '해시 테이블'과 '이중 연결 리스트'를 씁니다. '해시 테이블'로 원하는 페이지를 빨리 찾고, '이중 연결 리스트'로 최근에 쓴 순서를 관리(썼으면 맨 앞으로)합니다. C++로 구현한 코드는 다음과 같습니다. C++에서는 해시 테이블을 unordered_map으로 구현할 수 있고, 이중 연결 리스트는 list로 구현할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class LRUCache{
    list<int> li;
    unordered_map<int,list<int>::iterator> hash;
    int csize;
public:
    LRUCache(int);
    void refer(int);
    void display();
};
LRUCache::LRUCache(int n){
    csize=n;
}

void LRUCache::refer(int x){
    if(hash.find(x)==hash.end()){
        if(li.size()==csize){
            //가장 끝에 있는 것을 뽑아낸다.
            //이는 가장 오래된 것을 의미한다.
            int last=li.back();
            li.pop_back();
            hasn.erase(last);
        }
    } else{
        li.erase(hasn[x]);
    }
    
    //해당 페이지를 참조할 때
    //가장 앞에 붙인다. 또한 ,이를 해시 테이블에 저장한다.
    li.push_front(x);
    hash[x]=li.begin();
}

void LRUCache::display(){
    for(auto it=li.begin(); it!=li.end();it++){
        cout<<(*it)<<" ";
    }
    cout<<"\n";
}
int main(){
    LRUCache ca(3);
    ca.refer(1);
    ca.display();
    ca.refer(3);
    ca.display();
    ca.refer(0);
    ca.display();
    ca.refer(3);
    ca.display();
    ca.refer(5);
    ca.display();
    ca.refer(6);
    ca.display();
    ca.refer(3);
    ca.display();
    return 0;
}
/*
3 1
0 3 1
3 0 1
5 3 0
6 5 3
3 6 5
*/

⏰ NUR(Not Used Recently)

LRU의 '귀찮음(비용)'을 개선한 알고리즘입니다. (일명 '시계 알고리즘(Clock Algorithm)') 각 페이지마다 '최근에 썼니?'(1), '안 썼니?'(0)를 표시하는 '기회 비트'만 둡니다. 시계 방향으로 돌면서 '안 쓴 놈'(0)을 찾으면 그놈을 쫓아내고, '쓴 놈'(1)을 만나면 '기회를 한 번 더 주고' 0으로 바꿔둔 뒤 지나갑니다.

🔢 LFU(Least Frequently Used)

"'가장 사용 횟수(빈도)가 적은' 페이지를 쫓아냅니다." '딱 한 번 쓰이고 안 쓰인 놈'을 쫓아내는 거죠. 이것도 횟수를 다 세야 해서 비용이 듭니다.

---

1. 내부단편화와 외부단편화의 차이를 설명하세요.

내부 단편화는 고정된 크기의 메모리를 할당할 때 실제 필요한 공간보다 더 큰 블록이 배정되어 내부에서 낭비가 발생하는 현상입니다. 반면 외부 단편화는 가변 크기 메모리를 사용하다가 메모리 공간이 조각나면서 충분한 총 공간은 있어도 연속된 공간이 없어 배정이 어려운 현상입니다.

 

2. 스와핑이 무엇이고 발생하는 문제점이 무엇인가요?

스와핑은 메모리가 부족할 때 프로세스 전체를 디스크로 내보냈다가 다시 메모리로 가져오는 기법입니다. 하지만 디스크 I/O가 느리기 때문에 심한 성능 저하가 발생할 수 있고, 워킹셋이 계속 바뀌면 스래싱이 발생해 시스템 전체 성능이 크게 떨어지는 문제가 있습니다.

 

3. 페이지 교체 알고리즘 종류들을 한 줄로 요약해주세요.

페이지 교체 알고리즘은 페이지 부재가 발생했을 때 어떤 페이지를 메모리에서 내보낼지를 결정해 페이지 부하를 최소화하기 위한 메모리 관리 기법입니다. FIFO는 먼저 들어온 페이지부터 교체하며, LRU는 가장 오래 사용되지 않은 페이지를, LFU는 사용 빈도가 가장 낮은 페이지를 교체하는 방식입니다.

 

4. 페이징과 세그먼테이션의 차이점은 무엇인가요?

페이징은 고정 크기 블록으로 메모리를 나눠 외부 단편화를 해결하는 방식이고, 세그먼테이션은 코드, 데이터 같은 논리적 단위로 가변 크기 구역을 나누어 프로그램 구조를 반영하지만 외부 단편화가 발생할 수 있는 방식입니다. 페이징은 크기를 균일하게 나누어 관리 효율을 높이고, 세그먼테이션은 의미 단위로 나누어 구조적 유연성을 강조하는 점에서 차이가 있습니다.