운영체제(OS) - 8. Memory Management

Backgound

• 모든 프로그램들은 (필요로하는 자료와 함께) 실행하는 동안 main memory에 올라와 프로세스가 되어야함.

• Input queue

  • 디스크에서 main memory로 들어오기를 기다리고 있는 프로세스들의 집합
  • 큐에서 하나의 프로세스를 선택해서, 메모리로 올린 후 실행하고 이 프로세스는 실행하는 동안 메모리에서 자료를 접근함.

• 성능을 향상시키기 위해서는 main memory에 여러개의 프로세스가 올라와있어야함.

• user program의 단계별 처리과정 (Multistep Processing of a User Program)
  

Address Binding

= Binding of Instructions and Data to Memory

• Logical/Virtual Addr. → Physical Addr.
  • mapping 시키는 것
• Compile time
  • 만약 프로세스가 메모리 내에 들어갈 위치를 compile time에 알 수 있으면 compiler는 'absoulute code'를 생성할 수 있다.
  • 그러나 시작 위치가 변경되면 코드는 다시 컴파일해야한다.
• Load time
  • 만약 프로세스가 메모리 내의 어디로 올라오게 될지를 compile time때 알지 못하면 컴파일러는 이진코드를 재배치 가능 코드(relocatable code)로 만들어야한다.
  • Binding은 지연된다.
• Execution time
  • 프로세스가 실행하는 중간에 메모리 내의 한 segment에서 다른 segment로 옯겨질 수 잇을 경우, run time때까지 Binding이 지연된다.
  • address maps에 대한 HW 지원이 필요 (ex. base register, limit register)

Logical vs Physical Address Space

• Logical address : CPU가 생성하는 주소
  • virtual address라고도 함.
• Physical address : 메모리가 취급하게되는 주소(즉, MAR에 주어지는 주소)
• complie time binding & load time binding에서는 logical address = physical address
• execution time binding에서는 logical != physical address
  • 이럴 경우 logical address를 virtual address라고 함.
• Memory-Management Unit (MMU)
  • 프로그램의 실행 중에 virtual addr.을 physical addr.로 mapping(변환) 작업 하는 하드웨어 장치
  • relocation register(=base register) 속에 있는 값은 address가 메모리로 보내질 때 마다 user process에 의해 생성된 모든 주소에 더해진다.
  • 재배치 레지스터를 이용한 동적 재배치
    
    • 재배치 리제스터 값이 14000이고, 프로세스가 346에 접근할 대, 동적으로 재배치되어 주 메모리의 14000+346 = 14346 번지에 접근한다.
  • user program은 physical address를 결코 알수 없고 logical adress만 다룬다.

Dynamic Loading

• 각 routine은 실제 호출되기 전까지는 메모리에 올라오지 않고 재배치 가능한 상태로 디스크에서 대기한다.
  • main program이 메모리에 올라와 실행된다.
  • 이 루틴이 다른 루틴을 호출하게 되면 호출된 루틴이 이미 메모리에 load되어 있는지 조사한다.
  • 만약 load되어 있지 않다면 relocatable linkin loader가 불러져 요구된 루틴을 메모리로 가져오고 변화를 테이블에 기록해 둔다.
  • 그후 CPU control은 중단되었던 루틴으로 보내진다.
• 장점 : 사용하지 않는 루틴들이 미리 로드되지 않는다 → 더 나은 메모리 공간 활용

Dynamic Linking

메모리의 공간이 한정적이기 때문에 프로세스가 사용 중이던 메모리 공간을 하드디스크로 내려보냄

• linking이 execution time까지 연기됨
• 주로 시스템 library에 사용된다
  • 만약 이 방식이 없었다면 모든 시스템 라이브러리를 부르는 프로그램들은 그들의 이진 프로그램 이미지 내에 시스템 라이브러리 루틴들을 한 부씩 가지고 있어야 하므로 장치의 낭비가 심해진다.
• 라이브러리를 부르는 곳 마다 Stub이 생긴다.
  • Stub : 라이브러리를 어떻게 찾을 것인가를 알려주는 작은 코드 조각
• Stub이 실행될 때, 필요한 라이브러리 루틴이 이미 메모리에 존재하는 가 검사하고 없으면 디스크에서 가져온다.
• Stub은 라이브러리 루틴의 번지수를 알아내고 자신을 그 루틴의 번지로 대체한다 → 다음번에 그 부분이 불리면 동적연결을 할 필요 없이 직접 그곳의 라이브러리 루틴을 수행하게 된다.
• 라이브러리 루틴을 바꿀 때 특히 유용!

Swapping

메모리의 공간이 부족하기 때문에 temporarily하게 프로세스는 실행 도중에 보조 메모리로 보내졌다가 다시 메모리로 되돌아 올 수 있다.

• Backing Store
  • 모든 사용자가 사용할 수 있는 모든 memory image의 복사본을 저장할 수 있는 충분한 크기의 빠른 Disk. 직접 access할 수 있어야 함.
• Roll out, Roll in
  • 우선 순위 기반 scheduling algorithm에 사용되는 swapping 변형.
  • 더 높은 우선순위의 프로세스가 도착하면 memory 관리기는 우선 순위가 낮은 프로세스를 디스크로 스왑시켜 내보낸다.
  • 높은 우선순위의 프로세스가 끝나면, 낮은 우선 순위 프로세스는 다시 메모리로 스왑되어 계속 실행된다.
• swap time은 transfer time과 비례(proportional)

Contiguous Allocation

메모리는 다음의 두 파트로 나누어져있다.

• Resident operating system

  • 메모리에 상주하는 운영체제를 위한 것

• User processes를 위한 것

• single-partition allocation
  

• Multiple-partition allocation

  • Hole : 사용 가능한 메모리 블록
    다양한 크기의 hole들이 메모리 전체에 흩어져있다.
  • process가 도착하면, 이를 수용할 수 있을 만큼의 큰 hole이 메모리에 할당된다.
  • 운영체제는 1) 할당된 partition, 2) 사용가능한 partitions(Hole)에 대한 정보를 유지한다
    

Contiguous Allocation

연속적 메모리 할당

• main memory는 다음의 두 부분으로 나뉜다
  • memory에 상주하는 OS를 위한 곳
    • 보통 interrupt vector가 낮은 메모리에 보관
  • User process를 위한 곳
    • 보통 interrupt vector가 높은 메모리에 보관
• single-partition allocation
  
• • reallocation-register scheme은 사용자 프로세스를 서로 보호하고 운영체제 code 및 data를 변경하는 것을 방지하는데 사용됨
  • Relocation(base) register는 시작 physical address 중 가장 작은 값을 포함한다.
  • limit register는 logical addresses 범위를 포함함.
  • 각 logical addresses는 limit register보다 작아야함

physical address가 만들어진 이후의 그림

• Multiple-partition allocation
  • Hole
    • 사용 가능한 memory block
    • 다양한 크기의 hole이 메모리 전체에 흩어져있음.
  • 프로세스가 도착하면 수용가능할 만큼 큰 hole에서 memory가 할당됨.
  • OS는 a) free partitions (hole) b) input queue (기다리고 있는 프로세스)에 대한 정보를 유지해야한다.
    

Dynamic Storage-Allocation Problem

free hole list에서 크기 n의 요청을 충족하는 방법

• First-fit : 충분히 큰 첫번째 hole 할당
• Best-fit : 충분히 큰 가장 작은 hole 할당. 크기별로 정렬하지 않으면 전체 목록을 검색해야한다. 남는 hole이 가장 적다.
• Worts-fit : 가장 큰 hole 할당. 전체 list 검색해야 함. 남는 공간이 충분이 커서 다른 process를 위해 사용될 수 있다.

First-fit과 Best-fit이 Worst-fit보다 속도 및 storage 활용 측면에서 더 적합하다.

Fragmentation 단편화

• External Fragmentation
  • 프로세스들이 메모리에 load되고 제거되는 일이 반복되다보면 어떤 free partition은 너무 작은 조각이 되어비린다.
  • 유휴 공간들을 모두 합치면 충분한 공간이 되지만 그것들이 너무 작은 공간들로 여러 곳에 분산되어 있는 것. 최악의 경우 모든 프로세스 사이마다 못쓰게 된 free 공간이 존재할 수 있다.
• Internal Fragmentation
  • 할당된 메모리가 요청된 메모리보다 약간 클때, 이 크기 차이는 partition 내부의 메모리지만 사용되지 않는다.
• Compaction(압축)으로 external fragmentation 감소시킬 수 있음.
  • 메모리의 모든 내용을 한군데로 몰고 모든 자유공간들을 다른 한 군데로 몰아서 큰 블록을 만드는 것.
  • Compaction은 relocation이 dynamic하고, execution time에 수행되는 경우에만 가능
  • I/O 문제
    • 작업이 I/O에 관여하는 동안 메모리에서 compaction 될 경우
    • 해결 : OS buffer로만 I/O 수행

external Fragmentation을 한 프로세스의 주소공간을 여러개의 동떨어진 공간으로 배정하는 방법으로 해결할 수 있음. 1) Paging, 2) Segmentation

Paging

프로세스의 logical address space는 noncontiguous일 수 있다.

• physical memory를 frame이라고 하는 고정된 크기의 블록으로 나뉘어져있다.

• logical memory는 page라고 하는 동일한 크기의 블록으로 나누어진다.

• 모든 free frame은 축적함

• n page 크기의 프로그램을 실행하려면, n개의 빈 frame을 찾고 프로그램을 load해야 한다,

• logical addr.을 physical addr.로 변환하기 위한 page table 설정
  모든 프로세스에는 자체 page table(주 메모리에서 각 페이지가 점유하는 주소를 가지고 있다)이 있다.

• Internal fragmentation은 존재하게 된다.

• Paging Hardware
  - paging number(p) : page table을 access할 때 사용됨.
  - paging offset(d) : 기본 주소와 결합하여 메모리로 전송되는 physical memory address를 정의한다.
  

• logical 및 physical memory의 paging model
  

• 4바이트 페이지를 가진 32바이트 메모리의 페이징 예시
  

• free frame
  

페이징 테이블 구현

• 페이지 테이블은 메인 메모리에 있어야 한다.

• page-table base register (PTBR)가 페이지 테이블을 가리킴

• page-table length register (PRLR)는 페이지 테이블의 크기를 나타냄

• 이 scheme에선 모든 데이터 / instruction access에는 두 개의 메모리 액세스가 필요하다.

  • 1) page table용
    2) memory 자체 용(data/instruction 용)

• 해결: associative
  memory 또는 TLB (translation look-aside buffer)라고하는 특수 고속 조회 하드웨어 캐시를 사용하여 해결 가능

• Associative Memory : 병렬 검색
  
  - A´가 Associative register에 있으면 프레임# 을 내보낸다
  - 그렇지 않으면 메모리의 페이지 테이블에서 from# 을 가져온다.

-TLB를 이용한 paging Hardware

CPU에 의해 logical address가 생성되면 그 page number를 TLB에 제시한다. 만일 찾으면 그 frame 번호는 바로 알수 잇으며 메모리 접근하는데 사용할 수 있다. 이 모든 작업은 페이지 번호를 찾지 못하는 경우 10%미만의 시간이 소모된다.

Effective Access Time

• Associative Lookup = ε time unit
• 메모리주기 시간이 1 마이크로 초라고 가정
• Hit ratio – 연관 레지스터에서 페이지 번호가 발견 된 횟수의 백분율. 연관 레지스터 수와 관련된 비율
• Hit ratio = α
• Effective Access Time (EAT)
  • EAT = (1 + ε) α + (2 + ε) (1 – α) = 2 + ε – α ➠ 1 // ε이 작고 α가 큰 경우 1 (≅ 1)

Memory Protection

• 페이지 테이블의 각 항목에는 vaild-invalid 라는 하나의 비트가 더있다.
• "valid"는 연관된 페이지가 프로세스의 논리적 주소 공간에 있으므로 합법적 인 페이지임을 나타낸다.
• “invalid”은 페이지가 프로세스의 논리적 주소 공간에 없음을 나타낸다
  

Page Table Structure

페이징 테이블을 구성하는 일반적인 3가지 방식

Hierarchical Paging

logical address space를 여러개의 page table로 분할

Two Level Page Table

page table 자체가 paging 되는 것을 말한다.

• 4KB page size를 가진 32-bit 기계의 logical address
  • 20bit page number → 1million entries in table
  • 12bit page offset (4K word in page)
    
  • P1: outer page table index, P2 : outer page table 내의 offset

• two level 32bit paging architecture에서의 address-translation
  

Hashed Page Table

• address space > 32bit 이면 논리 주소를 hash로 사용하는 hashed page table을 사용함.
  -Hash형 page table의 각 항목은 연결리스트를 가지고 있다. 이 list에는 collision을 일으켜서 해쉬되는 원소들이 연결되어 있다.

• 장점: Hashed Page Table을 만들고 hash function으로 access 횟수를 많이 줄일 수 있다.

• 3가지 필드
  1) virtual(=logical) page number
  2) 사상되는 page frame number
  3) linked list 상의 다음 원소 pointer

1. logical address space으로부터 page number가 오면 이를 hashing한다.
2. Hashed page table에서 연결 리스트를 따라가며 첫번째 원소와 page 번호를 비교한다.
3. 일치하면 그에 해당하는 page frame 번호(두번째 필드)를 가져와 physical address를 얻는다. 일치하지 않으면 다음 원소로 비교(2번이랑 같은)

---

사실 process 하나당 page table이 존재하기에 이런 문제들이 발생했던 것. 그럼 이 frame은 어떤 프로세스의 몇 번 page인지 역으로 접근!! : Inverted page table

Inverted Page Tables

각각의 프로세스마다 페이지 테이블이 만들어지기 때문에 실제로는 다른 프로세스에서 해당 메모리에 접근하고 있음에도 불구하고 page table entry에 데이터를 가지고 있어야 하는 경우가 있다. → 단점 : page table의 크기

• 해결 : inverted page table 사용
  
• • 시스템에 page table이 한개만 존재한다.
  • 각 physical memory에 하나의 page를 가진다.
  • 장점 : logical page마다 각 page table를 가지는 대신 physical frame에 대응하는 항목만 table에 저장되기 때문 사용되는 memory가 감소!
  • 주소 공간 ID가 필요하다. 이 ASID는 logical address가 상응하는 physical address에 대응되는 것을 보장한다.
    • 단점: search시간 오래 걸림. → Hash를 이용하여 시간을 감소시키면 됨.
  • logical address : <process-id, page-number, offset>으로 구성
  • inverted page table 항목은 <process-id, page-number>로 구성 → process id = 주소 공간 id

Shared Pages

• Shared code
  • process 간에 공유되는 read-only(reentrant) code
  • 모든 proces의 logical address space 간에서 동일한 위치에 있어야 함
  • non-self-modifying code이므로 실행 중에 변하지 않는다
  • 따라서 2개 이상의 프로세스가 같은 코드에서 동시에 실행된다.
• Private code and data
  • 각 process는 code와 data를 private하게 보관
  • private code & data에 대한 page는 logical address space의 어느 위치에나 있을 수 잇음
    

Segmentation

메모리의 user view를 그대로 지원하는 memory-management 기법

• logical address space = segments의 집합
  

• Logical address : <segement-number, offset>으로 구성

• Segment table

  • base : segment 시작 주소
  • limit : segment 길이

• Segment-table base register (STBR)에 segment table의 위치 point

• Segment-table length register (STLR)은 program에 사용하는 segment의 개수 나타냄

  s < STLR일 때, Segment number s 유효
  

• Relocation

  • dynamic
  • segment table에 의해 (base값 바꿈)

• Sharing

  • shared segments
  • same segment number

• Allocation

  • first fit or best fit
  • external fragmentation은 존재함

• Protection : segment table에 bit 추가로 구현

  • validation bit = 0 -> 잘못된 segment
  • read/write/execute privileges(권한)
  • code sharing도 segment 단위로
  • dynamic storage-allocation problem이 발생 (segments 길이가 다양하기 때문)
    
  • segment sharing
    

Segmentation with Paging - MULTICS

• segment를 paging하여 external fragmentation 및 long search time 문제 해결