Memory Allocation
물리적 메모리의 할당
메모리는 일반적으로 두 영역으로 나뉘어 사용된다.
OS 상주 영역에는 아주 낮은 주소 영역에 interrupt vector 와 함께 존재한다.
사용자 프로세스 영역에는 높은 주소 영역을 사용한다.
이 사용자 프로세스 영역에 메모리를 할당하는 방법에는 다시 또 두 가지가 있다.
continuous allocation은 각각의 프로세스가 메모리의 연속적인 공간에 적재가 된다.
fixed partition allocation
variable partition allocation
noncontinuous allocation 은 하나의 프로세스가 메모리의 여러 영역에 나뉘어 올라간다.
paging
segmentation
paged segmentation
1) continuous allocation
fixed partition allocation 고정분할방식
fixed partition allocation 을 따르면 메모리의 공간이 몇개의 영구적 partition으로 분할된다.
파티션의 크기가 모두 동일한 방식과 서로 다른 방식이 존재하며
파티션당 하나의 프로그램이 적재될 수 있다.
융통성이 없어서 동시에 메모리에 로드되는 프로그램의 수가 제한적이게 되며, 최대 수행 가능한 프로그램의 크기도 제한된다.
프로그램이 파티션과 맞지 않다면, 외부조각 external fragment 이나 내부 조각 internal fragment이 생기게 된다.
variable partition allocation 가변분할방식
프로그램이 실행될 때마다 차곡차곡 메모리에 올려두는 방식으로
프로그램의 크기를 고려해서 할당된다. 분할의 크기와 개수가 동적으로 변한다.
이 방법을 위해서는 기술적으로 관리 기법이 갖추어져야한다.
가변분할방식도 프로그램 실행에 따라서 외부조각이 발생할 수 있는데 예를 들면 아래와 같은 상황이다.
프로그램 B의 수행이 끝나도 프로그램D가 B가 있던 공간에 들어가지 못하기 때문에, C뒤에 위치하게 된다. 이때 외부조각이 발생할 수 있다.
hole
가용메모리 공간
다양한 크기의 hole 들이 여러 메모리 공간에 흩어져 있다.
프로세스가 도착하면 수용 가능한 hole 을 할당한다.
따라서 운영체제는 다음의 정보를 항상 숙지하고 있다. → 1) 할당 공간 2) 가용공간 hole
dynamic storage allocation problem
가변분할 방식에서 size 가 n인 요청을 만족하는 가장 적절한 hole을 찾는 문제
해결방법에는 3가지가 있다.
first fit : size n을 만족하는 hole 중 가장 최초로 찾아지는 것에 할당하는 방법
best fit : size n을 만족하는 hole 중 가장 작은 것에 할당하는 방법
hole들의 리스트가 크기순으로 정렬되지 않는 경우, 모든 hole 들을 탐색해야한다.
많은 수의 아주 작은 hole 들이 생성될 수 있다.
worst fit : size n을 만족하는 가장 큰 hole에 할당하는 방법
모든 리스트를 탐색해야하며
큰 hole 들이 생성된다.
당연하게도 first fit 은 시간적으로, best fit 은 공간 이용률 측면에서 각각 가장 유리하며, worst fit은 가장 비효율적인 것이 실험 결과 나타났다.
compaction
external fragmentation 외부조각 문제를 해결하기 위해서 사용중인 메모리 영역을 한 군데로 몰고 hole 들을 다른 한 곳으로 모아 아주 큰 hole 을 만드는 방법이다.
비용이 매우 많이 들며, 최소한의 이동으로 메모리를 compaction 하는 방법은 매우 복잡하다.
당연하지만, compaction 기법은 프로세스의 주소가 실행되는 시간에 동적으로 재배치가 가능한 경우에만 사용 가능하다.
2) noncontinuous allocation
paging
프로그램을 구성하는 주소 공간을 페이지 단위로 자른다. 물리적 메모리의 공간도 같은 단위로 자른다.
주소 변환이 더 복잡해지기 때문에 address binding 이 더 복잡해진다.
segmentation
의미있는 단위로 자르는 것
paged segmentation
paging
프로세스의 virtual memory 를 동일한 사이즈의 page 단위로 나눈다.
virtual memory 의 내용이 page 단위로 noncontinous 하게 저장된다.
일부는 backing storage 에, 일부는 physical memory 에 저장된다.
basic method
physical memory 를 동일한 크기의 frame 으로 나눈다.
local memory 를 동일한 크기의 page 로 나눈다. → frame 과 같은 크기!
모든 가용 frame 들을 관리한다.
page table 을 사용하여 logical address를 physical address 로 변환한다.
page 단위로 나누어지기 때문에 더이상 두 개의 register 로는 불가하다.
external fragment 는 발생하지 않지만, 여전히 internal fragmentation 이 발생할수는 있다.
페이지 단위로 나누게 되면, 페이지 범위를 다 채우지 못해 남는 공간이 발생할 수 있다는 뜻.
page table 은 physical memory 에 상주한다.
page table base register 가 page table 을 가리키고 있고,
page table length register 는 테이블의 크기를 보관한다.
따라서 모든 메모리 접근 연산에는 2번의 memory access 가 필요한데, 한번은 page table 에 접근하기 위해서, 1번은 실제 데이터와 인스트럭션에 접근하기 위해서 필요하다.
속도 향상을 위해서
associative registerORtranslation look-asidebuffer 라고 불리는 고속의 lookup hardware cache 를 사용한다.associative resiters (TLD) : parallel search 가 가능하다. page table 테이블 중 일부만 존재한다. 없으면 page table 로 이동함
address translation 과정
page table 중 일부가 associative regieter 에 보관되어있다.
만약 해당 page 번호가 존재하는 경우, 곧바로 frame 번호를 얻게 된다.
하지만 존재하지 않은 경우, main memory 에 있는 page table로부터 frame 번호를 얻는다.
TLB 는 context switch 때 flush (remove old entiries) 된다. → 프로세스별로 별도로 존재하기 때문에
실제 메모리에 접근하는 시간은?
상당히 빠르다!
2단계 페이징 테이블 - two level paging table
사용하는 이유
컴퓨터에서 어떤 시스템이 존재할 때, 그 존재의 이유는 보통 두 가지이다.
시간을 빠르게 하거나
공간을 효율적으로 하거나
two level paging table 의 경우, 속도는 중간 과정이 추가 되기 때문에 오히려 더 늘어날 것이라는 것을 알 수 있다. 그래서 아마
공간을 효율적으로 하지 않을까, 추측할 수 있다.
현대의 컴퓨터는 32bit, 64bit 단위이다. 그렇다면, 프로그램마다 가지고 있는 Maximum 주소체계는 몇 개나 되겠는가? → 컴퓨터의 32bit, 64bit 에 따라서 나누어진다.
32bit 컴퓨터의 경우, 0번부터 2^32번까지의 메모리 주소를 가질 수 있다.
그런데 2^10 = K 이고, 2^20 = M이고, 2^30 = G이므로,
2^32 = 2^2 * G = 4GB를 의미하게 된다.이때, 페이지 사이즈가 4K라면, 1M개의 page table entry 가 필요하게 된다.
각 page entry가 4B일 때에는, 프로세스 당 4M의 page table 이 필요하다.
그러나 대부분의 프로그램은 4G의 주소공간 중에서 지극히 일부분만 사용하므로, page table 공간이 심하게 낭비된다.
page table 자체를 page 로 구성한다.
사용되지 않는 주소 공간에 대한 outer page table의 엔트리 값은 null 이다.
multi-level paging and performance
address space 가 더 커지면 2단계 페이징 테이블만으로는 부족하다. 다단계 페이지 테이블이 필요하다.
각 단꼐의 페이지 테이블이 메모리에 존재하므로 logical address 의 physical address 변환에 더 많은 메모리 접근이 필요하다.
TLB 를 통해 메모리 접근 시간을 줄일 수 있다.
4단계 페이지 테이블을 사용하는 경우,
메모리 접근 시간이 100ns, TLB 접근 시간이 20ns 이고 TLB hit ratio 가 98%인 경우,
총 5번의 메모리 접근이 필요하다 → 4번은 페이지 주소변환, 1번은 데이터 접근
effective memory access time = 0.98 * 120 + 0.02 * 520 = 128 nano seconds
98%는 TLB 를 통해서 이루어 질테니, 20ns정도만 주소변환에 소요된다. 이 경우, 메모리 접근시간+주소변환시간 = 120ns 가 된다.
반면 TLB 를 통해 이루어지지 못한 2%의 경우는, 주소변환에만 400ns 가 소요된다. 그리고 TLB 에 없다는 것을 확인하는 작업에 20ns, 실제 메모리에 접근하는 시간으로 다시 100ns 가 소요된다. 즉, 총 520ns 가 소요되는 것이다.
결과적으로 주소 변환을 위해 28ns 만 소요된다.
실제 메모리 접근을 위한 100ns + 주소변환을 위한 28ns
memory protection - page table 에서 valid, invalid bit 표현
page table 의 각 entry 마다 아래의 bit 를 둔다.
protection bit : page 에 대한 접근 권한 (read, write, read-only)
valid
해당 주소의 frame 에 그 프로세스를 구성하는 유효한 내용이 있음을 뜻함. → 접근 허용
테이블에 매핑된 실제 물리적 메모리 주소로 가면 데이터를 찾을 수 있다.
invalid
해당 주소의 frame 에 유효한 내용이 없음을 뜻한다. → 접근 불허
프로세스가 그 주소 부분을 사용하지 않거나
해당 페이지가 메모리에 올라와있지 않고 swap area에 있는 경우를 의미한다.
inverted page table
page table 이 매우 큰 이유
모든 프로세스별로 그 logical address 에 대응하는 모든 page 에 대해 page table entry 가 존재하기 때문이다.
대응하는 page 가 메모리에 있든 아니든 간에 page table 에는 entry 로 존재한다.
그래서 이 낭비되는 공간을 줄이기 위해 등장한 것이 inverted page table!
inverted page table 에서는 physical memory 에 접근하면 page table 에서 매핑된 logical memory 주소를 거꾸로 되찾아간다.
즉, 물리적 메모리 주소에 맞게 논리적 주소를 바꾸는 형식!
page frame 하나 당, page table 에 하나의 entry 를 둔 것이다.
각 page table entry 는 각각의 물리적 메모리의 page frame 이 담고 있는 내용을 표시한다.
process id, process logical address
단점 : 테이블 전체를 탐색해야한다.
해결 : associative register 를 사용한다. (하지만 너무 비싸다;;)
shared page
shared code
re-entrant code = pure code
read-only로 하여 프로세스 간에 하나의 code 만 메모리에 올린다.shared code 는 모든 프로세스의 Logical address space 에서 동일한 위치에 있어야 한다.
private code and data
각 프로세스들은 독자적으로 메모리에 올린다.
private data 는 logical address space 의 아무 곳에 와도 무방하다.
segmentation
의미단위로 범위를 나눈 것. 예를 들면 메모리 내의 코드, 스택 등의 공간
의미단위로 범위를 나누기 때문에 segment의 크기가 균일하지 않다.
logical address 는 다음의 두 가지로 구성된다.
segment-number
offset → d
segment table
모든 테이블은 base 와 limit 값을 가지고 있다.
base : starting physical address of segment. 즉, 물리적 메모리에서 세그먼트의 시작점을 나타낸다.
limit : lenght of the segment. 세그먼트의 길이를 나타낸다.
segment table base register - STBR
물리적 메모리에서의 segment table의 위치
segment table limit register - STLR
프로그램이 사용하는 segment의 수
segment number s < STLR 이어야 한다.
페이징 기법과 다른 점
페이징 기법의 경우, 모든 페이지의 단위가 같기 때문에 물리적 메모리 내부에 fragment 위치를 table 에 매핑하고 있으면 되었지만,
세그먼트 기법의 경우, 모든 세그먼트의 단위가 다르기 때문에 테이블에는 정확한 물리적 메모리의 byte 주소를 가지고 있어야 한다.
장점
protection
각 세그먼트별로 protection bit 가 존재한다.
각각의 entry 가 아래를 만족함
valid bit = 0 이면, illegal segment 라고 판단한다.
read, write, execution 권한 bit → 의미단위로 의미를 나누기 때문에 세그먼트별로 권한 분할이 가능하다.
sharing
shared segment
same segment number
segment 는 의미 단위이기 때문에 공유와 보안에 있어서 paging 보다 훨씬 유리하다.
paging 기법과 비교해보았을 때, 훨씬 페이징 테이블 개수가 적어서 메모리 낭비가 적다.
paging : 100만개
segment : 5개
단점
allocation : first fit, best fit
의미 단위로 길이가 유동적인 세그먼트들이 쌓이기 때문에 가장 첫번째로 쌓인 것이 잘 쌓이게 된다.
external fragmentation 이 발생한다.
segment 길이가 동일하지 않으므로, 가변 분할 방식에서와 동일한 문제점들이 발생하게 된다. → hole
allocation 문제가 발생할 수 있다.
paged segmentation
paging + segmentation
paging 기법과 segmentation 기법의 장점을 가져와 융합해놓은 방법으로
segment table 에는 segment 자체의 base address 가 아니라, segment 를 구성하는 page table 의 base address 를 가지고 있다.
실제 컴퓨터에는 segment 로만 이루어진 경우는 거의 없고 사실상 paging 기법을 같이 사용하고 있다.
지금까지…
지금까지 우리는 다양한 물리적 메모리의 관리 기법에 대해서 알아보았다.
물리적 메모리 관리에서 가장 핵심이 되는 것은 결국 논리적 주소를 물리적 메모리 주소로 변환하는 과정이었다. →
주소변환하지만 이 모든 과정에서 운영체제가 하는 일은 거의 없었다. 모두 하드웨어가 수행하는 일들이었다.
왜 하드웨어에 의지할 수 밖에 없을까?
하나의 프로세스가 CPU를 가지고 논리적 메모리 주소에서 물리적 메모리 주소로 변환을 하는 과정에는 사실상 운영체제가 끼어들 필요가 없다.
운영체제의 개입이 필요하다는 말은 프로세스가 사용자 → 운영체제로 넘어간다는 것을 의미하는데, 메모리를 참조할 때마다 운영체제와 사용자 사이를 이동해야한다는 것은 말이 안된다.
따라서 이 모든 과정은 하드웨어적으로 이루어질 수 밖에 없다.
운영체제가 끼어들어야 하는 케이스는 바로 I/O 접근 때였다.
그렇다면 운영체제는 무엇을 하는가…?
물리적 메모리 주소 변환에서는 사실상 운영체제가 하는 일은 없다.
하지만 virtual memory 관리에서는 운영체제의 역할이 늘어난다.
Last updated
