Operating System: Memory Management (Chapter 7)

Address Binding

• instruction과 data를 실제 memory의 어디로 보낼지 결정하는 것
• 세 곳에서 address binding을 할 수 있다
  
  • Compile time binding
    • compile할 때 절대 불변의 address를 각 process에게 할당하는 방식
    • multiprogram이 가능해 지면서 이 방법을 사용하면 두가지 문제가 생긴다
      • 문제1: 하나의 메모리 주소를 다른 process들이 공유할 수 없어서 효율이 떨어진다.  
      • 문제2: 공유를 허용하면, process0가 잠시 메모리에서 내려간 사이에, 그 주소를 process1이 사용하면, 나중에 process0는 올라오지 못한다.
  • Load time binding
    • 위의 문제를 해결하기 위해 등장한 방식
    • 그러나 memory에 올라간 process에게 한칸 정도 이동해 줄 것을 OS가 요청할 때가 생기는데, 이런 상황에서 load time binding 방식은 전체 process를 reload해야하는 문제가 여전히 남는다
  • Execution time binding
    • 매우 flexible한 방식
    • OS에게는 memory에 대한 가상 주소만 전달하고, OS는 그 주소를 갖고 process를 실행시킨다
    • 따라서 가상 주소를 실제 주소 (physical address)로 변환해 주는 역할을 할 stack이 필요하다
    • 이 stack 연산은 OS 입장에선 상당히 느리기 때문에, 빠른 속도 연산을 위해 하드웨어의 도움을 받기로 한다
    • 그것이 바로 Memory Management Unit (MMU)이다. 

Address Mapping Table

• virtual address와 physical address 간의 mapping을 기록해둔 table

Base and Limit Registers

• Base register와 limit register가 phsysical address space를 결정한다. 
  • base register: 시작 주소를 의미
  • limit register: 사이즈를 의미

Memory Menagement Unit (MMU)

• 엄청나게 빠른 속도로 virtual address >> physical address 변환을 돕는 하드웨어
• virtual address + base register 를 통해 physical address에 접근하고, virtual address <= limit을 판단하는 하드웨어

Swapping

• Process는 memory에서 backing store로 일시적으로 swap out 될 수 있고, 적절한 시기(sometime later)에 다시 memory로 swap in 될 수 있다
• 이 때 그럼 memory에 process를 어떻게 올릴 것인지 할당 해 주는 정책이 몇 가지 있다

Contiguous Allocation 

• Memory에 process를 쪼개지 않고, 통으로 예쁘게 올려주는 것

Multiple Partition Allocation

• contiguous allocation 중에서도 Multiple-Partiton Allocation이라는 방식이 있다
  • User process가 올라갈 수 있는 영역이 한 덩어리가 아니고, 일정 크기의 partition으로 나눈다
  • 올라가고자 하는 process의 크기 > n개의 연속된 partition 크기 일 경우 n개의 연속된 partition을 합쳐서, 거기에 process를 올리는 방식
  • Hole: 비어 있는 영역을 의미.

Dynamic Storage-Allocation Problem

• Hole이 여러 개 있을 때, 그 중 어디에 process를 올릴지 결정하는 문제
• 세 가지 정도 방식이 있는데
  • First-fit: allocate the first hole that is big enough
    • 가장 적은 시간이 소요되서 time complexity 측면에서 가장 좋음
  • Best-fit: 전체 hole list를 다 확인하고, smallest hole that is big enough를 찾아서 할당
    • 자투리 공간을 활용할 수는 없음
  • Worst-fit: 전체 hole list를 다 확인하고, largest hole that is big enough를 찾아서 할당
    • 남는 자투리 공간이 크기 때문에, 자투리 공간을 활용할 수 있음
    • storage utilization 측면에서는 세가지 중 가장 안 좋은 방식

​Fragment

• 이런 자투리 공간을 fragment라고 함
• external fragment: process의 memory 영역으로 할당되지 않은 자투리
• internal fragment: process에게 할당된 영억 중, 실제 process가 사용하지는 않는 자투리. 이건 partitioning 단위가 있는 방식에서 발생. (예: 1.5K process에게 1K partition 2개 할당하면, 실제로는 0.5K가 그 안에서 놀고 있음)
• Compaction: external fragment들을 모아서 활용하는 것. 그러나 이것을 위해서는 execution time에 dynamic reloading이 가능해야한다

Paging

• 그래서 나온 개념이 paging
• virtual memory와 physical memory를 모두 잘게 쪼개서 process를 memory에 흩어서 올리자는 방식
• Contiguous 하게 process가 올라가지 않음
• frame: physical memory address 영역을 쪼개는 단위. 2의 지수 값으로 쪼갠다
• page: virtual memory address 영역을 쪼개는 단위로 frame과 같은 크기다
• Step1: free frame을 계속 tracking하고 있어야한다
• Step2: n pages로 구성된 process를 올리기 위해서는 n frames가 필요하다 
• Step3: memory mapping table인 page table을 만든다
• paging을 통해서 external fragment는 없어지지만, internal fragment는 여전히 존재한다

Translation Look-aside Buffer (TLB)

• paging의 장점: External fragment가 없어졌다
• paging의 단점: MMU가 바로 memory에 가는 것이 아니라, page table도 들려야 해서 memory 접근 overhead가 2배가 된다
• 매번 page와 frame 사이의 address mapping을 찾는 것의 overhead를 줄여보고자, 자주 접근하는 page에 대한 address mapping을 저장하는 cache를 만들었다
• 이것은 일종의 캐시이기 때문에 context switch가 발행하면 flushing된다
• Effective Access Time 
  • associative loopup : a 시간, memory access: b 시간, TLB hit ratio : e 일경우
  • EAT = (a + b) * e + (a + 2b) (1-e) = a + (2-e) b이다

Segmentation

• Paging이 sematic단위를 전혀 고려하지 않고, size만을 기준으로 memory address를 쪼갰다면, 이제 의미를 고려 해 보면서 자르는 방식
• 이 방식을 사용하면, 잘라진 조각을 process간에 공유 하는 등 다양한 활용이 가능
  • Protection (read/write를 semantic 단위로 허용 가능) 이 쉬워진다
  • process 간에 associated segments Sharing이 가능해진다
• 단점: memory allocation이 좀 복잡하다
• Paging과 다르게 internal fragment는 없고 external fragment는 존재
• MULTIX의 경우 segmentation 우선 적용해서 process memory를 segment 단위로 쪼개고, 그 segment를 page로 쪼개는 방식을 사용 (segmentation + paging 혼합)