* 출처 : 유튜브 HPC Lab. KOREATECH

Non-Contiguous Allocation / Virtual Memory

Virtual Storage(Memory)

• 실행 시 필요한 block들만 메모리에 적재되고, 당시 필요 없는 block들은 swap device에 적재된다.

Address Mapping

• 상대적인 주소를 실제 물리적인 주소에 맵핑시키는 것.
  • Virtual address(relative, logical address) -> Real address

Non-continuous allocation

• 사용자 프로세스가 virtual address의 데이터를 요청
  • real address로 변환
  • 메모리에서 readl address의 데이터 접근
• 사용자 프로세스는 마치 실행 프로그램 전체가, 메인 메모리에 연속적으로 적재되었다고 생각하며 실행된다.

Paging System - Address Mapping

Paging System

• 프로그램을 같은 크기의 블록(페이지, Page)으로 분할한다.
  • 이를 관리하기 위한 자료구조가 필요해진다.(PMT)
• 메모리를 페이지의 크기로 모두 분할한다.
• 메모리에서 페이지가 들어갈 공간을 page frame(페이지를 넣는 틀)이라고 한다.
  • 따라서 페이지 프레임은 페이지와 크기가 같다.

• 하나의 프로세스가 위와 같이 많은 페이지들로 나뉘어지게 된다.

• 이 때 Swap device를 가상 메모리라고 생각해도 된다.

• 왼쪽과 같이 연속적이지 않고 떨어져서 메모리에 올라가는 것을 Non-contiguous allocation라고 하고, 프로세스를 페이지로 나눠서 저장해두는 것을 paging system이라고 한다.

• 특징

  • 크기에 따라 분할되었다.(논리적 분할이 아님)
    • segmentation 대비
      • page를 공유하거나, page를 보호하는 과정이 복잡하다.
        • 통째로 올라가있는 것이 아니라 잘게잘게 잘려있기 때문이다.
      • 같은 크기로 잘라놓았기 때문에 간단하고, 이로 인해 관리하기 편해서 효율적이다.
    • external fragmentation(외부 단편화)가 존재하지 않는다.
      • 중간에 프로세스가 종료되어 페이지들의 맵핑이 끊기더라도(메모리에서 빠지더라도), 다른 프로세스가 메모리에 올라갈 때 이미 페이지 단위로 나뉘어져 있고, 그 프로세스도 페이지 단위로 나뉘어져 있기 때문에 크기가 똑같아서 그 빠진 자리에 그 프로세스의 페이지가 들어갈 수 있어 외부 단편화가 존재하지 않는다.
      • 하지만 맨 마지막 페이지가 4KB가 아닐 수 있으므로 아주 작은 internal fragmentation(내부 단편화)은 발생할 수 있다.

paging system에서의 address mapping

• virtual address: v = (p, d)
  • p : page number
  • g : displacement(offset)
• address mapping
  • PMT(Page Map Table) 사용
• Page Map Table(PMT)
  
  • page number : 가상 주소 상의 페이지 넘버
  • residence bit : 이 가상 주소의 페이지가 메인 메모리에 올라가있는지 저장해두고 있는다.
    • 0 or 1
  • page frame number
    • 그 가상 주소의 페이지가 실제 물리적 메모리 어디에 올라가있는지
  • secondary storage address
    • swap device에서 그 페이지가 어디에 올라가 있는지
    • 페이지는 모두 swap device에 올라가 있다?
      • 맨 처음에 모두 swap device에 올라가 있는 상태에서 쓴다는 건가?

• Direct Mapping
  • 가장 간단한 address mapping 방법
  • 가정
    • PMT는 커널(kernel) 안에 저장되어 있다.
    • PMT entry 크기 = entrySize
    • Page 크기 = pageSize
  • 먼저 페이지가 메인 메모리에 있는지 검사한다.
    • PMT가 저장되어 있는 기본 주소인 b(PMT base address)가 있다고 가정.
    • b + p * entrySize으로 원하는 entry를 찾아간다.
    • p' * pageSize + d로 실제 메모리의 페이지를 찾고 거기서 offset을 통해 실제 원하는 r을 찾는다.
      • offset이 없다면 그냥 page만 찾게 되는 셈이다.
  • residence bit = 0인 경우
    • page fault가 발생한다.
      • 페이지를 읽는 데에 실패했다는 뜻으로, 아직 메인 메모리에 올라오지 않았다는 것이다.
      • swap device에 존재하는 그 page를 메모리에 적재한다.
      • page fault가 발생되면 context switching이 발생한다.
        • 해당 프로세스는 asleep 상태가 된다.
        • 해당 페이지를 swap device에서 읽어와야 한다.(I/O 작업으로 오버헤드가 크다)
        • 읽어오면 ready 상태가 되고 ready list로 올라가서 자신의 차례가 될 때까지 기다린다.
          
  • 문제점
    • PMT 또한 메모리에 존재하기 때문에 메모리를 2번 접근해야 하고 이로 인해 성능이 저하된다.
    • PMT를 위한 메모리 공간이 따로 필요해진다.
  • 해결방안
    • Associative Mapping(TLB)
    • PMT를 위한 전용 기억장치(공간) 사용
      • Dedicated register or cache memory

Associative Mapping

• TLB(Translation Look-aside Buffer)에 PMT를 적재한다.
  • addressing 시에 옆에 두고 변환을 위해 사용하는, PMT를 탐색하기 위한 전용 하드웨어
  • Associative high-speed memory

• p를 요청하면, 하나씩 보는 것이 아니라 parallel search, 즉 병렬로 탐색해서 한 번에 반환되도록 하드웨어적으로 구현되어 있다.
  • TLB를 통해 PMT를 병렬 탐색이 가능하다.
    • low overhead, high speed
  • 하지만 비싸다.
    • 따라서 큰 PMT를 다루기는 어렵다.

Hybrid Direct / Associative Mapping

• 두 기법을 혼합해서 사용하는 것이다.
• 작은 크기의 TLB를 사용한다.
  • 기존 PMT는 그대로 메모리(커널 공간)에 저장해둔다.
  • 동시에, PMT 중 일부 entry는 TLB에 적재해둔다.
  • 일부이기 때문에 TLB는 작아도 된다.
  • 이 때 최근에 사용된 page들에 대한 entry를 저장한다.
  • Locality(지역성)이 활용된다.
    • 프로그램의 수행 과정 중, 한 번 접근한 영역 + 그 인접 영역은 다시 접근될 가능성이 높다.
      

• first trial : 처음엔 TLB에 접근하여 해당 페이지가 실제로 물리적 메모리 어디에 올라가 있는지, 즉 TLB에 p'가 존재하는지 찾는다. 존재하면 그냥 TLB에서 끝난다.(이 때 TLB는 병렬 탐색을 하기 때문에 속도가 아주 빠르다)
• second trial : 만약 TLB에 없다면 메모리(커널 공간)의 PMT에 접근하여 페이지를 찾는다.
  • PMT에는 프로세스의 모든 페이지들이 물리 메모리의 어디에 올라가있는지 다 저장되어 있다.
  • p' * pageSize + d를 하기 직전에(이 연산을 거치고 나면 p'가 아니게 되버리니까 이 때 해주는 듯) TLB에 들러서 해당 정보(page number, residence bit, page frame number 등등)를 저장해두어 나중에 또 요청이 들어왔을 때 빠르게 반환해줄 수 있도록 한다.

Paging System - Memory Management

Memory Management

• Page와 같은 크기로 미리 분할하여 관리 및 사용한다.(메모리를 일정한 크기로 미리 잘라놓는다)
  • Page frame, 페이지를 담아 놓는 틀이다.

• Frame Table
  • 잘라놓은 page들을 관리할 자료구조가 필요하다.
  • 그것이 Frame Table이다.
  • page frame당 하나의 entry가 필요하다.
  • page frame의 구성
    • Allocated/Available field : 실제로 그 page frame이 할당되었는지, 사용할 수 있는지
    • PID field : 할당되었다면 누가 가져갔는지
      • process id가 적힌다.
    • Link field : 페이지 요청이 들어오면 어디에다가(빈 공간) 넣어줄지 결정해야 한다.
      • 이러한 빈 공간을 관리하기 위한 리스트(free list)
      • linked list를 만드는 field이다.
      • list_elem이라고 생각하자.
    • AV : free list header를 가르키는 포인터
      • 즉 free list의 시작점이다.
      • 가장 처음으로 비어있는(할당되지 않은) entry를 가르킨다.

Page Sharing

• 여러 프로세스가 특정 page를 공유 가능하다.

  • ex. 어떤 프로그램이 함수를 만들었다.
    • 다른 프로세스가 해당 함수를 사용한다면, 그 프로세스는 이 프로그램이 만든 함수를 가르키게 한다.(공유)
  • Non_continuous allocation이라서 가능하다.
    • 만약 연속이었다면, A는 해당 함수를 포함한 채 연속적으로 모두 올라가야 한다. B도 해당 함수를 쓴다면 마찬가지로 연속적으로 올라가야 하기 때문에 A와 해당 함수가 적혀진 메모리를 겹쳐서 올라갈 수 없다.

• 공유 가능 page

  • function 등 pure한 코드를 공유할 수 있다.
  • data 영역도 공유할 수 있다.
    • 읽기만 할 수 있는 데이터
    • 읽기, 쓰기 둘 다 할 수 있는 데이터
      • concurrency 제어 기법(락, 세마포어, 컨디션 밸류 등) 관리하에 사용이 가능하다.

Page Sharing Example

• 프로세스 1, 2, 3는 모두 ed1, ed2, ed3를 사용하고 있다.
  • ed1, ed2, ed3를 따로따로 만들어줄 필요 없이 하나의 ed1, ed2, ed3를 가르키게 하여 메모리 낭비를 줄인다.

• Data Page sharing
  
  • p'가 같아짐으로써, 원하는 데이터는 같지만 프로세스가 달라도, 같은 페이지 프레임이 접근할 수 있게 된다.
    • 즉 서로 다른 두 프로세스가 똑같은 a 값을 원할 때, 서로 페이지 테이블은 달라도 결국엔 page frame number가 같으니 둘 다 같은 page frame에 접근하게 된다.

• Procedure Page Sharing
  
  • 어떤 페이지 프레임 p'에, k1에서 d만큼 떨어진 곳에 가라는 branch가 존재한다면,
  • 프로세스2 입장에서는 k2에서 d만큼 떨어진 곳으로 가야 하는데, 아무 상관 없는 자신의 k1에서 d만큼 떨어진 메모리에 접근하게 되는 것이다.
  • Solution
    
    • 이름을 통일시킨다.
    • k1, k2가 아닌 그냥 k로 저장한다.
    • 즉, 프로세스들이 shared page에 대한 정보(페이지 프레임)를, PMT의 같은 entry에 저장하도록 한다.

Page Protection

• 여러 프로세스가 page를 공유할 때,
  • protection bit를 사용한다.
    • 이 페이지에 접근한 프로세스가 어떤 활동을 할 수 있는지 페이지 테이블에 적어놓는다.

Paging System - Summary

• 메모리를 미리 고정된 크기(페이지 크기, 4KB)로 잘라 놓는다.
• 외부 단편화 문제가 없어진다.
• 논리적인 구조를 고려하지 않았기 때문에, 통째로 넣어놓지 않고 여러 개에 걸쳐서 넣었기 때문에
  • 그 각각의 페이지를 보호하고, 혹은 공유해야 하므로 각각 접근하는 데에 복잡해질 수 있다.
• 필요한 페이지만 페이지 프레임에 적재하여 사용하기 때문에 메모리를 효율적으로 활용할 수 있다.
• 메모리 공간에 2번 접근해야하기에, 페이지 테이블이 메모리에 적재되어야 하기에
  • 메모리 공간이 추가적으로 필요하고 시간 또한 더 걸릴 수 있다.
  • 이를 TLB라는 하드웨어로 해결한다.
    • 하지만 하드웨어 비용이 증가하게 된다.

---

Segmentation System

• Non-continuous Memory Allocation
• 프로그램을 논리적인 block(segment)으로 분할한다.
  • segment의 크기가 서로 다를 수 있다.
  • ex. stack, heap, main procedure, shared lib 등
• 특징
  • 어떤 크기의 segment가 들어올지 모르니 메모리를 미리 분할하지 않는다.
  • 통째로 들어오기 때문에 segment sharing/protection이 용이하다.
  • 크기가 각각 다르기 때문에 관리하기 까다로울 수 있다.(오버헤드 증가)
  • 들어온 만큼 짤라서 주기 때문에 공간이 남아버릴 걱정은 하지 않아도 된다.
    • No internal fragmentation
    • External fragmentation은 발생 가능하다.
      • 어떤 segment가 빠졌을 때, 새로운 segment가 그 빠진 공간으로 못 들어갈 수도 있다.(외부 단편화)

Segment Map Table

• 논리적인 하나의 세그먼트로 나뉘어지기 때문에, 쉽게 보호가 가능하다. 그냥 통째로 보호하면 된다.

  • protection bits를 이용한다.

• 세그먼트마다 크기가 다르기 때문에 segment-length가 생긴다.

  

Address mapping(direct mapping)

• 프로세스 SMT가 저장되어 있는 주소 b에 접근
• SMT에서 entry를 찾는다.
  • segment의 위치 = b + s * entrySize
• 다음을 순차 진행
  • residence bit가 0일 경우(메모리에 없을 때)
    • missing segment fault
    • swap device로부터 segment를 가져와, SMT를 갱신시키면서(residence bit를 수정하는 등) 메모리에 적재시킨다.
  • 변위 d(offset)이 segment 길이 보다 큰 경우(d > ls)
    • segment overflow exception 처리 모듈 호출
  • 허가 되지 않은 연산을 하려 할 경우(ex. R인데 W를 하려 할 경우)
    • protection bit field(read/write/execute/access) 검사
    • segment protection exception 처리 모듈 호출
  • 실제 주소 계산
    • r = as + d
  • r로 메모리에 접근한다.

Segmentation system의 Memory management

Segment sharing/protection

Summary

• 전용 하드웨어는 TLB 같은 것을 말한다.

Paging vs Segmentation

• Paging
  • 간단하여 관리하는 오버헤드가 적다.
  • 나누는 데에 있어 논리적으로 구분하지 않기 때문에, 공유하거나 보호하는 것이 복잡하다.
• Segmentation
  • 크기가 각각 다르다보니 관리하는 오버헤드가 크다.
  • 논리적으로 나누어 놓았기 때문에, 공유하거나 보호하는 메커니즘이 간단하다.

---

Hybrid Paging / Segmentation

• Paging과 Segmentation의 장점을 결합했다.

• 프로그램 분할

  • 논리 단위의 segment로 분할한다.
  • 각 segment를, 고정된 크기의 page로 분할한다.

• page 단위로 메모리에 적재시킨다.
  

Address mapping

• virtual address : v = (s, p, d)
  • s : segment number
  • p : page number
  • d : offset in a page
• SMT와 PMT를 모두 사용한다.
  • 각 프로세스마다 하나의 SMT
  • 각 segment마다 하나의 PMT
• Address mapping
  • Direct, associated 다 가능.
• 메모리에는 결국 page가 올라가게 된다.

SMT와 PMT

• residence bit가 없다.
  • 실제로 메모리에 올라가는 것은 page이기 때문이다.
• 각 segment에 대한 PMT가 어디 있는지, PMT address가 존재한다.
  

Address mapping table

• Pi는 프로세스 넘버
• 프로세스에 대한 SMT가 존재하고
• 각 세그먼트에 대한 PMT가 존재한다.

Direct address mapping

• 메모리 접근을 3번하게 되지만, 그만큼 메모리 낭비를 줄이는 장점이 있다.
  • 메모리 접근을 3번하게 되어 느려지는 단점은 TLB라는 하드웨어를 이용해 줄일 수 있다.

Summary

• 장점
  • 논리적 분할 segment 장점과 고정 크기 분할 page의 장점을 결합
    • page sharing, protection이 쉽다.(segment 별로 관리하면 된다)
    • 실제 메모리 관리는 page라는 고정된 크기로 나눠서 하기 때문에 메모리 할당/관리 오버헤드가 적다.
      • 계속 크기를 다르게 하고, 그 다른 크기를 또 관리하고, 즉 사이즈가 달라질 필요 없이 그냥 4KB로 계속 고정된 크기로 관리하면 되기 때문인가?
    • No external fragmentation
      • 내부 단편화는 가능하다.
• 단점
  • 전체 테이블의 수가 증가한다.
    • 메모리 소모가 크다.
    • Address mapping 과정이 복잡하다.
  • Direct mapping의 경우, 메모리 접근이 3배가 된다.
    • 성능이 저하될 수도 있다.