메모리 관리 2 & 3

반효경 교수님 - 운영체제 2017 강의를 참고하여 작성하였습니다.

Paging

• Process의 virtual memory를 동일한 사이즈의 page 단위로 나눔
• virtual memory의 내용이 page 단위로 noncontiguous하게 저장됨
• 일부는 backing storage에, 일부는 physical memory에 저장

Basic Method

• Physical memory를 동일한 크기의 frame으로 나눔

• logical memory를 동일 크기의 page로 나눔 (frame과 같은 크기)

• 모든 가용 frame들을 관리

• page table을 사용하여 logical address를 physical address로 변환

• External fragmentation 발생 안함

• Internal fragmentation 발생 가능

• Page 크기는 기본적으로 4KB, 현대에는 조금 더 큼

• 주소는 편의상 32bit 주소체계를 사용한다.

• 32비트 주소체계를 사용하면, 한 프로세스가 최대 4GB

page table

• logical meory와 physical memory의 위치(주소)를 변환하기위한 자료구조

• Page table은 main memory에 상주

• Page-table base register(PTBR)가 page table을 가리킴 (시작위치)

• Page-tavle length register(PTLR)가 테이블 크기를 보관

• 모든 메모리 접근 연산에는 2번의 memory access가 필요하다

• Page table에 접근 한번, 실제 data/instruction에 접근 한번

• 속도 향상을 위해서 associative register 혹은 translation look-aside buffer(TLB)라 불리는 고속의 lookup hardware cache 사용(일부 정보만 담고 있음)

  • TLB는 일부 정보만 담고 있기때문에, page number와 frame number를 가지고 있어야만 한다.

  • Page number를 가지고 있는지 전부 확인해야하기때문에 오버헤드가 발생한다. 그래서 병렬적으로 서칭할 수 있도록 associative register를 필요로 한다.

Associative registers(TLB)

• parallel search가 가능하다.
• Address translation
  • page table 중 일부가 associative register에 보관되어 있음
  • 만약 해당 page #가 TLB에 있는 경우(TLB hit) 바로 frame #을 얻음
  • 그렇지 않은 경우(TLB miss) main memroy에 있는 page table로 부터 frame #을 얻음
  • TLB는 context switch 때 flush(remove old entries)

Two-Level Page Table

• 현대 컴퓨터는 address space가 매우 큰 프로그램을 지원한다.
  • 32 bit address 사용시 2^32 (4G)의 주소 공간
    • page size가 4K시 1M개의 page table entry 필요
    • 각 page entry가 4B시 프로세스당 4M의 page table 필요
    • 그러나, 대부분의 프로그램은 4G의 주소 공간 중 지극히 일부분만 사용하므로 page table 공간이 심하게 낭비됨
• 접근하는 횟수는 늘어나지만, 메모리 공간을 줄여줌
• 실제 사용되는 페이지가 적어도 table entry는 모두 만들어줘야 하기때문에 공간 낭비가 심함
  

• logical address의 구성
  • 20bit의 page number
  • 12bit의 page offset
• Page table 자체가 page로 구성되기 때문에 page number는 다음과 같이 나뉜다
  • 10bit의 page number
  • 10bit의 page offset
• p1 = 10, p2 = 10, d = 20
• p1은 outer page table의 index, p2 outer page table의 page에서의 변위
  

Multilevel Paging and Performance

• Address space가 더 커지면 다단계 페이지 테이블이 필요하다.
  • 각 단게의 페이지 테이블이 메모리에 존재하므로 logical addressdml Physcial address 변환에 더 많은 메모리 접근이 필요하다
  • -> TLB를 통해서 메모리 접근 시간을 줄일 수 있다. (상당수의 page가 cached 되기 때문에 TLB hit ratio가 높아짐)

Valid/ Invalid Bit in a Page table

• Valid 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음을 뜻함
• Invalid 해당 주소의 frame에 유효한 내용이 없음을 의미
  • 프로세스가 그 주소 부분을 사용하지 않는 경우
  • 해당 페이지가 메모리에 올라와 있지 않고 swap area에 있는 경우
    

• Protection bit
  • page에 대한 접근 권한(read/write/read-only)

• 물리적인 주소로 논리적인 주소를 찾는 방식(Page table을 하나만 가지고 있는 점은 장점이다.)
• 하지만 논리적 주소로 물리적 주소를 찾아야하는 것이 주소변환의 목적이기 때문에 page table을 모두 찾아봐야한다는 오버헤드가 발생한다.
• -> associative register를 사용한다면 해결 가능

Shared Page

• Shared code
  • Re-entrant Code(=Pure code)
  • Read-only로 하여 프로세스 간에 하나의 code만 메모리에 올림
    • Ex) text editors, compilers, window systems
  • Shared code는 모든 프로세스의 logical address space에서 동일한 위치에 있어야 함
• Private code and data
  • 각 프로세스들은 독자적으로 메모리에 올림
  • private data는 logical address space의 아무 곳에 와도 무방
    

Segmentation

• 프로그램은 의미 단위인 여러 개의 segment로 구성
  • 작게는 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의
  • 크게는 프로그램 전체를 하나의 세그먼트로 정의 가능
  • 일반적으로 code, data, stack 부분이 하나씩의 세그먼트로 정의됨
• segment는 logical unit
  • Main()
  • function
  • global variables
  • stack
  • symbol table
  • arrays
    

Architecture

• 논리적 주소는 segment-number, offset으로 이루어짐
• Segment table
  • Base - 세그먼트의 시작 물리적 주소
  • limit - 세그먼트의 길이
• Segment table base register (STBR)
  • 물리적 메모리에서의 segment table 위치
• Segment table length register (STLR)
  • 프로그램이 사용하는 segment의 수

• paging과는 다르게 segment의 길이,크기가 각각 다르기때문에 limit이 필요하다.

• proctection

  • 각 세그먼트로 별로 protection bit가 있다.

• Sharing

  • shared segment
  • same segment number
    • segment는 의미 단위이기 때문에 공유와 보안에 있어서 paging보다 훨씬 효과적이다.
    • page에서는 고정 크기이기 때문에 protection 설정이 어렵다.

• Allocation

  • first fit / best fit
  • external fragmentaion 발생 -> 가변분할 방식에서와 동일한 문제점이 발생한다.

Segmentation With Paging

• pure segmentation과의 차이점
  • Segment table entryr가 segment의 base address를 가지고 있는 것이 아니라 segment를 구성하는 page table의 base address를 가지고 있음
    
• segmentaition의 문제점을 해결하고 실질적으로 사용하기 위함