운영체제 (7) - Memory Management
2024년 1학기 운영체제 수업을 듣고 정리한 내용입니다. 수업 교재는 운영체제 - 내부구조 및 설계원리 8 판입니다.
Memory management
메인 메모리만 사용하는 시스템에서는 메모리 공간을 나누어 각 프로세스가 작업을 한다. 낭비되는 공간이 없도록 잘 나누어 사용해야 메모리에 많은 프로세스를 올려서 작업할 수 있다.
메모리를 나누어 관리할 때 OS는 3가지 작업을 하게 된다.
Relocation
프로세스가 메모리에 올라가기 전에 프로그램이 OS에 의해 컴파일되는데, 이 때 분기 명령어와 같이 다른 메모리의 주소로 jump하는 명령어를 컴파일하려면 메모리의 주소를 알아야 한다. 컴파일 시기에는 이 프로그램이 실제 메모리의 어떤 위치로 올라갈지 알 수 없으므로 Program의 시작 부분을 0번지(상대 주소)로 하여 컴파일한다. 그리고 실제로 메모리에 올라갈 때에는 명령어의 값을 프로그램이 올라갈 메모리의 위치 + 명령어의 상대 주소로 바꾸게 되는데 이게 Relocation이다.
Protection
Relocation을 거쳐서 메모리에 올라간 프로세스가 실행중에 다른 프로세스의 영역 또는 이상한 메모리를 참조하려고 하는지 확인해야하므로 허용된 메모리 영역의 경계를 알고 있어야 한다. Protection은 메모리에 프로세스가 올라갈 때 할당된 공간의 범위를 기억함으로 실행중에 잘못된 참조를 검사할 수 있도록 한다.
Sharing
OS가 여러 프로세스들이 허용된 메모리 공간을 공유하도록 하는 것이다.
Partitioning
메모리에 프로세스를 올리기 위해 프로세스가 들어갈 공간을 나눈다.
Fixed Partitioning
Equal-size partitions
고정된 크기로 메모리를 나누기 때문에 각 메모리 공간마다 시작 번지가 정해지게 된다. 따라서 Relocation을 하지 않는다. 프로세스 크기가 클 경우 제일 큰 프로세스를 기준으로 나누게 되어 공간낭비가 된다.
Unequal-size partitions
메모리 공간을 미리 나누되 각각 다른 크기로 나누고 그 공간에 프로세스를 올린다. 프로세스 크기가 대부분 8M 이상이라면 2M, 4M, 6M에는 프로세스를 올릴 수 없으므로 공간이 낭비되고, 12M, 16M과 같이 큰 공간에는 내부에 빈 공간이 생긴다(Internal fragmentation).
Dynamic Partitioning
프로세스 크기에 맞춰 메모리 공간을 나눈다. 메모리 공간을 낭비하지 않게 되겠지만 동적으로 자르기 때문에 실행중에 프로세스 사이에 빈 공간이 계속 생기게 된다(External fragmentation). 조각 모음처럼 프로세스의 위치를 이동시켜 메모리 공간을 확보할 수 있지만(Compaction), 실행중에 처리를 하는 것이 굉장히 오래 걸리므로 시스템이 멈추게 된다.
(a)부터 (d)까지는 동적으로 메모리 공간을 잘라 프로세스를 올린 모습이다. 그러나 프로세스 2가 실행을 마치고 공간을 반납하게 되면 (e)와 같이 14M 공간이 프로세스 사이에 생긴다. 14M보다 큰 프로세스를 그 공간에는 올릴 수 없기 때문에 크기가 작은 프로세스가 그 사이에 들어가게 된다. 프로세스 1이 실행을 마치고 나간 자리에 프로세스 2가 다시 올라오게 된다면 (h)처럼 프로세스 사이마다 빈 공간이 생기게 된다. 이 문제를 External fragmentation이라고 한다.
Dynamic Partitioning Placement Algorithm
빈 공간이 생기는 문제를 막을 수는 없기 때문에, 어떤 공간에 프로세스를 올릴 것인가가 중요해졌다.
Best-fit
빈 공간에 프로세스를 올렸을 때 남은 공간이 제일 작은 위치에 프로세스를 올린다. 그러나 작은 공간이 많이 생기면 전체를 탐색해야 한다.
First-fit
가능한 공간 중 제일 처음 탐색한 공간에 프로세스를 올린다. 탐색 시간이 짧지만 뒤쪽 공간은 잘 활용하지 못한다.
Next-fit
마지막에 배치한 위치에서 탐색을 시작하여 처음 찾은 공간에 프로세스를 올린다. 시스템 전체 공간을 활용하고 First-fit보다 탐색 시간이 빠르다.
Worst-fit
빈 공간이 가장 큰 곳을 찾아 그곳에 프로세스를 올린다. 이 방법은 남는 공간이 항상 크게 생기기 때문에 작은 공간이 여러 개 생기는 것을 방지한다.
Buddy System
Dynamic하게 고정된 공간을 할당한다. 메모리를 항상 반으로 쪼개 적절한 공간을 마련하고 그곳에 프로세스를 올린다. 이렇게 하면 메모리 공간이 항상 $2^U$꼴로 나타난다. 프로세스 크기가 $S$일 때 적절한 공간은 $2^{U-1}<S<2^U$인 공간이다.
메모리의 크기가 1MB인 시스템에서 100KB의 크기인 프로세스를 요청한다면, 100KB가 들어갈 수 있는 최적의 공간은 128KB이다. 따라서 1M을 쪼개서 512KB를 만들고, 512KB를 쪼개서 256KB를 만들고, 256KB를 쪼개서 128KB를 만든 후 그 곳에 100KB 프로세스를 올린다. 28KB정도 공간이 낭비되는 문제(Internal fragmentation)이 발생한다.
프로세스의 크기가 64KB일 때에는 128KB를 쪼개 64KB 공간을 만들고 그곳에 프로세스를 올린다. 이 때 64KB 공간에 올린 프로세스가 종료되어 공간을 반납한다면, 같은 공간에 있었지만 쪼개져서 64KB가 된 공간과 합쳐져서 128KB공간이 된다. 위 사진에서 Release C를 보면 64KB가 나가면서 자기 친구였던 다른 64KB와 합쳐진 모습을 볼 수 있다. Release E를 보면 128KB가 반납되면서 옆의 128KB와 합쳐지고, 합쳐진 256KB 공간이 바로 옆의 256KB와 합쳐지면서 512KB가 된 모습을 볼 수 있다. 그래서 'Buddy' System인 이름으로 불리게 되었다.
Addresses
3가지 종류의 주소가 있다.
Logical
페이지 테이블이나 세그먼트 테이블의 엔트리를 의미하는 주소다. 테이블은 실제 메모리를 가리키거나 다른 테이블의 주소를 가리키고 있기 때문에, 테이블을 가리키는 논리적 주소는 처리를 거쳐서 물리적 주소가 된다.
Relative
프로그램의 시작을 0번지로 하여 상대적으로 계산된 주소다. Relocation을 거쳐서 물리적 주소가 된다.
Physical
실제 메모리를 가리키는 주소다.
Relative address를 Physical address로 바꾸는 과정은 이렇다. 먼저 Relative address가 주어지면 프로세스의 Base Register를 더해 Physical address로 변환한다. Base Register는 프로그램이 들어간 메모리의 주소다.
Physical address가 되었지만 이 주소가 허용된 영역을 참조하는지 확인하기 위해 Bound Register값과 비교한다. 이 과정은 Protection이다. Bound Register 역시 프로그램이 컴파일 된 후에 Base Register와 함께 값이 생성된다.
Q. 시스템에서 Base, Bound 레지스터는 몇 개?
프로세스가 100개면 각 프로세스마다 Base값과 Bound값이 생긴다. 그러나 CPU의 모든 레지스터에 값을 등록하는게 아니라 각 프로세스마다 저장해두고, Relocation이 일어날 때마다 프로세스 내에 저장된 값을 업데이트하면 된다. 실제 실행될 때는 프로세스에 저장된 값을 CPU로 불러오게 된다.
Paging
위에서 살펴본 Relative Address를 Physical Address로 변환하는 작업은 프로세스가 메모리에 올라갈 때 연속된 공간에 할당되어야만 가능하다. Partitioning은 프로세스 사이에 빈 공간이 생기는 문제가 있기 때문에, 빈 공간을 모두 활용하기 위해 프로그램을 쪼개게 되었다. 즉, 연속되지 않은 공간에 프로그램을 올리기 때문에 주소를 변환하는 방법이 달라져야 한다.
프로그램을 쪼갤 때 크기가 다양하다면 골치아프기 때문에 고정된 크기(Frame)로 자른다. 프레임 크기에 맞춰 자른 프로세스의 한 조각을 Page라고 부른다. 프로세스는 여러 페이지로 쪼개져 메모리로 올라가게 되는데, 쪼개진 페이지가 메모리 이곳저곳에 퍼져있으므로 페이지가 올라간 프레임의 주소를 기억해야한다. 어느 프레임에 올라가 있는지만 안다면 프레임의 주소와 오프셋값을 통해 Physical address를 얻을 수 있다. 그러므로 프레임의 주소를 담고 있는 별도의 테이블이 필요한데 이것을 페이지 테이블이라고 한다.
페이징 시스템에서 실제 물리적 주소를 얻기 위해 사용하는 주소는 Logical address다. Logical address의 길이가 16비트인것은, 이 시스템의 메모리 길이가 $2^{16}$이라는 것을 뜻한다. Logical address에는 페이지 테이블의 인덱스와 오프셋이 들어 있다. page 비트 수가 6비트라는 것은 프로그램 안에서 가능한 최대 페이지 수가 $2^6$임을 뜻한다. 즉, 프레임이 $2^6$개 존재한다는 말이고, 메모리 길이가 $2^{16}$이므로 $2^{16}\div2^6=2^{10}$이 되기 때문에 한 프레임의 길이가 $2^{10}$이다. 다시 말해 오프셋의 비트가 10비트라는 것이다.
Physical address로 변환되기 위해서는 먼저 페이지 테이블의 인덱스값으로 테이블을 조회하여 프레임 번호를 획득한다. 그리고 프레임 번호 << 오프셋 비트 수를 계산한 후 오프셋을 더해 변환한다. 인덱스값이 1일 때 테이블에서 000110값을 얻게 되고, 000110 << 10을 하면 0001100000000000이 된다. 여기에 오프셋 값을 더하면 0001100111011110이 되어 물리적 주소를 얻게 된다.
페이징 시스템에서는 Protection할 때 페이지 번호만 신경쓰면 된다. 오프셋값을 더했을 때 잘못된 메모리 참조가 일어나려면 다른 메모리를 가리켜야 한다. 하지만 오프셋의 크기가 페이지의 크기를 벗어날 수 없기 때문에 (페이지 길이와 오프셋의 길이가 같으므로) 페이지 번호만 신경쓰면 된다.
Segmentation
페이징 시스템에서 배열이나 함수가 두 페이지에 걸쳐 있다면 두 페이지를 모두 메모리에 상주시켜야 하는데 뒷 페이지가 작은 공간만 차지할 경우 Internal fragmentation이 일어나 낭비가 될 수 있다.
세그먼트 시스템에서는 프로그램을 고정된 크기로 자르지 않고 논리적 단위로 자른다. 당연히 자른 프로그램마다 길이가 다르므로 External fragmentation이 발생하게 된다. 그러나 작은 크기의 세그먼트들을 그 공간에 집어 넣음으로 최대한 Compaction을 하지 않도록 한다.
세그먼트 역시 세그먼트들이 메모리에서 어떤 위치에 올라가 있는지 알기 위한 세그먼트 테이블이 존재한다. 페이지 테이블과는 다르게 세그먼트 테이블은 세그먼트의 길이(Length)와 세그먼트의 시작 주소(Base)로 구성되어 있다. 메모리 길이가 $2^{16}$인데, Length값과 Base값을 모두 담기 위해 테이블의 길이가 메모리 길이보다 길어지게 된다.
Logical address은 페이징 시스템과 똑같이 세그먼트 테이블 인덱스, 오프셋값을 갖고 있다. 세그먼트 테이블 인덱스를 통해 Length와 Base값을 얻게 되면 Base값과 오프셋값을 더해 Physical address를 만들게 된다. 여기서 오프셋값이 메모리를 잘못 참조하는지 확인하기 위해서 Length가 사용된다. 세그먼트 시스템에서 Protection은 오프셋이 Length보다 큰지 확인하는 것이다.