Virtual memory (fixed partition, variable partition, segmentation)

multi programming과 time sharing 시대가 도래하며 초기에는 process 전체에 권한을 주고 시간이 끝나면 모든 상태를 disk에 저장하는 방식을 사용했다. 당연히 이 방법은 매우 느렸다. 따라서 OS는 프로세스 전환 시 프로세스를 메모리에 유지하면서 time sharing system과 그에 따른 protection을 효율적으로 구현할 수 있게 설계되어야 했다.

Address Space

OS는 physical memory를 사용하기 쉬운 abstraction으로 만든다. 즉 address space는 running program의 view인 것이다.

Virtual Memory

virtual memory는 한정적인 DRAM을 여러 process가 나눠쓰기 위해 사용된다. 즉, process간 isolation 제공을 위해 사용된다.

virtual memory의 목표는 다음과 같다

1. transparency (투명성)
   프로세스는 메모리를 다른 프로세스와 공유하고 있다는 사실을 알아서는 안된다.
2. efficiency (효율성)
   너무 느리게 실행되어서는 안되고(시간), virtualization을 지원하기 위한 구조로 너무 많은 메모리를 사용해서는 안된다(공간). 나중에 등장하겠지만, 사용 공간을 절약하기 위해서 TLB라는 특별한 cache를 사용한다.
3. protection (보호)
   프로세스와 OS를 다른 프로세스로부터 보호한다. isolation의 의미는 어떤 프로세스가 다른 프로세스에 영향을 끼칠 수 없다는 것이다. 앞서 말했듯이, 프로세스는 메모리를 혼자 독차지하고 있다고 생각해야 한다. 즉, 각 프로세스에 private해야한다는 의미이다. 이를 위해 address translation이 필요하다. address translation때문에 두 프로세스가 같은 주소에 접근하더라도 physical address는 서로 다르게 된다.

Virtual memory를 구현하기 위한 여러가지 방법이 있다

Software-based relocation (static)

이 방법에서는 loader라고 불리우는 software가 실행하고자 하는 실행 파일의 모든 주소를 원하는 physical memory로 변경한다. 그러니까, 아예 프로그램 자체가 rewrite된다. software가 직접 바꿔주기때문에 하드웨어 서포트가 필요하지 않다는 장점이 있지만 protection이 되지 않고, 일단 한번 배치되면 나중에 주소공간을 재배치하는것이 어렵다는(static하다,,) 단점이 있다. 당연히 사용하지 않는 방식이다.

Hardware-based relocation (dynamic)

MMU(Memory Management Unit)이 address translation을 수행한다.

invalid virtual address에 대해 exception을 발생시키는 방법으로 하드웨어에 의해 protection이 된다.

OS는 현재 수행되고 있는 프로세스에 대한 valid address space 정보를 MMU로 넘긴다.

hardware-based relocation을 구현하는 방법에도 여러가지가 있다. (아래의 네 가지 방법!!)

● fixed partition

여기에서는 physical memory가 fixed partition으로 쪼개진다. 여기에서 각 partition의 크기는 고정되어있고, 모두 동일하다.(fixed partition이 이름인 이유!!)

따라서 partition의 수 = degree of multi-programming이된다.

OS는 이 partition의 starting point를 기억하고, translator는 그 주소(base register)를 더하는 방법으로 translation을 한다.

physical address = virtual address + base register

장점으로는 구현이 쉽고, context switch가 빠르다는 것이 있다.

하지만 치명적인 단점이 있다. internal fragmentation이다. internal fragmentation은 말 그대로 내부의 fragmentation이다. 각 partition의 크기가 고정되어있기 때문에, partition보다 작은 size의 program에도 partition 전체를 할당하기 때문에 당연히 사용하지 않는 부분의 memory waste가 생기게 된다. 이 방법은 partition size가 고정되어있기 떄문에 dynamic program에는 적합하지 않은 방법이다.

fixed partition을 조금 보완해보자면,

• partition 크기가 모두 동일한 필요는 없을 것이다.
• 그러므로 여러가지 partition size를 두고, 각 size에 대한 separated queue를 둔다.

● variable partition

physical memory를 여러가지 크기의 partition으로 쪼갠다.

그 후 VA(Virtual Address)와 limit address(size of partition)를 비교한다. 만약 limit address보다 작다면 base address와 더해 physical address를 구한다. limit address는 protection을 위해 존재한다.

이 방법을 구현하기 위해서 하드웨어는 limit와 base register라는 두 개의 register를 제공해 주어야 한다.

장점으로는 심플하고 저렴하게 구현할 수 있고, internal fragmentation이 없다는 점이 있다.

그러나 단점도 많이 있다.

먼저 각 process는 physical memory에서 연속적으로 할당되어야 한다.

그리고 external fragmentation이 발생할 수 있다. 얘도 말 그대로 partition 외부에서 발생하는 fragmentation이다. 프로세스 하나가 연속적으로 할당되어야하기 때문에 physical memory에는 비어있는 공간이 흩어져서 존재하게 된다.

또 partial sharing을 할 수가 없다. 즉, address space의 한 부분을 공유할 수가 없다.

● Segmentation

여기에서는 address space를 logical segment(code, data, stack, heap, …)로 나눈다. 이 segment들의 순서는 상관이 없다.

각 segment는 독립적으로 physical memory에 분리되어 배치되어야 한다.

그리고 이 segment들은 독립적으로 성장·수축하고, 보호되어야 한다.

virtual address는 <segment number, offset> 으로 표현된다.

segmentation과 variable partitioning의 다른점은, variable partition은 한 프로세스 당 한 개의 segment를 사용하지만, segmentation은 한 프로세스가 여러 개의 segments를 할당받는다는 것이다.

Segmentation서 addressing 하는 방법은 두 가지가 있다

1. 1. 1) explicit approach
      여기에서는 virtual address의 한 부분을 segment number로 사용하고, 남은 부분은 offset으로 사용한다.
      

      

      
      예를 들어, VAX/VMS system에서는 2bits를 segment number로써 사용하고, 이 두 비트를 이용해 segment의 종류를 판별한다
2. 2. 2) implicit approach
      memory reference type으로 segment를 결정한다.
      예를 들어, PC-based addressing이면 code segment이고,
      SP/BP based addressing이면 stack segment 이런 식으로 판별한다.
      Segmentation에서는 process 당 segment register 혹은 table이 존재해 그 process의 base, limit address 등을 저장해 둔다.
      

      

      
      장점으로는 먼저 address space를 sparse하게 할당할 수 있다. stack과 heap은 독립적으로 자라기때문에, free인 space를 찾기가 쉽다.
      또 각 segment를 protect하기가 쉽다. 각 segment마다 다른 권한을 부여하는 방식으로 구현하면 되기 때문이다. 예를들어, code segment같은 경우는 read-only로, system call같은 경우는 kernel mode only 이런 식으로 구현하면 된다.
      그리고 segment를 공유하기가 쉽다. 같은 translation을 base limit에 저장하면 되기 때문이다.
      마지막으로 각 segment에 dynamic reallocation이 제공된다.
      단점도 있다. 각 segment는 연속적으로 할당되어야 한다. 그러므로 variable partition과 같이 여전히 external fragmentation이 존재한다.
      위의 table을 저장하기 위한 large segment table도 필요하다. main memory에 저장되고, 속도를 위해 cache를 사용한다.

● Paging

paging은 너무 길어서 다음에 정리..