Memory Managemnets

Memory Managements

 Logical address (=virtual address)

 - 프로세스마다 독립적으로 가지는 주소 공간 (프로그램 시작과 동시에 생성)

 - 각 프로세스마다 0번지부터 시작

 - CPU가 보는 주소는 logical address

  Physical address

 - 메모리에 실제 올라가는 위치. (하단에 커널, 그 위에 여러 프로그램 올라감)

   주소 바인딩 : 주소를 결정하는 것.

  주소 바인딩 (Address Binding)

 - Compile time binding(주소변환이 compile할때 발생) : 물리적 메모리 주소가 컴파일 시 알려짐. 시작 위치 변경 시 재 컴파일.  컴파일러는 절대 코드(absolute code) 생성 (무조건 0번지부터이기때문) =>  논리적=물리적 주소. 메모리 주소 바꾸고 싶으면 다시 컴파일.

 - Load time binding(실행 시작할때) : Loader의 책임하에 물리적 메모리 주소 부여.  컴파일러가 재배치가능코드(relocatable code)를 생성한 경우 가능. => 주소바꾸는 것 아니다. Logical->physical로.

 - Execution time binding(실행 이후 물리적 주소변환) = Run time binding : 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있다. CPU가 주소를 참조할 때마다 binding을 점검.(address mapping table).  하드웨어적인 지원이 필요하다. (e.g., base and limit registers, MMU).

  Memory-Management Unit(MMU)

 - MMU : logical address를 physical address로 매핑해주는 Hardware device.

 - MMU scheme : 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소 값에 대해 base register(=relocation register)의 값을 더한다.

 - user program : logical address만을 다룬다.  실제 physical address를 볼 수 없으며 알 필요가 없다.

   CPU가 346번지 내용을 요청한다 -> logical address 346 -> MMU의 relocation register가 14000이면, 346을 더해서 physical address가 14346이 되어 메모리로 간다. MMU의 limit register가 3000일 때 만약 CPU가 3460을 요청했으면 limit를 넘어서서 trap으로 빠진다.(CPU제어권이 OS에 넘어감.)

  Some Terminologies

 - Dynamic Loading : 프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 load하는 것. 필요할때 마다 load.  memory utilization의 향상.  가끔식 사용되는 많은 양의 코드의 경우 유용하다. ex) 오류 처리 루틴.  운영체제의 특별한 지원없이 프로그램 자체에서 구현 가능하다.

 - Dynamic Linking : Linking을 실행시간까지 미루는 기법.

   Static linking - 라이브러리가 프로그램의 실행 파일 코드에 포함됨. 실행 파일의 크기가 커짐. 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비. (ex 같은 printf라도 각 프로그램에서 개별적으로 실행.)

   Dynamic linking : 라이브러리가 실행 시 연결됨.  라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub 이라는 작은 코드를 둠.(stub은 별도의 파일로 존재하여, 어디있는지 연결.)  라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어옴.  운영체제의 도움이 필요하다.

 - Swapping : 프로세스를 일시적으로 메모리에서 backing store로 쫓아내는 것.(swap area. hard disk.)

   Backing store(=swap area) : 디스크 - 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간.

   Swap in/out : 일반적으로 중기 스케줄러(swapper)(메모리에 너무 많은 프로세스가 올라갔을때 일부를 내보내는 스케줄러)에 의해 swap out 시킬 프로세스 선정.  priority-based CPU scheduling algorithm - priority가 낮은 프로세스를 swapped out 시킴. priority가 높은 프로세스를 메모리에 올려 놓음.  Compile time 혹은 load time binding에서는 원래 메모리 위치로 swap in 해야한다.  Execution time binding 에서는 추후 빈 메모리 영역 아무 곳에나 올릴 수 있다.  swap time은 대부분 transfer time(swap되는 양에 비례하는 시간)임.

  메모리는 일반적으로 두 영역으로 나뉘어 사용.

 - OS 상주 영역 : interrupt vector와 함께 낮은 주소 영역 사용

 - 사용자 프로세스 영역 : Contiguous allocation : Fixed partition allocation, Variable partition allocation

                                 Noncontiguous allocation : Paging, Segmentation, Paged Segmentation

  Contiguous Allocation

 - Contiguous allocation : 

   Fixed partition(고정분할)방식 => 물리적 메모리를 몇개의 영구적 분할로 나눔. 분할의 크기가 모두 동일한 방식과 서로 다른 방식이 존재. 분할당 하나의 프로그램 적재.  융통성이 없다-> 동시에 메모리에 load되는 프로그램의 수가 고정됨, 최대 수행 가능 프로그램 크기 제한.  Internal fragmentation 발생 (external fragmentation도 발생)

   Variable partition(가변분할)방식 => 프로그램의 크기를 고려해서 할당. 분할의 크기, 개수가 동적으로 할당. 기술적 관리 기법 필요. External fragmentation 발생.

   External fragmentation(외부조각) : 프로그램 크기보다 분할의 크기가 작은 경우.  아무 프로그램에도 배정되지 않은 빈 곳인데도 프로그램이 올라갈 수 없는 작은 분할.

   Internal fragmentation(내부조각) : 프로그램 크기보다 분할의 크기가 큰 경우.  하나의 분할 내부에서 발생하는 사용되지 않는 메모리 조각.  특정 프로그램에 배정되었지만 사용되지 않는 공간.

   Hole : 외부, 내부 포함한 빈 공간. 가용 메모리 공간.  다양한 크기의 hole들이 메모리 여러 곳에 흩어져 있다. 프로세스가 도착하면 수용 가능한 hole을 할당. 운영체제는 할당공간과 가용공간 정보를 유지한다.

   Compaction : 1. 모든 외부조각을 모은다.  2. 큰 hole들만 모은다.

                      external fragmentation 문제를 해결하는 한 가지 방법.  사용 중인 메모리 영역을 한군데로 몰고 hole 들을 다른 한 곳으로 몰아 큰 block을 만드는 것. 매우 비용이 많이 드는 방법이다.  최소한의 메모리 이동으로 compaction하는 방법(매우 복잡한 문제).  Compaction은 프로세스의 주소가 실행 시간에 동적으로 재배치 가능한 경우에만 수행될 수 있다. (Run time binding 이어야한다).  전체 hole을 모으기 위해 전체 프로그램이 이동하는 것이 아니라 최소한의 프로그램만 이동하여 큰 hole을 만드는 것이 효율적이다. -> 어떤 프로그램이 이동할지 정하는 문제가 생김.

  Paging

  (CPU는 논리적 주소를 참조한다. why 물리적 x? -> 물리적 주소는 계속 변한다. 그럼 할당 받을 때마다 계속~)

 - Paging : Process의 virtual memory를 동일한 사이즈의 page 단위로 나눈다. virtual memory의 내용이 page 단위로 noncontiguous하게 저장된다.  일부는 backing storage에, 일부는 physical memory에 저장.

 - Basic method : physical memory를 동일한 크기의 frame으로 나눈다. logical memory를 동일 크기의 page로 나눈다.(frame과 같은 크기)  모든 가용 frame들을 관리하고, page table을 사용하여 logical address를 physical address로 변환한다. External fragmentation 발생 안하고,(같은 크기로 나눴기 때문) Internal fragmentation 발생 가능성이 있다.

  Page table은 main memory에 상주한다. page-table base register (PTBR)가 page table을 가리키고, Page-table length register (PTLR)가 테이블 크기를 보관한다. 모든 메모리 접근 연산에는 2번의 memory access가 필요하다.(page table 접근 1번, 실제 data/instruction 접근 1번). -> 시간이 2배이기 때문에, 속도 향상을 위해서 associative register 혹은 translation look-aside buffer(TLB)라 불리는 고속의 lookup hardware cache를 사용한다.

  Two-Level Page Table

 - 현대의 컴퓨터는 address space가 매우 큰 프로그램을 지원한다. 32 bit address 사용시에 2의 32승 의 주소공간(4G). page size가 4K시 1M개의 page table entry가 필요하다. 각 page entry가 4B시 프로세스당 4M의 page table이 필요하다. 그러나, 대부분의 프로그램은 4G의 주소 공간 중 지극히 일부분만 사용하므로 page table 공간이 심하게 낭비된다.

 - page table 자체를 page로 구성

 - 사용되지 않는 주소 공간에 대한 outer page table의 엔트리 값은 NULL(대응하는 inner page table이 없음)

  Multilevel Paging and Performance

 - Address space가 더 커지면 다단계 페이지 테이블이 필요하다.  각 단계의 페이지 테이블이 메모리에 존재하므로 logical address의 physical address 변환에 더 많은 메모리 접근 필요.  캐시 메모리를 통해 메모리 접근 시간을 줄일 수 있다.

  Memory Protection

 - Page table의 각 entry마다 bit를 둔다.

   Protection bit : page에 대한 접근 권한 (read/write/read-only)

   Valid-invalid bit : valid는 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음을 뜻한다.(접근 허용)

                           invalid는 해당 주소의 frame에 유효한 내용이 없음을 뜻한다.(접근 불허)

   프로세스가 그 주소 부분을 사용하지 않는 경우, 해당 페이지가 메모리에 올라와 있지 않고 swap area에 있는 경우.

   Inverted Page Table

 - page table이 매우 큰 이유 : 모든 process 별로 그 logical address에 대응하는 모든 page에 대해 page table entry가 존재한다.  대응하는 page가 메모리에 있든 아니든 간에 page table에는 entry로 존재한다.(공간 overhead가 크다.)

 - Inverted page table(메모리에 있는 부분만) : page frame 하나당 page table에 하나의 entry를 둔 것. 각 page table entry는 각각의 물리적 메모리의 page frame이 담고 있는 내용을 표시한다. (process id, process의 logical address).

   단점 : 테이블 전체를 탐색해야 한다. 공간 활용은 되나, 비용이 크다.  ==> associative register를 사용한다.(expensive) TLB를 사용하여, inverted page table 전체를 TLB에.

   Shared Page

 - Shared code : Re-entrant Code (= Pure code).  read-only로 하여 프로세스 간에 하나의 code만 메모리에 올린다. (eg, text editors, compilers, window systems).  Shared code는 모든 프로세스의 logical address space에서 동일한 위치에 있어야 한다.  

 - Private code and data : 각 프로세스들은 독자적으로 메모리에 올린다. (각각 다른 frame으로 매핑)  Private data는 logical address space의 아무 곳에 와도 무방하다.

  Segmentation

 - 프로그램은 의미 단위인 여러 개의 segment로 구성 : 작게는 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의.  크게는 프로그램 전체를 하나의 세그먼트로 정의 가능.  일반적으로는 code, data, stack 부분이 하나씩의 세그먼트로 정의됨.

 - Logical address는 <segment-number, offset>으로 구성.

 - Segment table (read-only) : each table entry has : base - starting physical address of the segment.  limit - length of the segment.

 - Segment-table base register (STBR) : 물리적 메모리에서의 segment table의 위치.

 - Segment-table length register (STLR) : 프로그램이 사용하는 segment의 수.
 - Protection : 각 세그먼트 별로 protection bit가 있음.  Each entry : Valid bit=0 -> illegal segment,  Read/Write/Execution 권한 bit  (bit 관련하여 paging과 동일하다.)

 - Sharing : shared segment, same segment number. ===> segment는 의미 단위이기 때문에 공유와 보안에 있어 paging보다 훨씬 효과적이다.

 - Allocation : first fit/best fit.  external fragmentation 발생. ===> segment의 길이가 동일하지 않으므로 가변분할 방식에서의 동일한 문제점들이 발생한다.

  Segmentation with Paging

 - pure segmentation과의 차이점 : segment-table entry가 segment의 base address를 가지고 있는 것이 아니라 segment를 구성하는 page table의 base address를 가지고 있다.

 - Segment가 여러개의 page로 구성되어, Allocation 문제가 안 생긴다. segment마다 page table 생김.

   프로세스는 segment 단위로, memory는 paging으로.  original segmentation 쓰는 memory는 현실적으로 X.