Chapter9 가상메모리

Chapter9 가상메모리

1. Vitrual Memory

• Non-continuous allocation
• 사용자 프로그램을 여러 개의 block으로 분할
  • 실행 시, 필요한 block들만 메모리에 적재
  • 나머지는 swap device(disk)에 존재

 

1.1 Address Mapping

• Continuous allocation인 경우
  • 상대 주소 사용 → 프로그램의 시작 주소를 0으로 가정한 주소
  • 메모리가 할당되면 할당된 주소에 따라서 상대 주소들을 조정함

  • 

• Non-continuous allocation인 경우
  • 가상(논리) 주소(Virtual address) 사용 → 연속된 메모리를 할당을 가정한 주소
  • address mapping을 통해서 가상 주소를 실제 주소(real address)로 매핑 함.

  • 

 

1.2 Block Mapping

• 사용자 프로그램을 block 단위로 분할 및 관리
• Virtual address : v = (b, d)
  • b : block number
  • d : displacement(offset) in a block

  • 

• BMT(Block Map Table)
  • Address mapping 정보 관리(커널 공간에 프로세스 마다 하나의 BMT를 가짐)

  • 

    
    
    • residence bit : 해당 블록이 메모리에 적재되어 있는지(1) 아닌지(0) 알려줌
• 과정

  • 

    
    
    1. 프로세스의 BMT에 접근
    2. BMT에서 block b에 대한 entry를 찾음
    3. Residence bit 검사
       1. Residence bit = 0인 경우
          • swap device에서 해당 블록을 메모리를 가져온 후 BMT의 정보를 업데이트(residence bit을 1로 바꾸고 나머지 정보를 변경)를 하고 3-2 수행
       2. Residence bit = 1인 경우
          • BMT에서 b에 대한 실제 주소 값 a 확인
    4. 실제 주소 r 계산(r = a + b)
    5. r을 이용하여 메모리에 접근

2. Virtual Storage Methods

2.1 Paging system

• 프로그램을 같은 크기의 블록으로 분할 ← 메모리는 page frame으로 한다(Memory Management 참조)
• 용어
  • page : 프로그램의 분할된 block
  • page frame : 메모리 분할 영역, page와 같은 크기로 분할

• 

• 특징
  • 크기에 따른 분할(논리적 분할 X) → 공유 및 보호가 복잡함
  • 간단하고 효과적
  • No external fragmentation
    • Internal fragmentation 발생 가능
• Virtual address : v = (p, d)
  • p : page number
  • d : displacement(offset)
• PMT(Page Map Table)을 사용하여 address mapping을 함

  • 

• Address mapping mechanism
  1. Direct mapping
  2. Associative mapping
  3. Hybrid direct/associative mapping

 

1) Direct mapping

• Block mapping 방법과 유사

• 

  
  
  1. 프로세스의 PMT가 저장되어 있는 주소 b에 접근
  2. PMT에서 page p에 대한 entry를 찾음(p의 entry 위치 = b + p * entrySize)
  3. entry의 residence bit 확인
     1. Residence bit = 0인 경우(page fault) → Context switching 발생
        • swap device에서 해당 page를 메모리에 적재하고, PMT를 갱신(residence bit를 1로 바꾸고 정보를 입력)을 한 후에 3-2 진행
     2. Residence bit = 1인 경우
        • 해당 entry에서 page frame 번호(p`)를 확인
  4. page frame과 가상 주소의 오프셋 d를 사용하여 실제 주소 r로 접근
     • r = p` * pageSize + d
• 문제점
  • 메모리 접근 횟수가 2배 → 성능 저하
    • PMT를 위한 메모리 공간 필요
• 해결방안
  • Associative mapping 사용 → TLB 사용
  • PMT를 위한 전용 기억장치 사용

 

2) Associative mapping

• TLB(Translation Look-aside buffer)에 PMT 적재
  • PMT를 병렬 탐색할 수 있게 됨
• Low overhead, high speed
• Hardware가 비쌈

• 

• → page number p를 사용하여 TLB를 바로 접근 한다. 만약 TLB의 residence bit이 0이라면, swap device에서 정보를 가져온후 PMT를 업데이트 한다.

 

3) Hybrid Direct/Associative Mapping

• 두 기법을 혼합하여 사용
  • PMT : 메모리(커널 공간)에 저장
  • TLB : PMT 중 일부 entry들을 적재(최근에 사용된 page)
• Locality(지역성) 활용
  • Temporal locality : 한번 접근한 영역을 다시 접근 할 가능성이 높다.
  • Spatial locality : 접근한 영역의 인접한 영역을 다시 접근 할 가능성이 높다.

• 

  
  
  1. TLB에 PMT에 적재되어 있는 경우
     • residence bit를 검사하고 page frame 번호를 확인하여 real address 접근
  2. TLB에 PMT에 적재되어 있지 않은 경우
     • Direct mapping으로 page frame 번호 확인
     • 해당 PMT entry를 TLB에 적재하고 1번 반복

※ Memory Management

• Page와 같은 크기로 미리 분할 하여 관리/사용 → Page frame 사용
  • FPM 기법과 유사
• Frame table
  • Page frame당 하나의 engry

  • 

    
    
    • PID : process ID
    • aloocated : 할당 여부를 표시
    • AV : free list의 시작점 → page frame중 첫번째로 사용가능한 것
    • Link : 사용가능한 page frame을 연결

※ Page Sharing and Protection

1) Page sharing

• 여러 프로세스가 특정 Page를 공유 가능 → Non-continuous allocation이기 때문
• 공유 가능 page
  • Procedure page

    • 

      • 서로 다른 PMT가 같은 main memory영역을 공유하지만 서로 실제 주소가 다른 문제가 발생 → k1과 k2 둘 다 PMT에 각각 존재 가능하기 때문

        • 

      • → shared page에 대한 정보는 PMT마다 같은 entry에 저장하도록 해야 함
  • Data page

 

2) Page protection

• Protection bit를 사용하여 권한을 설정해야 함

  • 

2.2 Segmentation system

• 프로그램을 논리적 block으로 분할(segment)
  • Block의 크기가 일정하지 않음
• 특징
  • 메모리를 미리 분할 하지 않음(VPM과 비슷)
  • Sharing 및 protection이 용이 함
  • overhead가 큼
  • No internal fragmentation
    • External fragmentation 발생 가능
• Address mapping
  • Virtual address : v = (s, d)
    • s : segment number
    • d : displacement(offset)
  • SMT(Segment Map Table) 이용

    • 

  • 

    • address mapping 중 direct mapping
    1. 프로세스의 SMT가 저장되어 있는 주소 b에 접근
    2. SMT에서 segment s의 entry 찾음(s의 entry 위치 = b + s * entrySize)
    3. 찾은 Entry에 대해 다음 단계들을 순차적으로 수행
       1. Residence bit가 0인 경우(segment fault)
          • swap device로 부터 해당 segment를 메모리에 적재후 메모리 갱신
       2. 변위(d)가 segment 길이보다 큰 경우(d > Is)
          • segment overflow exception → 처리 모듈 수행
       3. protection bit를 검사했을때 허가되지 않은 연산일 경우
          • segment protection exception → 처리 모듈 수행
    4. 3번 단계에서 이상이 없으면 실제 주소 r을 구하여 접근
       • r = as + d

※ Memory Management

• VPM(Variable Partition Muliti-programming)과 유사

  • 

 

※ Segment Sharing and Protection

• 논리적으로 분할되어 있어서, 공유 및 보호가 용이

2.3 Hybrid paging/segmentation system

• paging과 segmentation의 장점 결합
  • sharing/protection이 쉬움
  • 메모리 할당 및 관리의 overhead가 작음
• 전체 테이블 수 증가로 메모리 소모가 크고 address mapping 과정이 복잡
• 프로그램 분할
  • 논리 단위의 segment로 분할
  • 각 segment를 고정된 크기의 page들로 분할
• 메모리 관리 → FPM과 유사
• page 단위로 메모리에 적재
• Address mapping
  • virtual address : v = (s, p, d)
    • s : segment number
    • p : page number
    • d : offset in a page
  • 각 프로세스 마다 하나의 SMT, 각 segment마다 하나의 PMT를 가짐

  • 

• SMT

  • 

  • Residence bit가 없다
• PMT

  • 

• Address Mapping tables

  • 

• Direct address mapping인 경우

  •