CPU의 활용률을 극대화 하며, 사용자에게 빠른 응답을 제공해야 하기 때문에(여러 프로세스를 동시에 실행가능하게 된 Multi-programming때 부터 특히) 한정된 Memory의 관리에 대한 필요성이 대두되었다.
1. 주소
주소 공간(Address space)는 Process에서 참조할 수 있는 주소들의 범위로, Process와 1:1로 매핑된다. 이 주소 공간의 크기는 Address Bus(HW간의 Address를 주고받는 통로)의 크기에 의해 결정되는데, 가령 이 크기가 32bit라면 0~(2^32)-1의 범위를 가질 것이다.
주소는 실제 물리 주소(PM)와 프로세스 관점의 가상 주소(VM)로 나뉘게 된다. CPU관점의 주소는 물리 주소도, 가상 주소도 될 수 있는데 VM이 PM과 어떻게 매핑되냐에 따라 달라지기 때문이다(만약 1:1로 매핑되면 PM을 사용하는 것과 같다). 이제 어떻게 컴퓨터의 메모리 매핑 방식이 발전했는지 확인해보자.
2. 단계별 주소 관리
2-1. 초창기
초창기에는 고정적으로 사용할 물리 주소를 Compile time에 생성하고, 이 주소를 직접 접근하여 메모리를 사용하는 방식을 채택했었다. 이 방식은 컴파일이 다시 되지 않는 이상 변하지 않으며, 변화를 주기 위해서는 다시 컴파일 하는 수 밖에 없었다. 이 방법은 한번에 실행하는 프로세스의 갯수가 많아짐에 따라 Compile time에 물리주소를 정하기 어려워짐에 따라 사장되었고, 가상 주소(VM)를 생성하는 방식으로 발전하기 시작하였다.
2-2 단계 별 메모리 결정 방법
프로그램 실행 전반에 걸쳐 주소가 결정될 수 있다. 결론적으로 현대에는 Execution time에 주로 결정되지만 각 단계에서 어떻게 결정되는지 알아보자. 우선 주소 결정 단계를 알아보기 위해서 아래의 프로그램 실행 순서와 그 단계를 부르는 이름에 대해서 알아보자
이제 어단계 별 주소 결정 방법에 대해 알아보자
- Compile time : Compiler가 symbol table을 만들고 주소가 symbol table relative한 주소로 기록됨 즉, Symbol table로 얼마나 떨어져있는지 명시된다(Compile된 Object 파일은 주소 0부터 시작한다! -> Relocatable하게 만들어 진다)
- Link time : Object파일과 System에서 제공하는 Library들을 묶어서 Symbol table에 의존적이지 않은 주소를 만들어 낸다. 즉, Link 결과로 하나의 Executable파일이 만들어진 주소는 0번째 주소부터 시작된다
- Load time : 이 단계부터 PM을 함께 고려해야한다. Program의 실행을 위해 Loader는 Executable을 Memory로 load한다. 이때 VM이 어떤 PM과 연결될 지 Binding한다. (시작 주소를 바꾸려면 다시 Load해야함!) 이전에 생성한 프로그램이 Relocatable주소로 되어 있기 때문에 Base register를 통해 물리 주소로 바뀐다.
- Execution time
Process가 실행될 때 물리 주소가 바뀌는 경우 즉, Paging, Swapping에 의해 바뀔 때에 대한 주소결정 메카니즘이다(현대의 대부분 운영체제가 이렇게 작동한다). 이때 물리 주소에 대한 Binding이 Process가 실행될 때 일어난다. 이러한 방식의 구현을 위해 MMU와 같은 특별한 하드웨어가 필요하게 된다.
3. CPU에서 사용하는 주소에 따른 변환 방법
3-1. CPU에서 Physical relative address를 사용
Program 내 instruction들의 주소를 시작주소(Base address)로 부터의 상대적인 Offset으로 표현하는 방법을 사용한다. 그런데 그 Base address가 고정되어서 relocate가 불가능하므로 매우 비효율적이다.
3-2. CPU에서 Virtual address를 사용
MMU를 활용한 자유로운 Translation을 사용한다. 다만 이 Translation의 속도가 매우 중요해진다.
여기서 MMU는 CPU로 부터 받은 VA를 PA로 변환(Translate)하는 역할을 한다
4. Virtual memory
4-1. VM의 정의와 오버뷰
실제 존재하진 않지만 사용자에게 Memory로서의 역할을 하는 Memory이다. 모든 프로그램의 모든 메모리가 다 올라갈 필요가 없다. 따라서 필요에 따라 나눠서 적재함으로써 전체 시스템의 성능을 올려보자는 아이디어이다. 이제부터 어떻게 구현될 지 알아보자. VM은 다음과 같이 구현된다
여기서 Table에 대해서 알아보자. 이 Table의 VM과 PM의 매핑 상태를 저장하는 테이블이다.
이제 각 Table의 원소가 가리키는 것(Page)이 무엇을 나타내고, 어떤 메카니즘을 갖는지 알아보자.
4-2. Paging
주소 공간을 동일한 크기인 Page로 나누어 관리하는 방식이다. 그리고 이렇게 나누어진 Page를 단위로 메모리에 올라가고 내려가게 된다. 실험적으로 효율성을 따져본 결과에 기반하여 Page 크기는 보통 4KB 이다. 여기서 Page는 특히 VM의 단위이고, Frame은 PM의 단위이다. (명명만 다를 뿐 사이즈는 같다) 그리고, Page가 하나의 Frame을 할당받으면 물리 Memory에 위치하게 된다. 이때 Frame을 할당 받지 못한 Page들은 HDD와 같은 외부 장치(Backing storage)에 Page 혹은 Frame과 같은 크기로 나누어져 있다.
이제 운영체제가 이렇게 Page단위로 실제 0과 1로 나타난 데이터에 접근할까? CPU가 VM을 기준으로 접근할 때, 운영체제는 그 VM과 매핑된 페이지를 찾는다. 이때 그 Page가 존재하는 번호를 Page번호라고 한다. 그리고 그 Page내에서 CPU가 접근하고자 하는 주소를 참조하기 위해서 Page의 내부주소를 저장하는 Page주소를 이용한다. 따라서 다음과 같은 형태로 접근 가능하다.
5. 여러 Paging 기법
5-1. 초기
이제 Page 정보를 저장하는 Page table을 알아보자. Page table은 물리 Memory에 위치한다. 왜냐하면 CPU가 PM의 접근 전에 VM을 PM으로 변환해야 하기 때문에 VM으로 접근할 수 없기 때문이다. 그렇다면 어떻게 접근하는가? 라고 하면 이는 특수한 레지스터들(위치 정보 : PTLR[Page Table Base Register] / 길이 정보 : PTLR[Page Table Length Register])로 접근 가능하다.
이때 데이터가 저장된 Page table의 인덱스가 아까전에 보았던 Page number인 것이다. 이제 실제로 어떻게 PM으로 매핑되는지 확인해보자!
뒤의 4KB는 Page address이고, 앞의 부분은 Page로, Page table로 실제 매핑된 PM의 Frame와 Page address를 참조하여 실제 PM에 저장덴 데이터를 찾을 수 있다.
이제 각 Page table의 Entry에 어떠한 정보가 저장되는지 확인해보자 1) Page에 할당된 Frame의 시작주소를 저장하는 Page Base Address 2) Flag bits들이 저장된다. Flag에는 접근 확인(Access bit), 내용 변경(Dirty bit), 할당 여부(Present bit), 권한(Read/Write bit)이 저장된다.
5-2. Translation Look-aside Buffer (TLB)
위 알고리즘에서는 반드시 메모리에 대한 접근이 2번(Page table에서 한번, 실제 데이터 찾을 때 한번) 발생한다. 이것이 너무 느리다는 문제 때문에 Register에 저장된 Table 혹은 Buffer(TLB)의 참조하여 속도를 올리자는 것이다. VM을 PM으로 바꾸 기 전에 Page table에 바로 접근하지 않고 Page number와 Frame number가 매핑된 버퍼(TLB)를 먼저 확인하고, 만약 존재한다면(TLB Hit한다면) 그 Frame number를 바로 이용하여 메모리에 접근한다.(따라서 메모리에 한번만 접근) 만약 존재하지 않는다면 (TLB Miss한다면) 이전과 같은 방식으로 접근한다. 여기서 TLB가 Hit 할 수 있는 확률(혹은 비율)을 TLB Hit Ration라고 한다.
5-3. Multilevel Page Table
System이 발전할 수록 가상 주소 공간이 넓어지고 이는 Page의 갯수의 증가로 이어지며, 이는 Page table 크기의 증가를 야기한다. 예를 들어 32bit 크기의 가상주소를 갖는 system에서는 Page 크기 : 4KB(2^12) / Page table 크기 : 1M(2^{32-12=20}) * 4B(일반적으로 4B를 차지) = 4MB이다. 이는 위에서 Page address와 page number 계산하던 방식을 떠올리면 쉽게 이해된다. 게다가 이 table은 process갯수만큼 생기므로, 실행 Process가 많으면 공간차지는 극대화 된다. 따라서 PM의 공간이 낭비된다어 Page의 Page table의 level을 세분화 함으로써 크기를 줄이고자 하는 방식이 Multilevel Page Table이다. 어떻게 Page table을 세분화 할까?
이는 Page table에 대한 Page table을 만듦으로써 해결할 수 있다
하지만 이 해결방법은 Table 참조 횟수가 늘어나기 때문에 Table walk에 걸리는 시간이 증가한다는 단점이 있다.
5-4. Inverted Page Table
32bit 시스템에서는 그렇다 쳐도 64bit 시스템에서는 위의 방법들을 활용이 적합할까? 표현해야할 정보가 너무 커져 이것이 꺼려졌다. 그래서 PM은 증가하지 않았다는 점에서 착안하여 VM -> PM으로의 매핑이 아니라, PM -> VM으로 치환하였다. 즉, 다음과 같이 표현할 수 있다
이처럼 System 전체에 하나의 Page table만 두고, Page table 내의 Page ID검색을 통해 매핑하는 방식이다. 메모리의 효율성은 높아졌지만, Page ID search에 시간이 증가하여 속도 측면에서 문제가 생겼다 (해쉬테이블을 사용하여 단축하더라도 느리다)
5-5. Demand Paging
현대에 널리 사용되는 방식이다. 필요한 Page의 요청이 발생할 때 메모리에 올리는 Paging방식이다. 만약 필요로 하지 않는 Page는 Secondary storage안에 이동한다. 필요의 여부를 확인하기 위해 flag로 Valid와 Invalid Page를 나눈다. 이렇게 하면 실행을 위한 물리 Memory 구성 시간이 줄어든다. 왜냐하면 위의 이전 알고리즘들과 같이 메모리에 로드된 페이지가 확정적으로 존재하는 것이 아닌, 필요에 의해 로드, 해제를 반복하므로 실행을 위한 Memory 구성에 대해 고려할 사항이 적어지기 때문이다. 그리고 필요한 것만 올림으로써 Memory의 양이 줄어든다.
참조하는 Page가 Valid한 경우, 바로 Table참조를 통해 PM에 접근하면 되고 Invalid한 경우, Page fault를 발생시켜 필요한 것을 PM에 로드한 후 접근한다.
Page fault를 어떻게 처리할까? 이는 Page fault handler가 수행하는데(동기적 이벤트, 프로세스의 실행을 멈춘다), 새로운 Frame을 할당받고, Backing storage에서 Page내용을 다시 Frame에 불러들이고 Page table을 재구성하고, Process의 작업을 재시작한다.
Page fault는 실행 중지를 야기하므로 실행 속도에 악영향을 미친다. 때문에 이를 줄이고자 실험을 해보았는데, Page-fault발생 빈도는 프레임의 개수와 반비례한다는 결론을 도출하였다. 이러한 실험을 바탕으로 결정한 것이 Page갯수와 크기이다.
실험을 하면서 알게된 사실은 Page fault는 특정 시간대에 사용하는 Page가 집중되어 있다는 것이다. 즉 Page fault는 Locality한 특성을 갖는다는 것을 알게되었다.
이러한 특성을 가지고 Fage fault를 낮출 수 있다. 아래의 특이 케이스는 비디오와 같은 경우이다. 이러한 경향성을 바탕으로 성능을 올리기 위해 Working set을 이용한다. working set은 일정 window 시간 동안 접근한 Page들의 집합을 의미하는데, 이 window 시간이 적당하면 Working set이 Locality를 나타내어 전체 시스템 성능 향상에 도움이 된다고 한다.
하지만 적당히 잡지 못하여 Page fault가 Execution시간보다 큰 Thrashing이 발생한다면 이를 잡아줘야 한다고 한다.