운영체제 - Memory Management

• 주기억장치 관리
  - 주소 바인딩
   : 프로그램을 작성할 때, 프로그래머는 기호 주소를 사용한다. 즉, 변수를 선언하고 이 변수 이름을 통해 주소를 접근
   : 프로그램은 실행되기 전에 이런 기호 주소를 실제 주소로 바인딩해주어야 한다.
   : 주소 바인딩 시기
   ■ 컴파일 시간(Compile time)
    : 컴파일러가 프로세스가 어디에 적재될지 알고 있으면 컴파일할 때 주소를 바인딩할 수 있다.
   ■ 적재 시간(Load time)
    : 컴파일할 때 프로세스가 어디에 적재될지 모르면 컴파일러는 재배치 가능 코드를 생성한다. 실제 바인딩은 적재할 때까지 지연된다. 재배치 가능 코드란 기준 위치 주소를 사용하는 코드를 말한다.
   ■ 실행 시간(Execution time)
    : 실행 도중에 프로세스의 적재 위치가 바뀔 수 있으면 바인딩은 실행될 때 이루어진다.
  
  
  
  - 논리(Logical) vs 물리적(Physical) 주소 공간
   : CPU에 의해 생성되는 주소는 보통 논리적 주소
   : 주기억장치가 접하게 되는 주소는 물리적 주소(MAR, Memory Address Register에 적재되는 주소)
   : 실행 시간 바인딩의 경우에는 논리적 주소와 물리적 주소가 다르며, 이 경우에는 논리적 주소를 가상주소(virtual address)라 한다.
   : 실행 시간 바인딩에서 논리적 주소와 물리적 주소 간에 매핑은 주기억장치-관리 장치(MMU, Memory-Management Unit)라 하는 하드웨어에 의해 이루어진다.
   
  
  - 가상주소는 왜 사용?
   : 현재 실행에 필요한 page만 memory에 올리고, 나머지는 swap device쪽에 있어라
   : 한 프로세스당 차지하는 memory 공간을 줄이자 (= multiprogramming degree를 높인다 = CPU utilization / throughtput이 높아진다)
   : 프로그래밍이 쉽다 (프로그래머가 물리적 메모리 사용량을 신경쓰지 않아도 됨)
   : memory에 프로세스를 load, swap하는 시간이 적게 든다.
  
  - 동적 적재 (Dynamic loading)
   : 초창기에는 프로그램이 실행되기 위해서는 전체 프로그램이 모두 주기억장치에 적재되어야 했다. -> 프로세스의 크기가 물리적 주기억장치 크
  기에 의해 제한된다.
   : 루틴이 호출될 때 주기억장치에 적재하는 방법
   : 모든 루틴은 재배치 가능 코드 형태로 디스크에 유지된다.
   : main 프로그램이 먼저 적재되며, 실행 도중에 다른 루틴을 호출해야 하면 이 루틴이 현재 주기억장치에 있는지 검사하고 없으면 재배치 가능 연결 적재기(relocatable linking loader)를 이용하여 루틴을 주기억장치에 적재한다.
   : 사용하지 않는 루틴은 주기억장치에 적재되지 않는 장점이 있다.
  
  - 동적 연결과 공유 라이브러리
    ■ 정적 연결(static linking)   
     : 프로그래밍 언어에서 제공하는 라이브러리를 프로그램과 결합하여 사용하는 방식
     : 모든 프로그램은 라이브러리의 복사본을 가지고 있다. 따라서 디스크 공간과 주기억장치 공간이 모두 낭비 된다.
    ■ 동적 연결(dynamic linking)
     : 라이브러리와의 연결이 실행 시간까지 연기되는 방식
     : 각 프로그램에 stub가 포함되며, 이 것은 주기억장치에 공유되고 있는 라이브러리 루틴에서 프로그램이 필요하는 루틴을 찾아주는 적은 양의 코드이다.
     : 어떤 루틴을 처음 호출할 때만 stub가 필요하며, 그 루틴을 다시 호출하면 주소 정보를 이용하여 바로 호출한다.
     : 라이브러리 갱신이 용이하고, 디스크 공간과 주기억장치 공간을 절약할 수 있다.
     : 다른 주소 공간을 접근해야 하므로 운영체제 지원이 필요하다.
  
  - 스왑핑 (Swapping)
    : 프로세스는 실행 도중에 일시적으로 주기억장치에서 디스크로 옮겨진 후에 나중에 다시 주기억장치에 적재되어 실행을 재개할 수 있다. 이 과정을 스왑핑(Swapping)이라 한다.
  
   
  
  - 연속적 공간 할당
   : 주기억장치는 운영체제 영역과 사용자 프로세스 영역으로 분리되며, 보통 운영체제는 하위 주소에 위치
   : 각 사용자 프로세스는 연속된 단일 영역을 할당받는다.
   : 운영체제를 사용자 프로세스로부터 보호해야 하며, 사용자 프로세스를 다른 사용자 프로세스로 부터 보호해야한다.
   : 이를 위해 기저(Base) 레지스터, 한계(Limit) 레지스터를 사용한다.
   
   : 운영체제는 현재 사용되고 있는 공간과 사용되지 않는 공간을 테이블에 유지한다.
   : 처음에는 운영체제가 적재되어 있는 공간을 제외하고는 모두 사용 가능하며, 사용 가능한 영역을 홀(hole)라 한다.
   : 어떤 홀에 프로세스를 할당할 것인가?
  
      ■ First-fit: 충분히 큰 첫 번째로 발견한 홀에 할당
      ■ Best-fit: 프로세스를 수용할 수있는 가장 작은 홀에 할당
      ■ Worst-fit: 가장 큰 홀에 할당
  
       => 외부 단편화 발생
           모든 홀을 합하면 프로세스를 수용할 수 있으나 연속 공간이 아니기 때문에 프로세스를 할당할 수 없는 경우
           -> 할당되어 있는 프로세스의 적재 위치를 재배치하여 하나의 큰 홀을 얻는 compaction 방법을 이용
       => 내부 단편화 발생
           할당된 메모리가 요구된 메모리보다 커서 사용되지 않아 낭비되는 경우
  
  

  - 페이징

     : 현재 가장 널리 사용되는 기법으로 프로세스에게 연속된 공간을 할당해주지 않아도 된다.
     : 운영체제 + 하드웨어를 연관시켜 구현
     : 물리적 기억장치는 고정된 크기의 프레임(frame)으로 나눔
     : 논리적 주소공간도 프레임과 같은 크기의 페이지(page)로 나눔
     : 오늘날은 4KB 또는 8KB의 페이지 크기 사용
     : 프로세스가 실행될 때 그것의 페이지는 사용한 어떤 프레임에도 할당될 수 있다.
     : 페이지 번호(p)와 페이지 오프셋(d)로 구성
    

     

    
    : 페이징을 사용하면 프로세스의 마지막 페이지는 프레임 크기보다 작을 수 있어서 최악의 경우 한 프레임의 대부분이 낭비될 수 있는 내부 단편화 발생
    : 페이지 크기를 줄여서 내부 단편화를 줄일 수 있지만 페이지 테이블의 크기가 커짐
    : 각 프로세스마다 페이지 테이블을 유지, 보통 PCB에 유지되어서 context switching 시간을 증가시킨다.
    : 운영체제는 주기억장치를 관리하므로 할당의 자세한 내용을 알고 있어야 하는데, 이를 위해 프레임 테이블을 유지, 프레임 테이블에는 실제 프레임마다 하나의 항이 존재히며, 프레임의 할당여부, 할당되어 있을 경우에는 어떤 프로세스의 몇 번째 페이지가 할당되어 있는지를 유지
   
   
    ■ 페이지 테이블 하드웨어 구현
       : 보호비트나 PTLR(Page-Table Length Register)을 사용하여 페이지 테이블의 크기를 나타내어 보호
  
      - 전용 레지스터 집합을 사용
      : 페이지 테이블이 작은 경우에만 가능
      : 주기억장치의 특정 영역에 페이지 테이블을 저장하고, 이것을 가리키는 주소만 레지스터에 저장한다. 이 레지스터를 PTBR (Page-Table Base Register)이라 한다.
      : 주기억장치를 접근하기 위해 항상 두 번의 접근이 필요하므로 접근 속도가 느리다.
  
     - 전용 캐시를 사용하는 방법
     : 이 캐시를 TLB(Translation Look-aside Bufer)라 하며, 보통 캐시와 마찬가지로 연관 매핑 방식을 사용한다.
     : TLB는 크기가 제한적이며, 비용이 비싸므로 페이지 테이블에 일부만 가지고 있으며, 캐시처럼 먼저 TLB를 검색한 다음에 찾고자 하는 페이지 정보가 없으면 주기억장치에 있는 페이지 테이블을 참조한다.
  
    

  
   
   ■ 페이지 테이블 구조
    - 계층구조 페이징
      

    - 해시 페이지 테이블
    

  
    - 역 페이지 테이블
    : 주기억장치의 각 프레임에 대한 항만을 가지고 있어, 이 항에는 이 프레임에 저장되어 있는 가상주소와 이것을 사용하는 프로세스의 식별자로 구성되어 있다.
  

   
    - 공유 페이지
    : 공통 코드의 공유 가능성이 있지만 여러가지 조건이 필요하여 쉽지 않다.
  
  
  
  

  - 세그먼테이션
   : 보통 사용자들은 주기억장치를 연속적 선형 공간으로 생각하지 않고, 순서가 없는 다양한 크기의 세그먼트의 집합으로 생각하는데 세그먼테이션이 이런 사용자 관점을 지원해주는 주기억장치 관리 기법
   : 외부 단편화가 발생할 수 있다.
   : 세그먼트 테이블을 사용하여 세그먼트 주소와 물리적 주소 간에 매핑
   : 세그먼트 이름과 오프셋을 이용하여 주소를 지정, 컴파일러가 사용자 프로그램을 번역할 때 자동적으로 세그먼트를 구성