운영체제 8장. Virtual Memory


앞으로 더 큰 메모리가 필요할것


앞에서 메모리 관리를 위해 필요한 요구사항을 알아봤다
물리 메모리에 재배치
논리적인 주소체계 관리
물리적 주소로 맵핑하는 문제
protection
sharing

그리고 여기서는 무한대의 메모리를 사용할수 있게 프로그램에 제공하는것에 대해 알아보자


memory management에서 중요한 두가지 특징
모든 메모리의 참조 - 프로그래머가 생각하는 모든 메모리 참조는 논리 메모리
이것을 수행시간 안에 물리 메모리로 변환할 필요가 있다

프로세스를 연속적이지 않은 메모리 덩어리로 나누어서 메모리에 넣고 실행시키는것이 필요

이런 상황에서 메모리에 실행중인 모든 프로그램이 들어갈수는 없다.
이 두개 특성이 만족된다면 페이지나 세그멘트가 모두 메인 메모리에 있을 필요는 없다
필요하면 가져오고, 필요없으면 세컨더리 스토리지에 넣는 방법이 필요
프로그래머 말고 운영체제가 해결하고자 한다


용어
버츄얼 메모리 - 메모리를 할당하는 방법, 세컨더리 스토리지를 프라이머리 메모리와 같이 프로그램에서 자동으로 접근할수 있도록 해주는 기억장치이다. 만약 발생한 주소가 메인메모리에 없는 기억장소를 가리킨다면. 그것을 자동으로 운영체제에 의해서 메인메모리로 가져오게 하는 방법을 만든것. 모든 주소는 실행시간 내에 물리주소로 번역되어, 그것이 메인메모리에 없다면, 세컨더리 스토리지의 주소를 번역해서 가져오도록 확장. 사실상 거의 크기 제한이 없다. 컴퓨터 시스템 내 번역하는 테이블 크기와, 보조기억장치의 크기에 의해 결정된다. 단점은 세컨더리 스토리지에 접근하기에 느려진다는것.
virtual address space - 프로그래머가 보는 프로세스의 주소공간, 그 주소공간은 무한정으로 커지게 된다
address space - 한 프로세스가 사용할수 있는 주소공간
real address에 대해서 address space라는 용어를 사용



한 프로세스가 실행되기 위해서는
운영체제는 메인메모리로 프로그램의 조각을 가져오고 실행시작
메인메모리에 들어있는 프로세스의 조각들을 resident set이라고 부름
만약 프로그램이 실행되다가 메인메모리에 없다는게 발견되면 interrupt 발생되고, 그 프로세스를 블록상태로 만든다.

메인메모리에 없는 프로그램의 덩어리를 가져오기 위해서, 거기에 해당되는 논리주소가 접근이 되면 disk i/o를 발생
해당 프로세스는 블록이 되고, 다른 프로세스가 dispatch 되어 cpu를 차지하고 실행
disk io가 끝나면 인터럽트를 다시 발생시켜서, os는 해당되는 메모리 블록을 메인 메모리에 집어넣었다는걸 PCB의 페이지(세그멘트) 맵핑 테이블 에 집어넣고,
그 프로세스를 ready 상태로 만든다

ready상태가 되었기 때문에 그 프로세스는 중단된적이 없었던것처럼 다시 다음차례에 cpu를 할당받고 실행된다. 언제 cpu를 할당받는지는 cpu의 디스패쳐에 의해 결정


이렇게 해서 더 많은 프로세스가 메인메모리에 들어올수 있고
프로세스는 메인메모리보다 더 큰 공간을 사용가능

프로세스의 개수를 증가시킬수 있고, 각 프로세스마다 부분적인 로딩을 해서 실행하게 된다
메인메모리에 들어와있는 프로세스 개수가 많아지고 ready 상태의 프로세스가 더 많아진다


앞장에서 real memory, RAM을 사용해서 메모리 할당하는 방법에 대해서 알아봤다
이제 virtual memory까지 포함하여 멀티프로그래밍 할수있고, 메인메모리의 크기에 의해 한정되는 프로그래머의 어려움을 해결했다.


simple paging - 메인메모리를 작은 사이즈의 메모리 덩어리(페이지 프레임)로 나누고, 프로그램을 페이지 단위로 나눠서 사상시키는 테이블을 가짐으로서 프로그램을 실행하는 방법 
virtual memory paging - 세컨더리 스토리지를 사용해서 메모리 공간을 늘리는 방법 소개
simple segmentation - protection, sharing 을 위해서 논리적 단위로 프로그램을 나누고, 그 단위로 메모리에 로딩해서 프로그램을 실행하는것 
virtual memory segmentation - 세컨더리 스토리지를 사용해서 세그먼트들을 내보내고 가져와서 멀티프로그래밍 정도를 높이고, 레디 상태의 프로세서를 늘리고, 프로그래머가 사용할수 있는 주소공간 크기의 한계를 없앰 

궁극적으로 무한대의 메모리를 제공


그러나 단점이 있다, 세컨더리 스토리지를 사용하므로 swaping process 발생, swaping 시 io interrupt발생, 상대적으로 느린 디스크나 ssd에 접근하므로 이에 시간 많이 소모
결국 locality가 맞지 않으면 전체 cpu시간중 IO interrupt 시간이 커진다. 이것을 Thrashing 이라고 함


일종의 캐시 시스템처럼 동작하므로 이것도 locality가 중요
머신러닝을 생각해보면 큰 행렬연산 - 계산이 집중, 두 연산 operand에 집중적으로 접근, 한번 계산시 계산이 집중된다는 추측이 가능 
locality에 해당되는 메모리의 크기만큼 real memory가 존재시 thrashing을 피할수 있다
반대로 그것보다 적은 메모리를 사용하면, virtual memory 사용시 thrashing 발생 


프로그램을 실행시키면서 페이징이 어떻게 발생되는지
memory access가 집중되는것을 보여준다.
전체적으로 골고루 접근이 일어나지 않으므로 locality가 있다고 볼수 있다.


이것을 활용하면 아주 큰 용량의 메모리를 저렴한 비용으로 만들수 있다, 캐시와 같은 원리
페이징과 세그멘테이션을 위해서는 실시간의 주소변환이 필요하므로 HW가 필요
OS는 테이블을 채워주고, 세컨더리 스토리지를 할당해주고 필요시 인터럽트를 처리해서 메인메모리로 가져오고, 메인메모리에서 업데이트된 변수같은 메모리의 내용을 세컨더리 스토리지로 내보내고 이런 동작이 필요하다
이걸 관리하기 위한 자료구조와 프로시져가 운영체제에 작성되어야 한다.


페이징 - 버츄얼 메모리 제공을 위해서 
각 프로세스가 페이지 테이블을 가지게 된다

프로그램을 페이지 단위로 나누고, 페이지 프레임 단위로 메인메모리를 나눠서 그 사이에 맵핑해서 가상주소를 실제주소로 변환했었다.


페이지 테이블에서
인덱스를 주면 프레임넘버를 가지고 있다, 실제 메모리 안에서 어떤 프레임에 존재하는지 내용이 들어있다.
이때 인덱스를 구하는법이 page number

0이 있다면 테이블 엔트리를 찾아서 프레임 넘버를 꺼내고, 오프셋을 붙여서 주소를 만든것이 real address였다.


논리주소가 주어지면 
앞부분의 페이지넘버를 잘라서 prefix로 해서 
페이지 테이블의 시작점 가리키는 레지스터의 값, 포인터와 더해서 인덱스로 엔트리를 찾음(일종의 배열)
여기서 프레임 넘버를 꺼내서 offset을 붙여서 물리주소를 만들고 그 주소를 내보내서 메모리에 접근

이것이 1클럭에 이루어진다, HW
os가 할 일은 페이지 테이블을 채워주는것


이러한 페이지 맵핑 테이블을 만들면
전체 주소 공간에 대해 테이블을 갖고 있어야 하므로 페이지 엔트리가 많아진다 
그것이 차지하는 메모리만 해도 양이 많아진다

이것을 계층을 나누어서 해결한다
전체중 필요없는 부분은 맵핑 테이블을 만들지 않는것. 중간중간 비는 부분이 생기게 된다. 그렇게 해서 필요한 메모리공간을 줄인다.


논리주소의 앞부분을 둘로 나누고
각각을 인덱스로 쓴다
첫번째 테이블의 시작점을 가리키는 레지스터를 더해서
테이블 엔트리를 찾는다.
이것이 두번째 테이블의 시작점을 가리키게 되고 
두번째를 더해서 두번째 테이블 엔트리를 찾는다
여기에 프레임 넘버가 있고, offset을 붙여서 real address를 만든다

이런 테이블이 프로세스당 하나씩 생기게 된다.
그 다음 계층은 그 하나당 각각...100개면 10000개 이런식으로
메인메모리 해당되는 만큼의 메모리가 필요...
이 원인은 프로세스당 테이블을 만든것이 문제
전체 메모리를 가지고 테이블을 만들고, 프로세스에게 나눠주자.
-> inverted page table


나눠주는 방법은
페이지 넘버 부분을 하드웨어 hashing을 사용해서 특정 entry를 가리키게 하고 그 엔트리가 inverted page table이 된다.
그 inverted page table은 하나의 real memory에 연결되어 있는것
그러면 주소변환을 위해 각 프로세스당 inverted page table의 entry만 가지고 있으면 주소변환 가능 


페이지가 있으면
페이지넘버로 해싱을 해서 엔트리를 찾고 거기에 페이지가 속한 프로세스의 id를 갖게 된다
그럴때 해시에서 링크드리스트를 사용해서(chained hash를 HW로 만들어서), 해싱 함수가 완전히 1:1이 되지 못하므로(커다란 주소공간이 제약된 주소공간으로 맵핑하므로), 그 엔트리가 이 페이지가 아니라면 링크를 따라가서 찾게된다 
결국 찾게된 페이지넘버에 대한 프레임 넘버를 꺼내서 오프셋을 붙이고 이것을 real address로 사용

프로세스당 페이지 테이블이 아니고
전체 메모리에 대해 해쉬 테이블을 가지고 있다가 그것을 사용해서 프레임 넘버를 찾도록 함


자료구조를 보면 각 엔트리에 대해
페이지 넘버에 대해 
프로세스 id와 컨트롤비트(protection,locking에 사용), 충돌 생길시 연결점을 만드는 체인 포인터로 구성


페이지테이블 자체가 메모리에 저장되면
테이블이 2계층이면 3번 메모리에 접근해야 한다, 메모리 접근 속도가 상대적으로 느림
이 주소번역에 대한 캐쉬를 만들게 되었다. (TLB)

버츄얼 메모리는 1회 메모리 접근을 위해 2회 메모리 엑세스
1은 페이지 테이블 엔트리를 가져오기 위해, 2는 실제 데이터 fetch위해서

이것을 극복하고자 TLB를 만듦, 일종의 cpu 안에 내장된 고속의 캐쉬


페이지 넘버를 가지고 TLB 버퍼 검색(동시에 검색)
엔트리를 찾게되면 그것을 가지고 프레임 넘버에 오프셋을 붙여서 실제주소를 만든다
만약 real memory에 존재하지 않는다면 세컨더리 스토리지에 가서 그것을 real memory에 옮겨놓고 그 다음에 동작하게 된다.


TLB operation 중요하다
페이징과 TLB이용해서 주소변환, 버츄얼메모리의 핵심동작

instruction 시작
cpu가 TLB체크, 있다면 그걸로 물리주소 만듦
없다면 페이지 테이블 접근해서
페이지 테이블이 메인메모리에 있다면
그 값을 가지고 TLB를 업데이트
그것을 물리주소 만드는데 사용

메인메모리에 없다면 (page falut)
os는 cpu에게 페이지를 ssd나 디스크로부터 읽어오라고 명령함
인터럽트 처리해서 cpu는 IO 하드웨어에게 페이지를 메인메모리에 보내라고 알려줌

페이지를 가져오기 위해서 메모리 빈곳을 써야하는데
빈곳이 없다면 지금 메인메모리에 들어온 프로세스의 페이지 중에 빼내고(캐쉬 replacement하듯이) 뭔가 빼내고 그 자리에 가져온 페이지를 갖다놓고
비어있다고 한다면, 페이지를 옮겨온다음 page table entry 업데이트 하고

그리고 다시 falut를 발생시킨 instruction을 돌아가게 된다


TLB를 만들기 위해서 Associative mapping 사용
지금 사용되고 있는 대부분의 프로세서는 TLB를 가짐 이것을 Associative memory로 구현, 이것은 하나의 칩 안에 들어있다


associative mapping
비교기가 동시에 넣고, true가 되는것을 밖으로 내보냄
frame number 가 나오게 되고, 오프셋을 붙여서 real address만들어냄

direct mapping
배열과 같이 인덱스로 해서 페이지 프레임 넘버를 꺼내는 방법


TLB와 instruction cache가 있다면 페이징을 사용한다면 어떻게 주소번역을 하고 데이터를 가져올까

페이지가 real memory에 있다면
논리주소가 주어질때 페이지넘버를 꺼내서 TLB가 붙으면 프레임 넘버를 사용해서 offset을 붙여서 real address를 만듦
miss라면 page table entry를 찾아서 offset과 붙여서 real address 만든다

이렇게 real address를 만들어지면
cache를 찾아서 그 안에 값이 있는지를 보고, hit면 그 값을 쓰고
miss면 그 주소를 메모리로 내보내서 값을 가져오게 되고,
메모리에도 존재하지 않는다면 SSD에 존재한다면, interrupt를 사용해서 해당되는 페이지를 가져와서, 주변 페이지까지 가져와서 워드를 가져오게 됨


이러한 시스템을 만들때, 페이지 크기는 성능에 영향을 미친다.
작은 크기로 페이지를 만들면 internal fragmentation이 적고
그렇지만 하나의 프로세스를 위해서 많은 페이지가 필요
여러 페이지를 쓰면 페이지 테이블 크기가 커진다.
그러면 실제로 프로세스를 위해 사용가능한 메모리 크기가 줄어든다

만약 멀티프로그램이 많이 일어나는 환경이라면, 테이블의 어떤 부분은 버츄얼 메모리에 들어가게 된다, 대부분의 세컨더리 메모리는 블럭단위로 읽어내기 때문에 크게 메모리를 읽어내야 효율적이게 된다.

usb 써보면 작은 단위일때 속도가 느려진다.


이러한 특징들 때문에 page size가 변하면서 page fault rate가 변하게 되고 
프로세스당 할당된 페이지 프레임 개수가 변하면서 fault rate가 변하게 된다

P는 프로그램 전체의 크기를 의미한다.
페이지가 커지면 internal fragmentation 이 많아지면서, hit rate가 떨어지고 fault rate가 커진다. 
프로그램 크기에 가까워질수록 fault rate가 떨어진다

할당된 페이지 프레임의 개수가 늘어날수록 page fault는 줄어든다
급격히 줄어들다가 완만하게 줄어드는 변곡점 부분이 Working set size에 해당되는 부분이다.
실제로 locality를 포함하는, 직접적으로 메모리를 많이 쓰는 크기만큼 가지게 되면, fault rate를 급격히 줄일 수 있는 장점이 버츄얼 메모리에서 생기게 된다.


페이지 크기는 처음에는 작게 시작


페이지 크기는, 결국 physical memory, 사용하는 프로그램의 크기에 영향받는다
메인메모리, 앱의 크기는 점점 커지고 있다.
4K로 고착화된것은 디스크에서 메인메모리로 가져올때 한번 읽어낼수있는 블록의 크기로 가져오는것이 가장 효율적이기 때문에... 이 값이 남아있다.


페이징은 외부파편화 없이 메모리 사용할수 있다는 장점
단점은 프로그램을 구성하는 각 덩어리, 세그먼트 단위로 관리되지 않으므로 sharing, protection에 문제

세그멘테이션은 프로그램이 컴파일되어 만들어진 덩어리인 세그먼트 단위로 관리 
이렇게해서 메모리 덩어리별로 메모리를 증가한다거나, 부분적으로 컴파일한다거나, data를 sharing하거나, protection하는데 잘 사용된다.


세그먼트의 구성
각 세그먼트 엔트리는 시작주소와 길이값을 갖는다
그리고 세그멘트가 메인메모리에 존재하는지 - present bit
그리고 세그멘트가 변경이 되었는지 - modify bit


주소 번역 방법
세그먼트 넘버가 있으면, 세그먼트 포인터값(시작)을 더해서 엔트리를 찾는다.
그 안에 세그멘트의 길이와 시작점이 들어있고 
시작점을 오프셋과 더해서 물리주소를 만든다


그래서 그 엔트리를 찾아서 메인메모리에서 가져온다 
base가 메인메모리에서 시작점이 되고, offset = d가 더해지는 값이 된다 


실제로는 페이징과 세그멘테이션의 장점이 있기에 둘을 결합하여 사용
먼저 세그먼트를 만들고, text, data, bss, stack을 만들고
그걸 다시 page단위로 나눔 

세그멘테이션은 프로그래머에게 보여지는 부분
페이징은 프로그래머에게 보이지 않는 부분이 되지만
페이징의 외부파편화가 없는 장점과 , 세그멘테이션의 sharing과 protection의 장점을 활용


segment paging system
virtual 주소에서 
일부분이 세그먼트 넘버가 되고, 시작점 더해서 엔트리 찾는다
그것을 가지고 페이지 테이블의 base address를 만든다

그 테이블 안에서 엔트리를 찾는데 페이지 넘버를 사용
그 안에 프레임 넘버가 있어서 주소를 만들게 사용, 오프셋을 더해서 물리주소를 만든다

결과적으로 프레임 넘버는 메인메모리의 시작점을 가리키게 된다.


사용되는 주소와 자료구조

세그멘트 테이블 엔트리에서
P - 메인메모리에 존재하는지
M - 수정되었는지, 값이 메인메모리에 들어온 이후 변경되었는지
세그멘트 베이스 - 테이블의 시작점을 나타냄

그 시작점으로 페이지 넘버만큼 떨어진 곳에 페이지 테이블 엔트리가 존재
거기서 프레임넘버 + 오프셋 = 물리주소


이렇게 해서 세그멘테이션은 
protection, sharing을 논리적 단위로 할수있게 해주고
각 엔트리는 base address와 길이가 있고
이 단위로 sharing 했을때 몇개나 sharing되었는지 카운트 값을 갖고있다.


운영체제 소프트웨어는 다음과 같은 구분점에 의해 구분됨
버츄얼메모리를 사용하는지?
세그멘테이션, 페이징 어떤걸 쓰는지, 둘다쓰는지
어떤 정책으로 memory management 관리하는지

이 뒤에부터는 세번째 내용을 알아본다