출처 : KOCW 운영체제-반효경
logical address vs physical address
프로세스 마다 0번지부터 시작하는 가상의 주소공간을 가진다. 실제 메모리에 올라가는 주소는 물리적 공간이라고 한다. 프로세스는 symbolic address(ex 프로그램의 변수, 함수명), virtual address , physical address 를 순서대로 매핑하여 주소를 결정한다. 이를 주소 바인딩이라고 한다. cpu는 logical address를 참고한다.
주소 바인딩
Logical address -> physical address 를 언제 결정하는 지에 따라 주소 바인딩 방식이 compile time binding, load time binding, execution(run) time binding 으로 나뉜다.
Compile 이라는 것은 symbolic address 를 logical address로 바꾸는 것을 말한다. 이 과정은 compiler 에 의해 실행된다. compile time binding을 하게되면 결국 logical address와 physical address가 같아진다. 그래서 compiler 는 absolute code를 생성한다. physical address를 바꾸고 싶다면 다시 compile을 해야한다는 불편함이 있다.
Load time binding은 logical address 의 데이터를 메모리에 올릴 때 메모리의 어떤 부분에 프로세스를 올릴지 결정한다. 즉, 프로그램이 시작될때 주소가 결정된다. 그래서 일반적으로 logical address 와 physical address 가 다르다.
Run time binding 은 load time binding과 동일하게 프로그램이 시작될때 주소바인딩이 일어난다. 다른점은 프로그램이 실행중일때 logical address와 physical address의 매핑이 변할 수 있다는 점이다. 그 변화는 MMU(memory management unit)인 relocation register와 limit register에 저장한다. Relocation register는 process가 메모리에 올라가는 최초의 주소를 저장하고 limit register는 logical address의 크기를 저장한다. cpu가 읽으려는 주소가 limit register보다 작은지 확인하고 크다면 프로세스는 cpu 제어권을 빼앗긴다. 프로세스가 자신의 공간외의 메모리를 접근하려고 하는 것을 막기위서 이다. 이 과정을 통과하면 cpu가 읽으려는 주소에 relocation register의 값을 더해서 physical address를 얻어낸다.
Some terminologies
Dynamic loading
프로그램은 굉장히 방어적으로 설계되어 있다. 일반적으로 일어나지 않는 오류 처리 코드가 존재한다. 이러한 모든 코드를 메모리에 올리는 것은 memory utilization을 저해할 수 있다.
Dynamic loading은 이러한 문제점을 해결하기 위해 해당 루틴이 불려질 때 메모리에 load 하는 방식이다. 현대의 프로세스는 운영체제가 관리하는 paging 기법을 통해 당장 필요한 부분을 메모리에 올리고 필요 없는 부분을 디스크로 쫓아내는 방식을 사용한다. Dynamic loading은 운영체제의 특별한 지원없이(운영체제의 라이브러리를 사용하는 정도) 프로그래머가 직접 구현하는 것을 말한다. 요즘은 프로그래머가 명시적으로 dynamic loading을 하는 것만을 뜻하지 않고 운영체제의 paging 기법에 의한 것 또한 dynamic loading이라고 부르기도 한다.
Overlays
Dynamic loading 유사하게 메모리에 프로세스의 부분 중 실제로 필요한 정보만을 롤려 놓는다. 하지만 dynamic loading과 역사적으로 다르다. 과거에는 하나의 큰 프로그램을 메모리에 올리는 것이 부담스러웠다. 그래서 큰 프로그램을 쪼개서 메모리에 올렸다 내렸다를 운영체제의 지원 없이 프로그래머가 수작업으로 진행을 하였다. 그래서 이것을 manual overlay라고 부르기도 한다.
Swapping
프로세스를 일시적으로 메모리에서 backing store(=swap area)로 쫓아내는 것을 말한다. 일반적으로 중기 스케줄러(=swapper)에 의해 swap out 될 프로세스가 결정된다. 보통 priority-based cpu scheduling algorithm을 참고하여 swap out/in을 결정한다. Compile time, load time binding은 프로그램이 한번 실행되면 원래의 위치로 swap in 해야되기 때문에 swapping을 사용하지 않는다. Execution time binding 에서는 physical address를 변경할 수 있기 때문에 swapping을 효율적으로 사용할 수 있다.
디스크를 접근하는 시간은 seek time(disk의 head 가 움직이는 시간) 이 거의 대부분을 차지하고 transfer time은 상대적으로 미미하다. 하지만 한번에 많은 양을 swap 하는 것은 transfer time 또한 상당부분 차지하게 된다.
최근에는 paging 기법을 이용해 프로세스의 일부를 쫓아내고 불러들이는 것도 swap out/in이라고 표현한다. 하지만 원칙적으로 swapping은 프로그램 전체가 swap in/out 하는 것을 말한다.
Static linking vs Dynamic linking
Static linking 은 라이브러리가 실행 파일 코드에 포함되는 방식이다. 그렇게 되면 실행파일이 무거워지고 동일한 라이브러리를 사용하는 여러가지 실행파일이 있다면 중복을 의미하고 결국 메모리의 낭비를 의미한다.
반면 dynamic linking은 라이브러리 코드가 실행 파일 코드에 포함되지 않고 라이브러리를 실행시 연결(link)하는 방식이다. 라이브러리를 호출하는 부분에 라이브러리 루틴의 위치를 찾기 위한 stub(pointer?) 라는 작은 코드를 둔다. 라이브러리가 메모리에 존재하면 그 루틴의 주소로 가고 없으면 디스크에서 읽어오게 된다.
Dynamic linking을 해주는 라이브러리를 shared library라고 한다. Linux 운영체제 환경에서는 shared object라고 부르며 windows 에서는 dll(dynamic linking library) 라고 한다.
Allocation of physical memory
메모리는 일반적으로 OS 가 상주하는 영역, 사용자 프로세스 영역으로 나뉜다. OS 는 interrupt vector 와 함께 낮은 주소 영역을 사용하며 사용자 프로세스 영역은 높은 주소 영역을 사용한다.
사용자 프로세스 영역을 할당 하는 방법은 contiguous allocation 과 noncontiguous allocation으로 나뉜다. 연속할당은 프로세스를 메모리에 연속적으로 할당하는 것이고, 불연속할당은 프로세스를 쪼개서 메모리에 할당하는 것을 말한다.
Contiguous allocation
Contiguous allocation은 프로세스에게 메모리를 연속적으로 할당한다는 것이다. 이 방식도 fixed partition allocation, variable partition allocation 으로 나뉜다.
Fixed partition 방식은 메모리를 미리 정해둔 partition(partition 크기는 다양할 수 있음)으로 나누어 partition 하나에 하나의 프로세스만이 들어가는 방식이다. 그렇기 때문에 최대 수행 가능 프로그램 크기가 제한되고 동시에 메모리에 load 되는 프로그램의 수가 고정되는 단점이 있다. Internal fragmentation, external fragmentation이 발생한다.
Variable partition 방식은 프로그램 크기를 고려해 할당하는 방식이다. 즉, 다양한 크기의 partition이 생기게 된다. 다양한 partition 을 잘 활용하기 위해 기술적 관리 기법이 필요하다. Variable partition 방식은 external fragmentation만 발생한다.
- Internal fragmentation : partition에 프로세스가 들어가 남은 공간
- External fragmentation : 프로세스가 들어간 partition 사이에 낀 빈 partition으로 인한 공간
가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 hole을 찾는 문제를 dynamic storage allocation problem 이라고 한다. Hole 은 가용 메모리 공간을 의미한다. 운영체제는 할당된 공간과 가용공간을 기억하여 다른 프로세스가 들어올때 적절한 공간을 할당해 주게 된다. 방법으로는 first-fit, best-fit, worst-fit 방식이 있다.
First fit 은 size가 n 이상인 최초의 hole에 할당하는 방법이다. 이 방법은 공간을 찾는것에는 적은 overhead가 들지만 공간을 효율적으로 사용하는 것에는 거리가 멀다.
Best fit 은 size가 n 이상인 hole 중 가장 작은 hole에 할당하는 방법이다. 모든 hole 을 탐색해야하기 때문에 그 부분의 overhead 는 가장크다. 하지만 가장 공간을 효율적으로 사용하는 방법이다.
Worst fit은 이도저도 아닌 방법이다. 가장 큰 hole에 할당하는 방법이기 때문에 공간효율성 도 좋지 못하고 시간효율성 측면에서도 별로이다.
실험적으로 first-fit 과 best-fit이 worst-fit보다 속도와 공간 이용률 측면에서 효과적인 것으로 알려져있다.
Contiguous allocation 을 사용하게 되면 가용 메모리보다 작은 크기의 프로세스라고 하더라도 hole 이 흩어져 있기 때문에 해당 프로세스에게 메모리를 할당할 수 없게 되는 상황이 발생한다. 이 경우 compaction을 사용할 수 있다. compaction은 메모리 영역을 한군데로 몰고 다른 곳은 hole을 몰아 큰 block을 만드는 것이다. (Disk 조각모음은 disck compaction) 메모리 저장된 정보를 옮기는 것은 address binding 과 같은 것들을 점검해야하기 때문에 cost가 크다. 그래서 최소한의 메모리 이동으로 compaction을 해야한다.(복잡한 문제) Compaction은 프로세스의 주소가 실행 시간에 동적으로 재배치 가능한 경우에만 수행될 수 있다.(run time binding)
Noncontiguous allocation
Noncontiguous allocation은 크게 paging 기법과 segmentation 기법으로 나눌 수 있다.
Paging 기법은 virtual memory 를 일정한 크기로 자르고 physical memory 또한 일정한 크기의 frame으로 나누어 할당하는 방법이다. Contiguous allocation의 방법들보다 공간, 시간효율성이 좋다. 다만 주소변환을 할때 page 단위로 추가적으로 Page table을 사용해야한다.
Segmentation 기법은 virtual memory를 의미있는 단위(code/data/stack, 함수…)로 나누는 방법이다. 하지만 의미단위로 자른것이기 때문에 크기가 다양할 수 있다. 따라서 dynamic allocation problem이 발생할 수 있다.
Paging
Paging 기법의 주소 변환은 page table을 통해 해당 page의 시작 지점이 physical memory의 어떤 부분인지와 해당 instruction이 page내에서 몇번째 instruction인지 알아내 두 값을 더하여 얻을 수 있다.
page table은 어디에 저장할 것인가? 보통 페이지를 자르는 단위는 4KB 이고 4GB 의 프로그램을 가정하면 100만개의 데이터를 가지는 배열이 된다. 그렇게 되면 register에 저장할 수 없고 cache memory에 저장하기에도 많은 양이다. 그래서 이 정보를 메모리에 저장하게 된다.
Paging 기법을 통해 주소 변환하는 것 또한 MMU의 2개의 register 를 사용하게된다. 여기서 이 register 를 다르게 사용되는데 relocation register에 해당하는 것은 page-table base register(PTBR:page table을 가리킴), limit register에 해당하는 것은 page-table length register(PTLR:테이블의 크기를 보관)이다. MMU에서는 physical memory에 접근하는 것이 목적이였다면 여기서는 page table에 접근하는 것이 목적이다.(아마 그 후 physical memory 에 접근 할때는 다시 relocation register 와 limit register로 사용할 것이다.)
프로세스를 실행하기 위해선 page table에 접근하는 메모리 접근과 실제 data, instruction 등에 접근 하기위한 메모리 접근 총 2번의 메모리 접근이 필요하다. 2번의 접근을 요구하기 때문에 속도가 떨어질 수 있다. 속도 향상을 위해 associative resgister 혹은 translation look-aside buffer(TLB)라고 불리는 고속의 lookup hardware cache(데이터를 저장하는 cache memory랑은 조금 다름 주소변환을 하는 cache memory) 사용한다.(운영체제 입장에서는 cache memory 는 감춰진(transparent) 계층)
TLB 에는 빈번히 참조되는 페이지의 번호에 대응되는 frame 번호를 저장한다. 하지만 페이지 테이블에 대한 모든 정보를 담고 있지 않기 때문에 page table과 달리 page 번호와 frame 번호를 모두 가지고 있어야한다.(page table은 entry를 통해 몇번째 page인가에 대한 정보를 나타낼 수 있다.) 그리고 TLB 는 전체를 확인해야하고 page table은 해당 엔트리의 값만 참고하면된다. 하지만 TLB 는 병렬적으로 전체를 search 하게 되어 속도가 굉장히 빠르다. 만약 원하는 페이지에 대한 정보가 없으면 TLB miss(cache에 확인해 봤더니 원하는 정보가 없다면 cache miss라고한다.) 가 나게된다. TLB miss 가 나게되면 page table을 사용하게 된다. TLB 는 프로세스마다 존재하므로 context switch가 일어나면 flush(remove old entries)된다.
TLB 를 활용하는 것은 TLB를 읽는데 걸리는 시간보다 TLB hit 를 통해 절약한 시간이 더 크다.
메모리에는 주소가 1byte 단위로 매겨진다. 32bit 주소체계를 사용한다면 하나의 프로세스가 가질 수 있는 virtual memory의 최대 용량은 4GB이다. 보통 page는 4KB 단위로 쪼갠다. 그 때 최대 page 개수는 2^20 약 100만개이다. 그리고 각각의 page entry가 약 4Byte 정도를 차지한다면 page table의 용량은 4MB가 된다.
대부분의 프로그램은 4G의 주소공간 중 지극히 일부만을 사용하므로 공간낭비가 굉장히 심하다. 그래서 two-level page table이 등장하였다. 2단계 페이지 테이블은 outer page table 과 inner page table로 나뉜다. Inner page table이 결국 page table 과 같은 양의 메모리를 점유하는 것이 아니냐고 반문할 수 있다. outer-page table의 특정 page에 해당하는 주소공간이 빈 공간이라면 entry 값은 NULL이 되고 inner page table을 생성하지 않는다. 프로세스의 주소공간은 빈 공간을 많이 포함되어 있다. 그래서 outer page table을 통해 1차적으로 그러한 빈 공간을 걸러낼 수 있고 결과적으로 메모리를 더 효율적으로 쓸 수 있다.
two-level paging 를 32bit machine 에 적용하는 상황을 생각해보자. Page size 는 4K(하나의 page가 담당하는 주소의 수), Page entry 4B(하나의 페이지가 차지하는 주소공간의 크기)라고 가정하자. Page size 가 4K(2^12=12bit) 이기 때문에 page offset은 12bit 가 된다. Inner page table은 outer page table 의 table과 대응된다. 따라서 Inner page table은 4K 개의 주소를 가지며 하나의 page entry는 4개의 주소를 사용하므로 inner page table의 entry의 개수는 1K(2^10=10bit) 이기 때문에 10bit가 필요하다. 나머지 10 bit는 outer page 가 사용하게 된다.
조금 햇갈려서 stack overflow 예제 를 찾아보았다. 링크의 예제는 얼마나 많은 level 의 paging 이 필요하냐에 대한 문제이다. 어느정도 해결이 되었지만 위의 경우도 그냥 two-level paging 기법을 쓸 수 있지 않냐는 의문이 생겼다. 왜냐하면 주소변환을 할때 가장 처음 만나는 page table은 누군가의 page가 아니기 때문이다.(미해결...)
###Multi level paging and performance
Adress space 가 커지게 되면 page table을 공간효율적으로 쓰기위해 다단계의 테이블이 필요하다. 하지만 다단계의 테이블을 쓰게되면 메모리접근을 그 단계만큼 더 해야한다는 단점이 있다. 마찬가지로 TLB를 통해 평균적인 메모리 접근 시간을 줄일 수 있다.
page table 의 부가적인 bit
Valid(v=1) / Invalid(I=0) bit
page table에 주소 변환 정보 이외의 추가적인 정보들이 들어있다. Valid/invalid bit 가 그 중 하나이다. virtual memory 에는 code, data, stack으로 구성되어 있고 그 사이 사이에는 정보가 담겨져 있지 않은 빈 공간이 존재한다. 이러한 빈 공간을 page table에 반영하지 않는다면 table 의 Index를 적극 활용하지 못한다. 따라서 page entry에는 빈공간이라고 할지라도 entry가 만들어져야한다. 이렇게 사용이 되지 않는 page에 대한 표시가 필요하다. 그 역할을 하는 것이 Valid/invalid bit 이다.
valid 는 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음을 의미한다.(접근 허용) invalid 는 해당 주소의 frame 에 유효한 내용이 없음을 의미한다.(접근 불허) 유효한 내용이 없다는 것은 프로세스가 그 주소 부분을 사용하지 않는 경우와 해당 페이지가 메모리에 올라와 있지 않고 swap area에 있는 경우 이다.
Protection bit
page 에 대한 접근 권한을 통제하는 것이 아니라, 어떤 연산(read/write/read only)을 허용할 지를 나타내는 비트이다.
inverted page table
page table 기법의 단점은 page table이 차지하는 메모리 공간의 크기가 크다는 것이다. 주소공간이 허용하는 한도만큼의 page entry 가 만들어진다. 또 각 프로세스마다 page table 이 만들어 져야한다. 이러한 것을 해결하기 위해 inverted page table 을 쓰기도 한다.
page table 은 logical address가 어떤 physical address에 해당하는 지를 통해 주소 변환을 하였다면 inverted page table은 반대로 physical address가 어떤 프로세스의 logical address에 해당하는 지를 통해 주소 변환을 한다. 따라서 entry는 frame의 수 만큼 생성되고 주소변환을 위해 pid 와 logical address 가 모두 필요하다. 또한 inverted page table의 index는 page table 처럼 몇번째 페이지인가 에 대한 정보를 담고 있지 않기때문에 table을 순차적으로 탐색해야한다. 이러한 방법은 시간적으로 overhead가 크기 때문에 TLB 와 비슷하게 associative register를 사용하여 병렬적으로 탐색한다.
shared pages
shared code는 IPC(inter process communication)에서 shared memory 를 이용해서 프로세스가 서로 협력하는 것과는 조금 다르다. IPC 에서는 read/write 권한을 통한 communication 을 목적으로 한다. Shared code 는 동일한 코드를 여러 프로세스가 사용할때 메모리를 효율적으로 사용하기 위한 방법(반복을 피하기위해)이다. 그러한 점에서 shared code는 dynamic linking과 비슷하다고 생각한다. 하지만 코드의 경우 프로세스가 실행되는 시점에 변하면 안된다. 따라서 read only 권한을 부여해야한다.
shared code 는 re-enterant code(=pure code)라고한다. Shared code는 모든 프로세스의 logical address space에서 동일한 위치에 있어야한다. 왜냐하면 logical memory의 내용이 physical memory에 올라갈때 내용이 변하지 않는다. 즉 코드가 logical address 기준으로 작성된 것이기 때문이다. 그 외의 private code and data는 독자적으로 관리된다.
segmentation
프로세스가 가지는 주소공간을 의미단위로 쪼갠것을 말한다. 각각의 의미단위는 segment가 된다. 크게는 프로그램 전체를 하나의 세그먼트라고 볼 수 있고 작게는 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의할 수 있다. Logical address는 <segment-numver, offset> 으로 구성된다. offset에 몇 bit를 줄지를 통해 segment의 크기를 제한할 수있다.
segment table에는 limit, base 가저장된다. Limit은 segment의 크기를 의미하고 base는 해당 segment의 physical memory 상에서의 시작 위치를 의미한다. paging 과 달리 segment 의 크기는 프로세스 내에서 고정된 크기가 아니여서 limit가 필요하고 frame 또한 고정된 크기가 아니여서 base는 몇번째 프레임인지를 나타내는 것이 아니라 physical address 자체여야한다. Segment table 과 관련된 2가지 register가 존재한다. Segment-table base register(STBR) 은 segment table의 시작 위치를 나타내며 segment-table length register(STLR)은 프로그램이 사용하는 segment의 수를 나타낸다.
주소 변환은 segment table의 base 와 offset 을 더함으로써 수행된다. 단, STLR을 통해 접근하려는 segment가 프로세스의 segment 의 수를 초과하는 경우, offset이 segment table의 limit을 초과하는 경우 trap이 걸리게 된다.
segmentation 의 단점은 segment 의 크기가 다양하다는 것에서 기인한다. External fragmenration이 발생하여 별도의 할당 알고리즘(first fit, best fit)이 필요하다. 장점은 프로세스를 의미단위로 나눈것에서 기인한다. 실행권한, 보안(valid,protection bit)은 보통 의미단위로 설정된다. 메모리를 공유하는 부분에서도 의미단위로 하는 것이 유리하다.또한 실제적인 상황(일반적으로)에서는 paging은 많은 수의 page로 나누지만 segmention은 그에 비해 훨씬 적은 수의 segment로 나눈다. 따라서 table을 저장하는데 드는 비용은 segmentation이 더 작다.
shared segment 의 동작방식은 shared pages와 거의 동일하다. Shared segment를 공유하는 프로세스들은 shared segment의 logical memory(segment 번호)를 동일하게 사용해야한다.
paged segmentation
segment 를 여러개의 page로 구성하는 방식을 말한다. segmentation 기법 단독으로 사용하는것은 사실상 존재하지않는다.(메모리를 효율적으로 못쓰니까) 하지만 segmentation이 가져오는 권한부여, 프로세스간의 메모리공유 등 의 이점이 크기 때문에 그 부분은 segmentation으로 하고 메모리 할당은 paging 기법을 쓰겠다는 것이다.
segment 번호와 STBR을 통해 segment table에 접근한다. Segment length와 offset을 비교해 접근하려는 곳이 segment 내인지를 판단한다. Page-table base를 통해 해당 segment의 page table의 시작 주소를 알아내고 offset을 통해 몇번째 Page인지를 알아낸다. 둘을 더해서 해당 페이지가 어떤 frame에 해당하는지 를 알아내고 offset에서 page 번호를 때어내어 생긴 offset을 통해 최종적으로 물리적 주소를 알아낸다.
이때 까지 메모리 관리에 대한 하드웨어적인 것을 알아보았다. 다음 chapter는 OS 가 관여하는 virtual memory에 대해 알아볼 것이다.
