200613_OS_14.md

OS 정리 14

Chapter 8 - Memory Management

Background

• CPU 스케줄링의 결과로, 우리는 다음 두개를 개선시킬 수 있다.
  • CPU 사용률
  • 컴퓨터의 사용자에 대한 반응 속도
• 이 성능 향상을 실현하기 위해서 우리는 주 메모리에 여러개의 프로세스가 올라와 있도록 관리해야한다.
• 프로그램은 실행되기 위하여 반드시 메모리에 올라와서 프로세스들 사이에 위치해야한다.
  • 각 프로세스들은 분리된 메모리 공간 을 가지고 있다. 이를 위해 특정 프로세스만 접근할 수 있는 합법적 메모리 주소 영역이 설정되어있어야 한다.
  • Base register 와 limit register 는 물리 메모리에서 프로세스의 주소영역을 결정하는데에 필요하다.
  • 기준 레지스터는 가장 작은 합법적인 물리 메모리 주소값을 저장한다( 영역의 최소 주소를 가리킨다)
  • 상한 레지스터는 프로세스 주소 공간의 크기를 저장한다. (영역의 offset을 저장함으로써 영역 상한을 가리킨다)

H/W address protection with base and limit register

• 메모리 공간 보호 는 CPU 하드웨어가 사용자모드에서 만들어진 모든 주소와 레지스터(기준/상한)을 비교함으로써 이루어진다.
• 사용자 모드에서 실행되는 프로그램에 의해 운영체제의 메모리공간이나 다른 사용자 프로그램의 메모리공간으로 불법적인 메모리접근 이 일어나면 OS는 이를 치명적인 에러로 간주하고 trap 을 발동시킨다.

Input queue

• 프로그램은 원래 이진 실행 파일 형태로 디스크 에 저장된다.
  • 이 프로그램이 실행되기 위해서는 주 메모리로 올라와서 "프로세스"가 되어야 한다.
  • 사용하는 메모리 관리기법이 무엇이느냐에 따라서, 프로세스는 실행하는 동안 디스크와 주 메모리 사이를 왔다갔다 할 수 있다.
  • 디스크에서 주 메모리로 들어오기를 기다리고 있는 프로세스들의 집합은 input queue 를 형성한다.
• input queue - 디스크에서 주 메모리로 들어오기를 기다리고 있는 프로세스들의 집합

Logical vs Physical Address Space

• 프로그램에 의해 생성된 모든 논리 주소 집합을 논리주소공간 logical address space 라고 하며, 이 논리 주소에 상응하는 모든 물리 주소 집합을 물리주소공간 physical address space 라고 한다.

  • 논리 주소 - CPU에 의해 만들어지며, virtual address 로도 불린다.
  • 물리 주소 - 메모리유닛에 의해 보여지는 주소

• 논리주소와 물리주소는 컴파일 타임에는 동일하다.

• 논리(가상) 주소와 물리주소는 실행시간바인딩 execution-time address-binding 기법과 적재시바인딩 load-time address 에서는 다르다.

• 이를 단순하게 설명하면 다음과 같다.

  • 우리가 코드를 짜서 컴파일 했을 때(logical address), 프로그램은 순차적인 주소로 만들어져 있으므로 정확히 어느 라인에서 문제가 생겼는 지 체크할 수 있다.(ex- 코드의 48번라인에 세미콜론이 빠져있다던지)
  • 그런데 실제로 메모리에 저장될 때는, bound와 limit 사이에 무작위로 흩뿌려져서 코드가 저장된다.
  • OS는 이를 mapping 시킨다. OS가 임의로 논리주소->물리주소 변환한다음 저장시키므로, 해당 주소 공간 내에서 우리는 메모리 주소 내에 어떤 순서로 들어가 있을지 예측할 수 없다. 이런 방식을 paging이라고 하고, 이후에 배울 것이다.
  • 따라서, 여기서 기억할 점은 논리주소와 물리주소가 결과적으로 달라진다는 점이다.

Address Binding : Instructions and Data to Memory

• 메모리 주소공간에서 명령어와 데이터의 바인딩은 바인딩이 이루어지는 시점에 따라 세가지로 구분된다.
  • Compile time : 프로세스가 메모리 내에 들어갈 위치를 컴파일 시간에 미리 알 수 있으면 컴파일러는 absolute code 를 생성할수 있다. 그러나 만일 이 위치가 변경되면 재컴파일해야한다.
  • Load time : 프로세스가 메모리 내 어디에 올라오게 될 지를 컴파일 시점에서 알지 못하면 컴파일러는 일단 이진 코드를 relocatable code 로 만든다.
  • Execution time : 프로세스가 실행하는 중간에 메모리 내의 한 세그먼트로부터 다른 세그먼트로 옮겨질 수 있다면, 바인딩이 실행시간까지 허용되었다고 할 수 있다.
    • 이 방식은 주소 맵에 대한 특별한 하드웨어적 지원이 필요하다(예 - 기준, 상한 레지스터 등)

Memory Management Unit(MMU)

• 논리주소와 물리주소를 연결해주는 하드웨어 장치이다.
• MMU scheme 에서, 재배치 레지스터의 값은 주소가 메모리로 보내질 때 사용자 프로셋에 의해 생성된 모든 주소에 대해 더해진다.
• 사용자 프로그램은 논리주소 를 담당한다.
• 진짜 물리주소 는 결코 알수 없다.

• 예를 들어, 재배치 레지스터의 값이 14000이라면 프로세스가 346번지를 액세스할 때 실은 주메모리의 14346(346 + 14000)번지를 액세스하게 된다.
• 사용자 프로그램 내에서는 346번지에 대한 포인터를 가지고 레지스터에 저장, 연산, 비교 등의 온갖 일을 다하지만, 메모리에 참조하는 순간 기준 레지스터(여기서는 재배치 레지스터)를 기준으로 재배치된다.

---

Swapping

• 프로세스 는 일시적으로 주 메모리에서 보조 메모리(ex- 하드디스크)로 내려갔다가 다시 되돌아 올 수 있다.
  • 이를 swap in, swap out이라고 일컫는다.
• Backing store
  • 모든 유저의 모든 메모리 이미지 복사본을 다 수용할 수 있을 만큼 충분히 큰 고속 디스크
  • 이러한 메모리 이미지들에 대해 직접 액세스를 제공해야만한다.
• Roll out, roll in : 스와핑은 스케줄링 알고리즘의 우선순위에 따라 달라진다. 낮은 우선순위의 프로세스는 높은 우선순위 프로세스가 로드되어서 실행될 수 있도록 스왑 아웃된다.
• 스왑 시간의 대부분은 transfer time 이다.
• 총 transfer time은 스왑되는 메모리 량에 정비례한다.
• UNIX, Linux, Windows 등의 많은 시스템에서 수정된 스와핑을 채택하고 있다.

• 주 메모리 공간이 충분하지 않으면, Dispatcher 는 프로세스를 backing store 에 있는 input queue 로 스왑아웃시킨다.
• 주 메모리 공간이 확보되면, Dispatcher 는 프로세스를 backing store에서 준비 큐로 불러들인다.

---

Contiguous Allocation

• 주 메모리는 일반적으로 두 개의 부분으로 나눠진다.
  • 메모리에 상주하는 OS를 위한 것 , interrupt vector 와 함께 하위 메모리 에 상주한다.
  • 사용자 프로세스 는 상위 메모리에 상주한다.
• Contiguous Allocation연속적 할당
  • 각 프로세스는 메모리 내에서 연속된 메모리공간을 하나씩 가진다.
  • 재배치 레지스터는 유저 프로세스를 서로로부터 보호하고, OS의 코드와 데이터를 변경하는것을 막기 위해 사용된다.
    • 재배치 레지스터는 가장 작은 물리주소값 을 저장하고있다.
    • 상한(한계) 레지스터는 논리주소의 범위 값을 저장한다 - 각각의 논리주소는 상한 레지스터보다 더 작아야한다

• 각 프로세스들은 연속된 공간을 가진다. 파란색 부분은 empty spae이고, 만약 P4가 들어온다면 저 공간으로 들어오게 될 것이다.

• Protection with limit and relocation register

  • 각 논리주소는 상한 레지스터보다 작아야한다.
  • MMU는 논리주소를 메모리로 보낼 때 재배치레지스터의 값을 동적으로 더해서 매핑시킨다.

• Hole 자유공간 : 사용가능한 메모리 공간 ; 메모리 곳곳에 다양한 사이즈로 흩어져있다.

• OS는 allocated partition 과 free partitions(hole) 에 대한 정보를 유지하고 있다. (어떤 부분이 사용되고 있고, 어떤 부분이 사용되지 않는가를 파악할 수 있는 테이블을 유지하고있다)

• 프로세스가 시스템에 들어오면, OS는 그것을 수용할 수 있을 정도로 충분히 큰 hole로부터 메모리를 할당한다.

• Dynamic Storage Allocation Problem 동적 메모리 할당 문제

  • 자유 공간의 리스트에서 n 크기의 블록 요청을 어떻게 만족시킬 것인가?
  • 최초적합 First-fit : 들어갈 수 있을만큼 충분히 큰 첫번째 hole을 사용
  • 최적적합 Best-fit : 들어갈 수 있을만큼 충분히 큰 hole중 가장 작은 hole을 사용
    • 크기순으로 정렬된 것이 아니면 모든 리스트를 다 훑어봐야한다.
    • 가장 작은 잔여공간만을 남겨둔다.
  • 최악적합 Worst-fit : 가장 큰 hole을 사용
    • 크기 순으로 정렬된 것이 아니면 모든 리스트를 다 훑어봐야 한다.
    • 할당하고 남게된 hole이 충분히 커서, 이것이 다른 프로세스들을 위해서 유용하게 사용될 수 있다.

• ​ 스피드와 저장공간 사용측면에서 최초/최적적합이 최악적합보다 낫다.

Fragmentation

• External Fragmentation 외부 단편화 - 전체 메모리공간이 요청을 만족시키지만, 연속적이지는 않다.

• • 이런식으로 군데군데 메모리를 사용하면 중간에 끼어있는 빈 공간들이 프로세스가 들어가는 크기는 못되고, 결과적으로는 너무 많은 빈 공간이 생겨서 아주 비효율적일수있다.
  • 메모리가 너무 많은 수의 매우 작은 조각들로 단편화되어 있는 것이다.

• Internal Fragment 내부 단편화 - 요청공간보다 조금 더 많은 메모리를 할당해야 할수도 있다.

• • 이 사이즈 차이는 분할된 조각 내부에 존재하는, 현재 사용되고 있지 않은 메모리이다.

• 외부 단편화를 compaction 으로 줄일수 있다. ex-디스크조각모음

• • 사용가능한 메모리들을 전부 모아 하나의 블록으로 만들기 위해 메모리를 셔플한다.
  • 압축은 재배치가 수행시간에 동적으로 이루어지는 경우에만 가능하다.
  • 프로세스를 계속 옮겨야하므로 당연히 복사 시간이 오래 걸린다.

---

Paging - 메모리 관리 기법의 일종

• 다음을 허용한다.

• • 물리주소가 애초에 noncontiguous 여도 상관없다
  • 프로세스는 물리주소가 가용할때만 물리주소에 올라가게 된다.

• 물리주소 를 frame 이라는 정해진 사이즈의 블록 으로 나눈다. 사이즈는 일반적으로 2의 배수이다.

• 논리주소 를 page 라고 하는 같은 사이즈의 블록 으로 나눈다.

• 모든 가용한 프레임의 목록을 추적해둔다.

• n 사이즈의 페이지가 필요한 프로그램을 실행할 때, n사이즈의 프레임을 찾아서 프로그램을 메모리에 적재한다.

• 논리주소를 물리주소로 변환시키기 위해 page table 을 만든다.

• 외부 단편화는 없지만 내부 단편화는 존재한다.

• 풀이
  • 물리주소를 여러 조각의 페이지로 나누어놓고, 프로세스가 요구하는만큼 페이지를 나누어서 저장한다.
  • 예를들어 process가 40페이지를 요구한다면, 메모리는 비어있는 e1에서 10페이지를 주고, e2에서 15페이지를 주고, e3에서 15페이지를 줘서 프로세스를 여러 공간에 할당할 수 있다.
  • 대신에 내부 단편화가 발생된다. 할당은 항상 프레임의 정수배로 할당되기때문에, 프로세스가 더 필요한 공간이 한 프레임보다 더 작다면 프레임이 남는, 내부단편화가 발생한다. 이런 걸 보면 페이지 크기를 줄일수록 내부단편화를 줄일수 있다고 생각할 수있는데, 페이지 사이즈가 너무 작아지면 페이지 테이블이 커지므로 페이지 테이블이 차지하는 공간이 낭비된다. 적절한 중간선을 찾는것이 필요하다.
  • 그리고 내부 단편화가 발생하더라도 페이지 크기가 충분히 작으므로, 이전에 남던 단편화로인한 유휴공간보다 훨씬 더 적은 공간낭비가 발생한다.

Address Translation Scheme

• CPU에 의해 생성되는 논리주소는 아래와 같이 나뉜다

• • Page number (p) - 물리주소 내 각프레임의 기준 주소를 담아놓은 페이지테이블의 인덱스로서 사용된다.
  • Page offset (d) - 페이지 넘버를 가지고 페이지테이블에서 매칭한 기준주소에 페이지 변위를 더하면 메모리장치로 사상될 물리 주소가 된다.

• 만약 논리 주소공간이 2^m이고, 페이지 사이즈가 2ⁿ이면

  • 논리 주소의 상위 m-n 비트는 페이지 번호를 나타내고, 하위 n비트는 페이지 변위를 나타낸다.

• CPU가 페이지 번호를 말해주면, 페이지 테이블에서 해당 페이지 번호를 이용해 어떤 물리주소로 갈 것인지를 알려준다.
• 페이지 테이블은 물리주소에서 각 페이지의 기준주소를 가지고 있다.
• 페이지 테이블은 각 프로세스마다 형성된다.

• 위와 같이 페이지 0~3까지 사용하는 프로세스가 있을 때, 페이지 테이블에서 각 페이지당 어느 물리주소로 연결되어있는지를 알려준다.

• 예시

  • 한 페이지(프레임)의 크기 : 4(=2²)B, 따라서 n=2
  • 물리 메모리 : 32B
    • 8 프레임
    • 주소 표현에 5bit (32B = 2⁵ B 이므로)
    • 페이지 테이블 엔트리 표현에 3bit 사용
  • 논리 주소 공간 : 16(=2⁴)B , 따라서 m=4
    • 4 페이지
    • 주소 표현에 4bit (16B = 2⁴ B 이므로)
  • 논리 주소 4bit중
    • 상위 2비트(m-n)는 페이지 넘버
    • 하위 2비트(n)는 페이지 변위
  • 논리 주소 0 (0000)은
    • 페이지 0, 변위 0이므로 5 (페이지 0의 물리프레임 주소) * 4 (페이지 크기 4B) + 0 (변위) = 20
  • 논리주소 1011(1011)은
    • 페이지 2, 변위 3이므로 (1*4) + 3 = 7

• Page Table Size

  • 페이지 테이블 사이즈는 프로세스의 논리주소공간 크기와 페이지 테이블 엔트리(PTE)에 달려있다.
  • 상황에 따라 다를수도 있지만 일반적으로 PTE 는 4B이다.
  • 32bit 엔트리는 2³² 개의 물리페이지프레임 중 하나를 가리킬 수 있다.
  • 만약 프레임 사이즈가 4KB(=2¹² )라면 4B의 PTE를 가진 시스템은 [한 프레임의 크기 * 프레임의 총 갯수]를 계산했을 때 총 2⁴⁴ B(16TB)의 공간을 가리킬 수 있다.

• 새로운 프로세스가 생성될 때 4 페이지의 주소공간을 할당받는다면, OS는 4 페이지에 대응될 가용 프레임이 4개 있는지 확인해야한다.

Implementation of Page Table

• 페이지 테이블도 주 메모리 내에서 구현된다.

  • 페이지테이블 기준 레지스터(PTBR)은 페이지 테이블의 포인터이다(자체의 주소를 가리킨다).
  • 페이지테이블 길이 레지스터(PRLR)는 페이지테이블의 사이즈를 가리킨다.

• 이러한 방식에서 모든 데이터/명령어 접근법은 2종류의 메모리 접근을 거쳐야한다.

  • 페이지 테이블에 대한 접근
  • (페이지 테이블에서 얻은 정보를 바탕으로) 데이터/명령어 접근

• 두 번이나 메모리 액세스를 해야하는 문제는 Translation look-aside buffers(TLB) 라고 불리는 특수한 고속탐색 하드웨어의 사용으로 해결될 수 있다.

• TLB

  
  • 매우 빠른 연관(associative) 메모리로 구성된다.
    • 페이지 테이블에 대한 캐시이다.
  • TLB는 PTE의 일부 만을 가지고 있다.
    • CPU에 의해 논리주소가 생성되면, 해당 페이지 넘버가 TLB에 제출된다.
    • 페이지 넘버가 TLB에서 찾아지면(hit), 해당 프레임 넘버로 바로 메모리에 접근할 수 있다.
    • 페이지 넘버가 TLB에 없으면(miss), 페이지 테이블로 메모리 참조를 해서 찾아야한다.
    • 페이지테이블에서 프레임넘버를 찾으면, 그 이후에 메모리에 접근할 수 있다.
    • 이렇게 얻어진 페이지 넘버와 프레임 넘버는 TLB에 기록된다.
    • 만약 TLB가 꽉차면, OS는 교체작업을 수행한다.
      • 교체 방식 : LRU, random

• Effective Access Time

  • Hit ratio (⍺)
    • TLB에서 페이지 넘버를 찾는 비율
    • 80%의 적중률 : 원하는 페이지를 10번을 찾았을 때 8번을 TLB에서 찾을 수 있다는 얘기
  • 다음과 같이 가정하자.
    • TLB Lookup time (TLB 탐색 시간) = ε 시간
    • 메모리 접근 시간 = τ 시간
  • Effective Access Time(EAT)
    • EAT = (τ + ε ) * ⍺ + (2τ + ε ) * (1 - ⍺)
    • = [TLB에서 찾았을 경우(전체 * 적중률) : TLB 탐색시간 + 메모리접근시간] + [TLB에서 못 찾았을 경우(전체 * 미적중률) : TLB 탐색시간(하였으나 실패) + 2번의 메모리 접근(페이지 테이블, 물리 메모리)]

Shared Pages

• 페이징의 장점은 code sharing 이 가능하다는 점이다. 이 점은 시분할(time sharing) 환경에서 특히 중요하다.
• Shared Code
  • 단 하나의 읽기 전용 코드(reentrant code, 재진입 가능 코드) 사본만 프로세스들간에 공유된다 (ex- 텍스트 편집기, 컴파일러, 윈도우 시스템 등)
    • 재진입 가능 코드는 스스로 수정할 수 없는 코드이므로, 실행 도중에 절대로 변하지 않는다.
  • 공유 코드는 모든 프로세스의 논리주소공간에 동일한 위치에 존재해야한다.
• Private code and data
  • 각 프로세스는 분리된 코드와 데이터도 가지고 있다.
  • 프라이빗 코드와 데이터를 저장하는 페이지는 논리주소공간의 아무곳에나 저장 될 수있다.

• 텍스트 에디터를 쓰는 40명의 유저가 있다면, 텍스트 에디터에는 각 150KB의 코드, 50KB의 데이터가 있다.
• 각 프로세스마다 저장한다면 200 * 40 = 8000, 8000KB가 필요하다.
• 그러나, 이 코드가 만약 reentrant code 라면, 15040 대신 150 * 1 = 150KB만 코드 공간으로 있으면 될 것이다. 이 경우 150 + 5040 = 2150, 2150KB의 공간만 사용하면 된다.
• 페이지 테이블 자체는 모두 다 다르게 가지고 있는 데, 그 내부에 재사용되는 페이지(reentrant code 페이지)만 모든 프로세스에 같은 넘버로 저장되어있다고 생각하면 된다.

---

Page Table Structure

Hierarchical Page Tables

• 시스템에 32bit의 논리주소공간이 있고, 페이지 크기가 4KB라면 페이지 테이블 크기는 2²² = 4 MB로 너무 커진다.

• 따라서 이 문제를 해결하기 위해, 페이지 테이블을 여러개의 작은 조각 으로 나눈다.

• 간단한 방법으로 two-level page table 이 있다.

  • 논리주소 = [페이지넘버 + 변위] 인데, 페이지 넘버 부분을 두 파트로 나누어 p1은 outer page table의 인덱스이고, p2는 p1이 가리키고 있는 페이지 내의 변위이다.

• 이 때, 원래 페이지 넘버를 이루던 20비트를 10비트씩 두 파트로 쪼갰으므로, 각 파트는 2¹⁰ 개의 엔트리를 가리킬 수 있게 된다.

Hashed Page Tables

• 32비트보다 큰 주소공간 을 다루는 일반적인 방식이다.
• 가상 페이지 넘버 가 페이지 테이블에 해싱되어있다. 해시 페이지 테이블의 각 항목은 연결 리스트를 가지고 있고, 이 리스트에는 collision이 일어나 모두 한 곳으로 해시되는 원소들이 연결된다.
  • 각 원소들은 세 가지의 필드로 이루어져있다.
    • 가상 페이지 넘버, 매핑된 페이지프레임 번호, 연결 리스트 상의 다음 원소를 가리키는 포인터
  • 가상 페이지 넘버는 해시값과 일치할 때까지, 연결리스트의 원소들과 하나하나씩 차례대로 비교된다.

Inverted Page Table

• 보통 프로세스는 각자 하나씩 페이지 테이블을 가진다.
  • 단점 : 물리메모리의 매우 많은 부분이 소모된다.
  • 이 문제의 해결책으로 제시된 것이 Inverted Page Table 이다.
• 메모리 내의 각 페이지 프레임에 대해 단 하나의 엔트리(페이지 테이블 내의 한 칼럼)를 가지고 있다.
• 엔트리는 다음과 같이 구성된다.
  • 실제 메모리 주소를 기준으로, 해당 주소에 저장된 페이지 넘버들
  • 해당 페이지를 소유한 프로세스의 ID
• 각 페이지 테이블을 저장하는 메모리는 줄어들지만, 페이지 참조가 발생할 때 테이블을 탐색하는 시간이 늘어난다.

---

Segmentation

• 추후에 다시 정리한다.