메모리 관리

배경

---

• 매모리는 각각 주소가 할당된 일련의 바이트로 구성되어 있습니다.
• CPU는 program counter가 지시하는 대로 메모리로부터 다음에 수행해야할 명령어를 가져오는데, 그 명령어는 필요한 경우 추가적인 데이터를 가져올 수 있으며 반대로 데이터를 메모리로 내보낼 수 있습니다.

 

💡 기본 하드웨어

 

• 메인 메모리와 각 처리 코어에 내장된 레지스터들은 CPU가 직접 접근할 수 있는 유일한 범용 저장장치입니다. 기계 명령어들은 메모리 주소만을 인수로 취급하고, 디스크의 주소는 인수로 취급하지 않기 때문에 실행되는 모든 명령어와 데이터들은 CPU가 직접 접근할 수 있는 메인 메모리나 레지스터에 적재되어 있어야 합니다. 만약 데이터가 메인 메모리나 레지스터에 없다면 CPU가 그것을 처리하기 전에 적재해야 합니다.
• 각각의 프로세스는 독립된 메모리 공간을 가질 수 있도록 보장해야 하는데 이러한 독립적인 메모리 공간은 프로세스별로 보호하고, 병행 실행을 위해 여러 프로세스가 메모리에 적재되게 하는 것이 필수입니다.
• 프로세스마다 개별적인 메모리 공간을 분리하기 위해서는 특정 프로세스만 접근할 수 있는 합법적인 메모리 주소 영역을 설정하고, 프로세스가 합법적인 영역만 접근하도록 해야합니다.
• 메모리 공간의 보호는 CPU 하드웨어가 사용자 모드에서 만들어진 모든 주소와 레지스터를 비교함으로써 이루어지는데, 사용자 모드에서 수행되는 프로그램이 운영체제의 메모리 공간이나 다른 사용자 프로그램의 메모리 공간에 접근하면 운영체제는 오류로 간주하고 트랩을 발생시킵니다.

 

    기준 레지스터

 

• 가장 작은 합법적인 물리 메모리 주소의 값을 저장

    상한 레지스터

 

• 주어진 영역의 크기 저장

 

💡 주소의 할당

 

• 프로그램은 이진 실행 파일로 디스크에 저장되어 있는데, 이 프로그램을 실행하기 위해서는 메모리에 적재해야 합니다.
• 주소를 할당하기 위해서는 링커와 로더에 대해 살펴볼 필요가 있습니다.

    링커(Linker)

 

• 링커는 무엇인가를 연결하다라고 생각하면 이해하기 쉽습니다.
• 예를들어 프로그래머가 작성한 소스코드를 컴퓨터가 이해할 수 있는 언어로 변환하는 과정을 컴파일링이라고 합니다. 그리고 이 기계어를 실행가능한 파일로 변환하는 것을 링킹이라 합니다.
• 링커는 프로그램에서 사용된 모든 함수나 변수가 해당 정의에 맞는지 확인되도록 서로 다른 개체 파일과 라이브러리 간의 참조를 확인합니다.

    로더(Loader)

 

• 로더는 이진 실행 파일을 메모리에 적재하는데 사용됩니다. 링커가 어떠한 프로그램을 실행시키기 위해 소스코드를 기계어로 변환한 다음 실행가능한 파일로 변환했다면 로더는 이 실행 가능한 파일을 메모리에 적재하는 역할을 수행합니다.

 

💡 Address Binding 하는 3가지 시점

 

    Compile Time Binding

 

• 프로세스의 물리적 주소가 컴파일 시점에 정해집니다.
• 프로세스가 메모리의 어느 위치에 들어갈지 미리 알고 있다면 컴파일러는 절대(고정) 주소를 생성할 수 있습니다.
• 만약 위치가 변경된다면 재컴파일되어야 합니다.

    Load Time Binding

 

• 프로세스가 메모리의 어디 위치로 들어가야할지 컴파일 시점에 알지 못한다면 재배치 가능 코드(Relocatable Code)를 생성해야 합니다. 이러한 재배치 가능 코드는 메모리의 어느 위치에서나 수행될 수 있는 기계 언어 코드인데 Loader가 프로세스를 메모리에 적재하는 시점에 물리 주소를 결정하게 됩니다. 그렇기 때문에 논리 주소와 물리 주소는 다르게 됩니다.

    Execution Time Binding

 

• 프로세스가 수행이 시작된 이후에 프로세스가 실행될 때 메모리 주소를 변경하는 방법입니다.
• 실행시점에 물리적 주소가 결정되며, 실행 도중에도 물리적 주소가 변경될 수 있습니다.
• 실행시간 주소 할당은 CPU가 주소를 참조할 때마다 address mapping table을 이용하여 바인딩을 점검합니다. 이러한 방식은 MMU라는 하드웨어 장치를 사용하여 논리적 주소를 물리적 주소로 바꿔줍니다.

 

💡 논리 주소와 물리 주소

 

• CPU가 생성하는 주소를 논리 주소 또는 가상 주소라 합니다.
• 메모리가 취급하는 주소를 물리 주소라 합니다.
• 컴파일 시점 바인딩은 논리 주소와 물리 주소가 같지만 적재 시점 바인딩과 실행 시점 바인딩은 논리 주소와 물리 주소가 다릅니다.

 

🤔 논리 주소와 물리 주소가 다른 경우 어떻게 매핑시킬까?

 

• 프로그램 실행중에는 논리 주소를 물리 주소로 변환을 시켜줘야 하는데 이 작업은 하드웨어 장치인 메모리 관리 장치(MMU)에 의해 실행됩니다.
• MMU를 사용한 기법에서는 기준 레지스터를 재배치 레지스터라 부릅니다. 이 재배치 레지스터속에 들어있는 값은 어떠한 논리 주소가 메모리로 보내질 때마다 논리 주소에 더해지게 됩니다. 그렇기 때문에 사용자 프로그램은 결코 실제적인 물리 주소에 접근할 수 없게 됩니다.
• 사용자 프로그램은 논리 주소를 사용한 것이고, 메모리 하드웨어는 논리 주소를 물리 주소로 바꾼것입니다.

 

연속 메모리 할당

---

• 메모리는 일반적으로 두 개의 부분으로 나누어지는데, 하나는 운영체제를 위한것이며 다른 하나는 사용자 프로세스를 위한 것입니다.
• 연속 메모리 할당은 이름에서 알 수 있듯이 각 프로세스들이 연속적인 메모리 공간을 차지하는 것입니다.

 

💡 메모리 보호

 

• 연속 메모리 할당은 각 프로세스들이 연속적으로 메모리 공간을 차지하고 있기 때문에 각 프로세스별 메모리를 어떻게 보호할 수 있는가에 대해 문제가 발생할 수 있습니다. 이러한 문제는 상한 레지스터와 재배치 레지스터를 활용하여 문제를 해결할 수 있습니다.
• CPU 스케줄러가 다음으로 수행할 프로세스를 선택할 때, 디스패처는 context-switch할 때 재배치 레지스터와 상한 레지스터에 정확한 값을 적재합니다. CPU에 의해서 생성되는 모든 논리 주소는 이 레지스터들의 값을 참조해서 확인 작업을 거치기 때문에 운영체제와 다른 사용자 프로그램을 현재 수행 중인 프로그램의 접근으로부터 보호할 수 있습니다.

💡 메모리 할당

 

• 연속적인 메모리를 할당하기 위해서는 고정된 크기로 나누는 고정 분할과 프로세스의 크기를 고려해 나누는 가변 분할 방식이 있습니다.

    고정 분할

 

• 분할의 크기가 모두 동일하거나, 서로 다를 수 있습니다. 분할 당 하나의 프로세스가 적재되기 때문에 동시에 메모리에 적재되는 프로세스의 수가 고정됩니다. 또한 수행 가능한 프로세스의 최대 크기가 제한됩니다.

    가변 분할

 

• 프로세스를 메모리의 가변 크기 파티션에 할당하는 것입니다.
• 각 파티션에는 하나의 프로세스만이 적재될 수 있습니다. 
• 가변 파티션 기법에서 운영체제는 사용 가능한 메모리 부분과 사용중인 부분을 나타내는 테이블을 사용하게 됩니다. 처음에는 모든 메모리가 사용자 프로세스에 사용 가능하며, 하나의 큰 사용 가능한 메모리 블록인 hole로 간주합니다.

    동적 메모리 할당 문제를 해결할 수 있는 기법

 

• 최초 적합 : 첫 번째 사용 가능한 공간을 할당합니다. 
• 최적 적합 : 사용 가능한 공간중 가장 작은 것을 택합니다. 
• 최악 적합 : 가장 큰  가용 공간을 택합니다.

💡 단편화

 

    외부 단편화

 

• 외부 단편화는 유휴 공간들을 모두 합치면 충분한 공간이 되지만, 그것들이 너무 작은 조각들로 여기저기 산재되어 있으면 발생합니다.
• 즉 메모리는 너무 많은 수의 매우 작은 조각들로 단편화되어 있는 것입니다.
• 외부 단편화의 심각한 문제는 모든 프로세스 사이마다 못 쓰게되는 가용 공간을 가질 수 있는데, 이 모든 가용 공간들을 합쳐 하나의 큰 가용 공간으로 만들면 여기에 프로세스를 할당할 수 있습니다. 하지만 많은 비용을 소모합니다.
• 외부 단편화의 문제를 해결할 수 있는 방법은 압축 이라는 방법을 사용할 수 있는데, 이러한 압축은 메모리의 모든 내용을 한쪽으로 몰고 모든 가용 공간을 다른 한군데로 몰아서 큰 불록을 만드는 것입니다. 하지만 이 방법은 재배치가 어셈블 또는 컴파일 시점 메모리 할당 방법에서는 사용할 수 없습니다. 그 이유는 압축이라는 것은 프로세스들의 재배치가 실행 시점에 동적으로 이루어지는 경우에만 가능하기 때문입니다.

    내부 단편화

 

• 내부 단편화란 프로세스가 할당된 공간보다 주어진 공간이 더 큰 경우에 발생하는데, 주어진 공간에 할당된 공간을 채우고 남는 공간이 내부 단편화입니다.
• 내부 단편화가 발생하는 이유는 프로세스가 메모리를 요청하면 할당을 항상 분할된 크기의 정배수로만 해주므로 내부 단편화가 발생하게 됩니다.

 

페이징

---

• 연속 메모리 할당은 앞서 본거처럼 여러가지 문제점을 발생시킵니다. 하지만 페이징은 연속 메모리 할당에서 문제가 되는 단편화와 압축의 문제를 해결할 수 있습니다.

 

💡 기본 방법

 

• 물리 메모리는 프레임이라 불리는 같은 크기의 블록으로 나뉩니다. 
• 논리 메모리는 페이지라 불리는 같은 크기의 블록으로 나뉩니다.
• CPU에서 나오는 모든 논리 주소는 페이지 번호(p)와 페이지 오프셋(d) 두 개의 부분으로 나뉩니다.
• 페이지 번호는 프로세스 페이지 테이블에 접근할 때 사용됩니다.
• 페이지 테이블은 물리 메모리의 각 프레임의 시작 주소를 저장하고 있으며, 오프셋은 프레임안에서의 위치입니다. 따라서 프레임의 시작 주소와 페이지 오프셋이 결합하여 물리 메모리 주소가 됩니다.

과정

    과정

 

1. 논리 주소에서 페이지 번호 p를 추출하여 페이지 테이블의 인덱스로 사용합니다.
2. 페이지 테이블에서 해당 프레임 번호 f를 추출합니다.
3. 페이지 번호 p를 프레임 번호 f로 바꿉니다.
4. 프레임 번호 f를 사용하여 물리 메모리 주소에 존재하는 프레임 f에 접근합니다.
5. 페이지 오프셋을 사용하여 프레임안에서의 인덱스로 사용합니다.

    장점

 

• 페이지들이 연속적으로 메모리가 할당될 필요가 없기 때문에 외부 단편화를 해결할 수 있습니다.
• 공통의 코드를 공유할 수 있습니다. 코드가 재진입 코드인 경우에만 공유할 수 있는데 재진입 코드는 자체 수정할 수 없는 코드로서 실행중에는 절대 변경되지 않습니다. 따라서 두 개 이상의 프로세스가 동일한 코드를 실행할 수 있습니다. 

    단점

 

• 내부 단편화의 문제를 해결할 수 없습니다.
• 페이지 테이블을 저장하기 위해 메모리가 추가로 소모됩니다.
• 메인 메모리에 페이지 테이블을 저장하면 context-switch 속도가 빨라지지만 메모리 엑세스 시간이 느려질 수 있습니다. 예를들어 메모리 i에 접근하기 위해서는 먼저 페이지 번호를 기준으로 페이지 테이블에 접근하게 됩니다. 이때 한번의 메모리 엑세스가 필요하게 됩니다. 이렇게 얻은 프레임 번호와 페이지 오프셋을 결합하여 실제 물리 주소를 얻게되는데 이때 메모리에 접근하기 위해 또 한번의 엑세스가 필요합니다. 이렇게 2번의 메모리 엑세스가 필요하므로 메모리 접근 시간은 2배로 느려지게 됩니다.

    페이지 테이블

 

• 페이지 테이블은 각 프로세스마다 존재하며, 메인 메모리에 상주합니다. 페이지 테이블은 대부분 매우 크기 때문에 이를 구현하기 위해 비용이 비싼 레지스터를 사용하는 것은 적절하지 않습니다. 따라서 페이지 테이블은 메인 메모리에 저장하고 Page-Table Base Register(PTBR)로 하여금 페이지 테이블을 가리키도록 합니다. 만약 context-switch가 발생하는 경우 해당 레지스터의 내용만 변경하면 됩니다.

    페이지 테이블의 보호

 

• 페이지 테이블의 각 엔트리에는 유효/무효 라는 하나의 비트가 더 있습니다. 
• 비트가 유효로 설정되면 관련된 페이지가 프로세스의 합법적인 페이지임을 나타냅니다.
• 비트가 무효로 설정되면 그 페이지는 프로세스의 논리 주소 공간에 속하지 않는다는 것을 의미합니다.
• 운영체제는 이 비트를 사용하여 그 페이지에 대한 접근을 허용할지 말지를 결정할 수 있습니다.

    Translation Look-Aside Buffer(TLB)

 

• 페이징을 사용하면 물리 메모리에 접근하기 위해 2번의 메모리 엑세스가 필요하다는 것을 알게되었습니다. 이러한 상황에서는 지연이 발생하게 되는데 TLB 라고하는 특수한 소형 하드웨어 캐시로 해결할 수 있습니다.
• TLB는 메모리 주소 변환을 위한 별도의 캐시 메모리로, 페이지 테이블에서 빈번히 참조되는 일부 엔트리를 캐싱하고 있습니다.
• TLB는 key-value 쌍으로 데이터를 관리하는 연관 메모리로 구성되며, key에는 페이지 번호가, value에는 프레임 번호가 대응됩니다.
• CPU는 페이지 테이블보다 TLB를 우선적으로 참조하며, 만약 원하는 페이지 번호가 TLB에 있는 경우 바로 프레임 번호를 얻을 수 있지만 그렇지 않은 경우 메인 메모리에 있는 페이지 테이블을 이용하여 얻을 수 있습니다.
• TLB에서 엔트리를 검색할 때 TLB 전체를 다 검색해야하지만 병렬 검색이 가능하므로 검색시간을 줄일 수 있습니다.

 

    TLB에서 Context-Switch

 

• TLB의 각 항목에 ASIDs(Address-space identifiers)이라는 것을 저장합니다. ASID는 TLB 항목이 어느 프로세스에 속한 것인지 알려주며, 그 프로세스의 정보를 보호하기 위해 사용됩니다. TLB에서 논리 주소를 변환할 때 현재 수행중인 프로세스의 ASDI가 TLB 항목에 있는 ASID와 같은지 검사합니다. 만약 일치하지 않으면 TLB 미스로 처리합니다.
• TLB에서 ASID의 지원이 없다면 context-switch가 발생할 때마다 다음 프로세스가 잘 실행될 수 있도록 TLB를 전부 flush해줘야 합니다. 그렇지 않으면 다음에 실행될 프로세스가 이전 프로세스가 사용하던 페이지 번호와 프레임 번호가 남아 무효가 된 주소를 공급해줄 수 있습니다.

 

페이지 테이블의 구조

---

💡 계층적 페이징

 

• 계층적 페이징은 현대 많은 컴퓨터들은 매우 큰 주소 공간을 가지므로 페이지 테이블 또한 용량이 커집니다. 따라서 페이지 테이블 자체가 다시 페이징되도록 하는 것입니다.
• 아래 사진에서 볼 수 있듯이 바깥 페이지 테이블이 있고 바깥 페이지 테이블 내부에는 내부 페이지 테이블을 참조하고 있는 페이지 번호가 있습니다.

https://charles098.tistory.com/108 이미지 참고

💡 해시 페이지 테이블

 

• 해시 페이지 테이블은 계층적 페이징이 32비트보다 커지면 비효율적이기 때문에 해시 페이지 테이블을 사용하지 않을까? 생각합니다.
• 해시 테이블은 연결 리스트 구조이며, 가상 페이지 번호, 매핑 프레임 번호, 연결 리스트의 다음 포인터를 가지고 있습니다.

    과정 

 

1. 페이지 번호(P)를 Hash Function을 사용하여 해싱
2. 해시 테이블에서 연결 리스트를 따라가며 첫 번째 원소와 가상 페이지번호를 비교
3. 일치하면 그에 대응하는 매핑 프레임번호를 가져와 물리적 주소 얻음
4. 일치하지 않으면 리스트의 다음 포인터로 넘어가고 3번의 행위 반복

 

💡 역 페이지 테이블

 

• 보통 프로세스는 자신만의 페이지 테이블을 가지고, 또 페이지 테이블은 프로세스가 사용하는 페이지마다 하나의 항목을 가지게 되는데 이는 페이지 테이블의 항목 개수가 점점 많아질 수 있습니다. 이 문제를 해결할 수 있는 방법이 역 페이지 테이블입니다.
• 역 페이지 테이블은 메모리에 하나의 페이지 테이블만 두는 방법입니다. 모든 프로세스는 하나의 페이지 테이블만을 참조합니다. 따라서 페이지 테이블의 엔트리 개수는 메모리 프레임 수와 같습니다.

    과정 

 

1. 가상주소는 <PID, page-number, offset>으로 구성되어 있습니다.
2. 역 페이지 테이블의 항목은 PID와 page-number로 구성되어 있으며, PID는 주소 공간의 ID 역할을 수행합니다.
3. 메모리 참조가 발생하면 PID, page-number의 쌍으로 이루어진 가상 주소의 일부가 메모리 하부 시스템으로 전달됩니다.
4. 역 페이지 테이블에서 일치하는 것이 있는지 탐색합니다.
5. 일치하는 것이 i번째 엔트리에서 발견되면 물리 주소는 <i, offset>이 되고, 일치하는게 없으면 잘못된 메모리로 간주합니다.

    장점

 

• 각 프로세스마다 페이지 테이블이 형성되는게 아닌 메모리에 하나의 페이지 테이블을 둠으로써 메모리를 적게 소모할 수 있습니다.

    단점 

 

• 역 페이지 테이블에서 주소를 검색하는 경우는 빈번히 발생하므로 최악의 경우 모든 페이지 테이블을 검색해야 하는데 이러한 경우 오버헤드가 크게 발생하게 됩니다. 
• 메모리에 하나의 페이지 테이블만 있으므로 프로세스간 메모리 공유가 불가능합니다. 같은 프로세스 내부에서도 페이지가 다르면 데이터 공유가 불가능한 상황이 발생합니다.

 

 

참고자료

• https://techblog-history-younghunjo1.tistory.com/511
• https://rebro.kr/178
• https://charles098.tistory.com/108
• https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=sqlmvp&logNo=140191559473