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 register OR translation look-aside buffer 라고 불리는 고속의 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 관리에서는 운영체제의 역할이 늘어난다.