Logical address(=virtual address)

• 프로세스마다 독립적으로 가지는 주소 공간
• 각 프로세스마다 0번지부터 시작
• CPU가 보는 주소

Physical address(물리적 주소)

• 메모리에 실제 올라가는 위치

Address Binding(주소 바인딩)

주소를 결정하는 것

• Compile time binding
  • 물리적 메모리 주소가 컴파일 시 알려짐
  • 시작 위치 변경시 재컴파일
  • 컴파일러는 절대 코드(absolute code) 생성
• Load time binding
  • Loader의 책임하에 물리적 메모리 주소 부여
  • 컴파일러가 재배치가능코드(relocatable code)를 생성한 경우 가능
• Execution time binding(=Run time binding)
  • 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮긿 수 있음
  • CPU가 주소를 참조할 때마다 binding을 점검(address mapping table)
  • 하드웨어적인 지원이 필요

Symbolic Address ${\rightarrow}$ Logical Address ${\rightarrow}$ Physical address

Dynamic Loading

• 프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 load하는 것
• Memory utilization의 향상
• 가끔씩 사용되는 많은 양의 코드의 경우 유용
  • ex) 오류 처리 루틴
• 운영체제의 특별한 지원 없이 프로그램 자체에서 구현 가능(OS는 라이브러리를 통해 지원 가능)

Overlays

• 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올림
• 프로세스의 크기가 메모리보다 클 때 유용
• 운영체제의 지원없이 사용자에 의해 구현
• 작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현

Swapping

• 프로세스를 일시적으로 메모리에서 backing store로 쫓아내는 것

Backing store(=swap area)

• 디스크
  • 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간

Dynamic Linking

• Linking을 실행 시간(execution time)까지 미루는 기법
• Static linking(${\leftarrow}$ static library)
  • 라이브러리가 프로그램의 실행 파일 코드에 포함됨
  • 실행 파일의 크기가 커짐
  • 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비
• Dynamic linking(${\leftarrow}$ shared library)
  • ex) .so(linux) .dll(windows)
  • 라이브러리가 실행시 연결(link)됨
  • 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둠
  • 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어옴
  • 운영체제의 도움 필요

Allocation of Physical Memory

메모리는 일반적으로 두 영역으로 나뉘어 사용

• OS 상주 영역
  • interrupt vector와 함께 낮은 주소 영역 사용
• 사용자 프로세스 영역
  • 높은 주소 영역 사용

사용자 프로세스 영역 할당 방법

• Contiguous allocation: 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것
  • Fixed partition allocation
  • Variable partition allocation
• Noncontiguous allocation: 하나의 프로세스가 여러 영역에 분산되어 올라갈 수 있음
  • Paging
  • Segmentation
  • Paged Segmentation

Contiguous Allocation

• 고정분할(Fixed partition) 방식
  • 물리적 메모리를 몇 개의 영구적 분할(partition)로 나눔
  • 분할의 크기가 모두 동일한 방식과 서로 다른 방식이 존재
  • 분할당 하나의 프로그램 적재
  • 융퉁성이 없음
    • 동시에 메모리에 load되는 프로그램의 수가 고정됨
    • 최대 수행 가능 프로그램 크기 제한
    • Internal fragmentation 발생 (external fragmentation도 발생)
• 가변분할(Variable partition) 방식
  • 프로그램의 크기를 고려해서 할당
  • 분할의 크기, 개수가 동적으로 변함
  • 기술적 관리 기법 필요
  • External fragmentation 발생

• External fragmentation(외부 조각)
  • 프로그램 크기보다 분할의 크기가 작은 경우
  • 아무 프로그램에도 배정되지 않은 빈 곳인데도 프로그램이 올라갈 수 없는 작은 분할
• Internal fragmentation(내부 조각)
  • 프로그램 크기보다 분할의 크기가 큰 경우
  • 하나의 분할 내부에서 발생하는 사용되지 않은 메모리 조각
  • 특정 프로그램에 배정되었지만 사용되지 않는 공간

Noncontiguous Allocation

• 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로 변환
• Internal fagmentation만 발생 가능

• Segmentation
  • 작게는 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의
  • 크게는 프로그램 전체를 하나의 세그먼트로 정의 가능
  • 일반적으로는 code, data, stack 부분이 하나씩의 세그먼트로 정의됨
  • segment는 의미 단위이기 때문에 공유(sharing)와 보안(protection)에 있어 paging보다 훨씬 효과적
  • Segment의 길이가 동일하지 않으므로 가변분할 방식에서와 동일한 문제점들 발생
    • ex) External fagmentation

Segment의 logical unit 종류
main(), function, global variables, stack, symbol table, arrays

• Paged Segmentation

Implementation of Page Table

• Page table은 main memory에 상주
• Page-table base register(PTBR)가 page table을 가리킴
• Page-table length register(PTLR)가 테이블 크기를 보관
• 모든 메모리 접근 연산에는 page table 접근 1번, 실제 data/instruction 접근 1번의 총 2번의 memory access 필요
• 속도 향상을 위해 associative register 혹은 translation look-aside buffer(TLB)라 불리는 고속의 lookup hardware cache 사용

Demand Paging

• 실제로 필요할 때 page를 메모리에 올리는 것
  • I/O 양의 감소
  • Memory 사용량 감소
  • 빠른 응답 시간
  • 더 많은 사용자 수용
• Valid / Invalid bit의 사용
  • Invalid의 의미
    • 사용되지 않는 주소 영역인 경우
    • 페이지가 물리적 메모리에 없는 경우
  • 처음에는 모든 page entry가 invalid로 초기화
  • address translation 시 invalid bit이 set되어 있으면 ${\Rightarrow}$ "page fault"

Page Fault

• Invalid page를 접근하면 MMU(Memory Management Unit)가 trap을 발생시킴(page fault trap)
• Kernel mode로 들어가서 page fault handler가 invoke됨

Page fault 처리 순서
1. Invalid reference ${\Rightarrow}$ abort process
2. Empty page. frame을 가져오고 없으면 뺐어온다(replace).
3. 해당 page를 disk에서 memory로 읽어옴

• Disk I/O가 끝나기까지 이 프로세스는 CPU를 preempt 당함(block)
• Disk read가 끝나면 page tables entry 기록, valid/invalid bit = "valid"
• Ready queue에 process를 insert ${\rightarrow}$ dispatch later

4. 이 프로세스가 CPU를 잡고 다시 running
5. 아까 중단되었던 instruction 재개

Page Replacement 방법

• Optimal Algorithm
  • 가장 먼 미래에 참조되는 page를 replace
  • 미래의 참조를 아는 Offline algorithm으로 다른 알고리즘의 성능에 대한 upper bound 제공
  • Belady's optimal algorithm, MIN, OPT 등으로 불림
• FIFO(First In First Out) Algorithm
  • 먼저 들어온 것을 먼저 내쫓음
  • FIFO Anomaly(Belady's Anomaly) 발생 가능
    • page frame이 늘어났음에도 page fault가 발생하는 경우
• LRU(Least Recently Used) Algorithm
  • 가장 오래 전에 참조된 것을 지움
  • ${\mathcal{O}}(1)$ complexity(Linked list)
• LFU(Least Frequently Used) Algorithm
  • 참조 횟수(reference count)가 가장 적은 페이지를 지움
  • ${\mathcal{O}}({\log n})$ complexity(Heap)

Clock Algorithm

LRU의 근사(approximation) 알고리즘

• Paging은 하드웨어의 도움만을 받고, page falut가 발생할 때에만 운영체제의 도움을 받기 때문에 LRU, LFU 방법을 사용할 수 없어 LRU의 근사 알고리즘을 사용
• 하드웨어의 도움을 받는 Reference bit을 사용하여 교체 대상 페이지 선정(circular list)
  • Reference bit가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동
  • 포인터를 이동하는 중에 reference bit 1은 모두 0으로 변경
  • Reference bit이 0인 것을 찾으면 그 page를 교체
  • 한 바퀴 되돌아와서도(=second chance) 0이면 그때에는 replace 당함
  • 자주 사용되는 페이지라면 second chance가 올 때 1로 되어있음
• Second chance algorithm, NUR(Not Used Recently), NRU(Not Recently Used)로도 불림
• 성능을 개선하기 위해 modified bit(dirty bit)을 함께 사용
  • 메모리에 올라온 page가 한번이라도 수정됬으면(modified bit = 1) disk로 내쫓을 때 수정된 값으로 변경해주고 수정되지 않았으면 그냥 삭제하면 됨

Thrashing

• 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당 받지 못한 경우 발생
• Page fault rate이 매우 높아짐
• CPU utilization이 낮아짐
• Low throughput
• OS는 MPD(Multiprogramming degree)를 높여야 한다고 판단해 또 다른 프로세스가 시스템에 추가되어(higher MPD) 프로세스 당 할당된 frame 수가 더욱 감소
• 프로세스는 page의 swap in/swap out으로 매우 바쁘지만 대부분의 시간에 CPU는 한가함
• 해결법으로 Working-Set Model과 PFF가 존재

Working-Set Model, PFF(Page-Fault Frequency)

• Working-Set Model
  • 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조하는 Locality of reference를 활용(집중적으로 참조되는 해당 page들의 집합을 locality set이라 함)
  • Locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page들의 집합을 Working Set이라 함
  • Process의 working set 전체게 메모리에 올라와 있어야 수행되고 그렇지 않을 경우 모든 frame을 반납한 후 swap out(suspend)
  • Working set의 결정은 window size만큼의 Working set window를 통해 알아냄
  • Multiprogramming degree를 결정
• PFF
  • Page-fault rate의 상한값과 하한값을 둠
    • Page fault rate이 상한값을 넘으면 frame을 더 할당
    • Page falut rate이 하한값 이하이면 할당 frame 수를 줄임
  • 빈 frame이 없으면 일부 프로세스를 swap out

---

Reference

KOCW - 운영체제 이화여대 반효경 교수님