[운영체제] 메모리 관리

변진상·2024년 2월 9일

메모리 관리 운영체제

학습 기록

목록 보기

18/31

이 글은 면접을 위한 CS 전공지식노트의 책을 읽고 학습 후 스터디 공유를 위한 글입니다.

메모리 관리

대표적 OS의 역할

가상 메모리

메모리 관리 기법 중 하나로 컴퓨터가 실제로 이용 가능한 메모리 자원을 추상화 해 사용자들에게 더 큰 메모리로 보이게 만드는 것.
프로세스 전체가 올라가지 않고 실행에 당장 필요한 부분만 메모리 올려 한정된 물리 메모리의 한계를 보완
용어
- 가상 주소(Virtual address): 가상으로 추상화 되어 주어진 주소
- 실제 주소(Physical address): 실제 메모리상에 있는 주소
- TLB: 메모리와 CPU 사이에 있는 주소 변환을 위한 캐시. 페이지 테이블에 있는 리스트를 보관하며, CPU가 페이지 테이블까지 살피지 않도록 해 속도를 향상시킬 수 있는 캐시 계층.
- 페이지: 가상 메모리를 사용하는 최소 크기 단위
- 프레임: 실제 물리메모리를 사용하는 최소 크기 단위
가상 주소는 메모리 관리 장치(MMU, Memory management unit)에 의해 실제 주소로 변환 → 사용자 입장에서는 실제 주소를 의식할 필요 없이(추상화) 가상 주소를 이용해 프로그램 구축
가상 메모리는 가상 주소와 실제 주소가 매핑되어 있고 프로세스의 주소 정보가 들어있는 페이지 테이블로 관리 → 이때, 속도 향상을 위해 TLB 사용

페이지 폴트

프로세스의 주소공간에는 존재하지만 RAM에는 존재하지 않는 데이터나 코드에 접근시 페이지 폴트가 발생한다.

스와핑

페이지 폴트를 방지하기 위해 당장 필요하지 않은 영역을 하드에 옮기고 필요할 때 다시 RAM으로 올리는 행위를 반복하며 RAM을 관리하는 것을 스와핑이라고 한다.

어떻게 필요한 자원을 스와핑 해올 것인가?

CPU가 물리 메모리를 확인해 해당 페이지가 없으면 트랩을 발생 시킨다.
OS가 내부 테이블을 본다.
1. 잘못된 참조(주 기억장치 내 다른 프로세스와 관련된 자원을 바라보고 있는 레퍼런스라던지…)를 테이블이 가지고 있을 경우 → Abort 발생( Fault와 다르게 복구할 수 없는 예외 상황)
2. 단지 메모리에 없는 경우 → 2번으로
물리 메모리(주기억장치)의 빈 프레임을 찾는다.
디스크에서 필요한 처리 후 메모리에 페이지를 올린다.
메모리에 있는 페이지를 가리키도록 테이블을 리셋한다.(+validation bit를 v로 바꾼다.)
페이지 폴트로 인해 멈췄던 명령어의 실행을 재개한다.

스레싱

원인: 메모리에 너무 많은 프로세스가 동시에 올라가 스와핑이 많이 일어나서 발생
많은 프로세스가 동시에 올라가게 되면 페이지 폴트가 자주 일어나고 스와핑이 많이 발생하게 된다. → CPU 이용률 낮아짐
OS에서 CPU 이용률이 낮아짐에 따라 가용성을 높이기 위해 더 많은 프로세스를 메모리에 올리게 된다. → 프로세스가 더 많아짐에 따라 악순환

→ 이런 현상을 스레싱이라 함

해결 방법

하드웨어: HDD → SSD, RAM을 늘림.
OS: 작업 세트, PFF

작업 세트

프로세스의 과거 사용 이력인 지역성(시간, 공간…)을 통해 결정된 페이지의 집합을 구성 → 미리 메모리에 로드
미리 메모리에 로드하면 탐색에 드는 비용을 줄일 수 있고 스와핑을 줄일 수 있다.

PFF(Page Fault Frequency)

페이지 폴트 빈도를 조절하는 방법
상한선과 하한선을 둔다. → 만약 상한선에 도달하면 Page를 늘리고 하한선에 도달하면 페이지를 줄이는 것.

메모리 할당

메모리 관리에 이어 메모리 할당에 대한 내용

메모리에 프로램을 할당할 때에는 시작 메모리의 위치, 메모리의 할당 크기를 기반으로 할당
연속 할당, 불연속 할당으로 나뉨

연속 할당

메모리에 연속적으로 프로세스를 공간 할당(프로세스를 쪼개서 메모리에 할당하지 않음)
고정 분할 방식, 가변 분할 방식이 있다.

고정 분할 방식

메모리를 미리 나누어 관리하는 방식
내부 단편화가 발생한다.

가변 분할 방식

매 시점 프로그램의 크기에 맞춰 동적으로 메모리를 나눠 사용한다.
외부 단편화 발생

가변 분할 방식의 종류

이름	설명
최초 적합	메모리공간의 위쪽이나 아래쪽 부터 시작 → 빈 공간이 있으면 바로 할당한다.
최적 적합	프로세스의 크기 이상인 공간중 가장 작은 공간부터 할당
최악 적합	프로세스 크기와 가장 많이 차이가 나는 공간부터 할당

내부 단편화, 외부 단편화

내부단편화 (Internal Fragmentation):
내부단편화는 고정 분할에 따라 나뉜 메모리의 공간의 크기가 프로세스의 크기보다 커서 메모리가 남지만, 다른 프로세스가 사용할 수 없는 상태를 말한다.

외부단편화 (External Fragmentation):
외부단편화는 메모리 내의 여러 빈 공간들이 분산되어 있고, 이 공간들의 총합은 필요한 메모리보다 충분하지만, 단일 프로세스에 할당하기에 충분한 연속된 공간이 없을 때 발생합니다.

불연속 할당

현대 운영체제가 실질적으로 쓰는 방법
페이징 기법, 세그멘테이션 기법, 페이지드 세그멘테이션 기법이 있다.

페이징

동일한 크기의 페이지 단위로 나눠 메모리의 서로 다른 위치에 프로세스 할당
홀의 크기가 균일해지지만 주소 변환이 복잡하다.

세그멘테이션

페이지 단위가 아닌 의미의 단위인 세그먼트로 나누는 방법
프로세스는 코드, 데이터, 스택, 힙으로 이뤄지는데, 이를 기반으로 나누거나 함수 단위로 나눌 수 있다.
공유와 보안 측면에서 좋으며 홀 크기가 균일하지 않아 주소 변환이 복잡했던 문제가 해결된다.

페이지드 세그멘테이션

논리적 단위인 세그먼트로 나누고, 물리적 메모리는 페이지로 나누는 것을 의미한다. → 외부 단편화를 세그멘테이션의 단점으로부터 해방시키고, 내부 단편화를 페이징의 방식으로 해결할 수 있다.
논리적인 세그먼트와 물리적인 페이지를 매핑하기 위한 페이지 테이블이 필요합니다.
세그먼트와 페이지의 크기는 서로 다를 수 있으며, 이는 프로세스의 요구에 따라 동적으로 조정될 수 있다.

페이지 교체 알고리즘

오프라인 알고리즘

먼 미래 참조되는 페이지와 현재 할당된 페이지를 바꾸는 알고리즘. 이상적
미래에 사용되는 프로세스를 알 수 없다. 비현실적이다. → 그러나 다른 알고리즘과의 성능 비교에 대한 기준을 제공

FIFO

가장 먼저 온 페이지를 교체 영역에 가장 먼저 놓는 방법
```
3번째 페이지 교체 후 page Fault 발생
```
구현이 쉽다. 효율성은 떨어진다.
Belady’s Anomaly(벨라디의 이상 현상) 발생 가능

LRU(Least Recently Used)

참조가 가장 오래된 페이지를 바꾼다.
오래된 것을 파악하기 위해 각 페이지마다 계수기, 스택(반론: 책의 설명과는 다르게 아마도 예시로 주어진 코드나 동작을 생각하면 큐같다는 생각이 든다…)을 두어야하는 문제점이 있다.

구현 코드

해시, 이중 연결리스트를 이용해 구현 한다.
해시를 이용해 이중 연결리스트에서 빠르게 찾을 수 있도록 사용
이중 연결리스트는 한정된 메모리를 의미

    #include <bits/stdc++.h>
    using namespace std; 
    //list는 캐시를 뜻함.
    //hash는 들어왔을 때 
    //해당 페이지가 있는지 없는지를 
    //빠르게 체크해서 해당부분을 erase하는 역할을 함.
    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(); 
                hash.erase(last);
            }
        }else { 
            cout << "지웁니당! : " << distance(li.begin(), hash[x]) << "번째 " << *hash[x] << '\n';
            li.erase(hash[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;
    } 
    /*
    1
    3 1
    0 3 1
    3 0 1
    5 3 0
    6 5 3
    3 6 5
    */

스택을 이용한 MRU(Most Recently Used) 알고리즘에서의 스택의 사용

NUR(Not Used Recently) 알고리즘

clock알고리즘, Second-Chance Page-Replacement 알고리즘이라고 불리기도 한다.
이 알고리즘은 FIFO(First-In-First-Out) 알고리즘을 기반으로 하지만, 페이지를 교체할 때 매번 가장 오래된 페이지를 교체하는 것이 아니라, 페이지의 참조 비트를 확인하여 참조된 페이지는 다시 두 번째 기회를 주는 방식으로 동작한다(LRU 알고리즘의 응용 발전된 알고리즘 이유).
동작 흐름
- 페이지 히트로 참조된 페이지의 경우 참조 비트를 1로 갱신한다.
- 가장 오래된 비트부터 순회 하면서 최근에 참조된 페이지의 경우 참조 비트가 1이기 때문에 0으로 바꾸고 한번 기회를 준다.
- 참조비트가 0인 페이지를 만나면 쫓아낸다.

알고리즘은 페이지 교체 시 오버헤드가 적고, 구현이 간단하여 많은 운영 체제에서 사용되고 있다고 한다.
NUR 알고리즘의 개선판 참조 여부와 더불어 수정여부까지 체크

💡 페이지 교체 우선순위
2비트(R: 참조 됨, M: 수정 됨)를 사용하여 페이지를 4가지 카테고리로 분류
1. R = 0, M = 0: 페이지가 최근에 참조되지 않았고 수정되지 않았음.
2. R = 0, M = 1: 페이지가 최근에 참조되지 않았지만 수정되었음.
3. R = 1, M = 0: 페이지가 최근에 참조되었지만 수정되지 않았음.
4. R = 1, M = 1: 페이지가 최근에 참조되었고 수정되었음.

LFU 알고리즘

가장 참조 횟수가 적은 페이지를 교체한다.
참조(MFU, LFU 등… 참조 횟수를 기반으로 하는 알고리즘에 대한 소개)

변진상

자신을 개발하는 개발자!

이전 포스트

[디자인 패턴] MVP 패턴

다음 포스트