Operating System Ch 10

LeemHyungJun·2022년 11월 19일
0

Operating System

목록 보기
9/20
post-thumbnail

운영체제 수업 + Operating System
Concepts 10E 정리 내용

Operating System Ch10 : Virtual memory

Virtual Memory

1. Overview

  • Physical Memory는 resource의 한계가 존재한다.
  • physical memory가 꽉 차서 못쓰는 상황 -> 디스크에서 frame 사이즈와 같은 크기로 만든 자료구조를 이용
  • physical memory와 디스크의 swap을 통해 공간을 만들어 physical memory크기보다 더 큰 공간을 사용할 수 있게 해준다.

2. Demand Paging

  • logical 영역 : 프로그램이 실행하는데 필요한 영역이 한번에 다 생성된다.
  • demand paging : run time에 disk에 있는 것 중에서 필요한 것만 올리는 방식
    • 필요한 것을 필요할 때에 가져오기
    • 메모리를 아낄 수 있고 효율적이다. (locality를 잘 이용할 수 있다)
  • 순서
    • TLB miss -> page table 보기 -> invalid -> exception -> OS의 개입
      1) page fault : disk에서 필요한 것을 가져와서 실행
      2) protection fault : trap
  • cf) process에서 swap in/out : 전체 프로세스를 모두 올리고 내리는 것을 결정하기
    • long, mid term scheduling이 사라진 이유
  • locality 특성으로 인해 더욱 효율적으로 동작한다.
    • caching이 locality의 특성을 극대화
  • locality in a memory-reference pattern을 보면..
    • 가로축으로 연속된 형태 : temporal locality
    • 세로축으로 연속된 형태 : spatial locality

3. Memory Protection in Paging

  • virtual memory 없는 경우 : page table의 valid bit에 invalid가 체크되어있을때 접근한다면 무조건 protection fault이므로 trap이 발생한다.
  • virtual memory가 있는 경우 : page table의 valid bit가 invalid인 경우 protection fault와 page fault 두 가지 경우가 존재한다.
    • protection fault : trap
    • page fault : 디스크에 접근해서 swap
  • 실행 이후 한 번도 access가 되지 않은 page는 invalid 이다.

4. Page fault

  • page fault 발생 시 처리
    • hardware : 매우 복잡하게 구현
    • OS : 대체로 사용하는 방식 (hardware의 기능/발전 덕분에 계산을 쉽게 할 수 있게 되었다)
  • Steps in Handling a Page Fault

5. Memory Reference

  • Memory reference 종류
    1) TLB hit : 바로 memory 접근 (이전에 한번 써서 caching이 된 경우 - 99% 차지)
    2) TLB miss : page table 참조 -> 원하는 정보를 찾아서 TLB로 업데이트
    3) TLB miss 후 page table에도 정보가 없는 경우 : page fault or protection fault로 처리
  • 순서
    1) CPU가 메모리를 참조할 때 TLB를 먼저 참조
    2) 맨 처음에 TLB를 참조한 순간 page table은 모두 invalid로 체크되어있어 cache miss가 발생 (처음 실행 시 느림)
    3) 실행하다 보면 TLB와 page table이 채워진다. (TLB hitting range가 99%를 넘게 된다)
  • 위의 과정을 통해 실제로 physical memory를 넘어서는 작업을 하더라도 유저 입장에서 느려지는 것을 잘 느끼지 못한다. (cache의 기능)
  • cache hit 증가 : hot cache / cache hit 감소 : cold cache
  • TLB miss 상황
    • page table 자체가 out된 경우
    • 거의 일어나지 않는 상황
      • cache miss가 일어나서 page table을 보려고 하니 page table이 없는 경우
      • swap out 한 것이 page table인 경우
    • OS 처리 : 잘 사용하지 않는다.
    • hardware 처리 : 대체로 사용하는 방식
  • page faults
    • page fault가 발생하면 io가 많아지면 느려질까? -> 아니다.
    • 올라가 있지 않은 영역을 CPU가 찾으러 가는 상황
      • TLB miss
      • page table invalid
    • OS가 처리

6. Copy-on-Write

  • fork() 상황
    • physical memory는 같다. -> physical memory영역을 공유하기
    • 한 프로세스가 업데이트 되어 업데이트 한 page가 있다면 새로운 frame을 받아와서 처리한다.
  • exec() 상황
    • 성능 향상
    • demanding paging으로 필요한 것을 필요할 때 하나씩 올린다.

No free Frame issue

1. Overview

  • physical memory가 꽉 찬 경우 physical memory 중 하나를 골라서 디스크로 swap out 시키기
  • 어떤 physical memory를 swap out 할 것인지를 결정하는 문제

2. Page replacement

  • 어떤 memory를 내릴 것인지 결정해서 내리는 작업
  • OS가 담당
  • 여러 알고리즘 존재
  • 동작 과정

3. Performance of Demand Paging

  • Effective Access Time (EAT)
    • page fault rate : p(0<=p<=1)p(0<= p <= 1)
    • EAT = (1p)(1-p)* memory access +p+p* (page fault overhead + [swap page out] + swap page in + restart overhead)

4. Page replacement Algorithms

  • page replacement의 목적 : 다시 참조되지 않을 법한 것을 내려야 page fault의 비율을 줄일 수 있다.
  • example
    • A 방식 : frame을 작게 할당
    • B 방식 : frame을 크게 할당
    • A의 page fault가 더 많이 발생한다.
      • but 특정 process의 frame 갯수가 5~6개가 되면 이후로 page fault의 수가 비슷하게 유지된다. (locality 특성)
      • 5~6개보다 많이 frame을 할당할 필요가 없다.

Page replacement Algorithms

  • 한 프로그램에서 많이 사용하는 frame을 예측해서 많이 사용되는 것은 유지하고 많이 쓰지 않는 것을 내리는 것이 좋은 방식이다.

1. FIFO

  • 먼저 들어온 frame이 먼저 나가는 방식
  • swap in 하고 가장 오래된 것을 먼저 빼기
  • 효율성 x
  • example
    • frame 수가 많아졌는데 page fault가 더 많아지는 case도 존재한다.
    • 비효율적이다.
    • 도착 시간만을 생각하는 알고리즘은 page replacement의 목적에 부합하지 않는다.

2. Optimal Algorithm

  • 과거를 보고 현재 상태를 예측하는 방식
  • locality 특성을 활용
  • LRU, NRU, LFU

3. LRU Algorithm

  • Least Recently Used (LRU) Algorithm
  • 최근에 가장 사용되지 않은 것을 내리는 방식 -> 거의 optimal 하다
  • time stamp를 통해 특정 시점의 시간 정보르 표시해야 한다.
    • time stamp 찍기 : 참조될 때 마다 참조되는 page에 대해서 time stamp를 찍는 방식
    • 단점
      • 시간 정보를 남기려면 4~8bit 정도의 크기가 필요 (메모리 차지)
      • 매번 참조할 때 마다 시간 정보를 가져와야 하므로 overhead가 크다
    • time stamp 방식 해결 방안
      • stamp를 찍지 말고 stack을 이용해서 오래된 순으로 쌓아두면 정확한 시간 정보를 몰라도 오래된 것이 무엇인지 알 수 있다.
      • stack 방식의 문제점 : 마찬가지로 stack을 OS가 관리해야 하므로 overhead가 크다.
    • stack 방식 해결 방안
      • time stamp의 bit를 1bit로 줄여서 가지고 있으며 대략적으로 시간 정보를 관리
      • 처음에는 0 저장되고 사용되면 1로 저장
      • timer interrupt가 발생하면 모든 bit를 0으로 초기화 해줘야 한다.
      • 간소화된 time stamp 방식의 문제점
        • 특정 주기 안에서 해당 page가 참조된 것인지 아닌지만 확인
        • reference bit가 1인 경우가 다수 존재하면 누가 먼저 들어온 것인지 확인 불가능하다.
    • 간소화된 time stamp 방식 해결 방안
      • LRU clock사용
  • LRU clock
    • 참조가 되면 refernce bit가 0에서 1이 된다.
    • next victim이 가리키는 것을 보면서 1인 경우 (최근에 참조됨) 0으로 바꾸고 해당 bit의 아래 bit를 확인하여 처음으로 0을 발견하면 해당 bit를 victim으로 선정하여 다음에 초기화를 해야 할 때 먼저 초기화시킬 bit를 가리키기
      -> 다음 timer interrupt가 발생 이전에 page fault가 일어나면 먼저 내려야 할 것을 미리 정해두는 작업!
    • NRU 알고리즘보다 성능이 좋지 않아서 사용하지 않는 방식이다.

4. NRU algorithm

  • Not Recently Used (NRU)
  • 정보를 read만 한 것인지 write까지 한 것인지 확인 (modify bit 사용)
  • page table entry에 modified bit를 추가
    • page table에 reference bit와 modify bit 두개가 존재
  • 동작 방식
    • class 0 에서 시작 -> interrupt가 들어옴
    • reference bit 초기화
    • read만 한 경우 reference bit를 1로 설정 -> class 2
    • write 한 경우 modify bit 1로 설정 -> class 3
    • modify bit가 한번 1로 설정되면 다시 0으로 설정되는 경우가 없다.
    • class number가 낮은 것이 먼저 replacement된다.
    • class 1 vs class 2
      • reference bit가 1인 것은 이전 timer interrupt 이후 최근에 한번 참조가 된 것 (modify bit가 1인 것은 언제 참조된건지 알 방법이 없기 때문)
      • class 1이 class 2 보다 먼저 replacement 된다.
  • 특징
    • 구현하기 쉽다. Optimization 쉽다.
    • hardware 제조사에서 결정한 동작 방식
  • PTE
    • reference bit : LRU, NRU
    • modift bit : NRU
    • CPU hardware에 의해서 결정된 모습

5. LFU algorithm

  • Least Frequently Used (LFU)
  • count 횟수가 가장 적은 것을 victim으로 선정하기
  • count 횟수를 저장해야 할 공간이 필요하다 -> overhead
  • overhead는 approximation으로 해결한다. (1 bit로 처리) -> LRU와 같아짐
  • Aging
    • shift register로 구현
    • 한 프로세스가 6개의 page를 사용, 참조되는 page와 참조 되지 않은 page를 남겨두기
    • 한 page당 8bit를 더 사용해야 하는 구조 -> overhead

Allocation of Frames

1. Overview

  • Logical memory : page
  • Physical memory : frame
  • Allocation algorithms : 운영체제 위에서 여러 개의 process가 동작할 때 frame을 골고루 나눠주는 방식
  • Allocation algorithm 종류
    • equal allocation : 동등하게 분배
    • proportional allocation : process 사이즈에 따라 분배
    • priority-based allocation : process의 우선순위에 따라 분배
  • Page replacement
    • Global replacement
      • NRU 알고리즘 page table에서 사용하는 방식
      • 모든 page의 모든 page table을 검색해야 한다.
    • Local replacement
      • 자신의 process 안에서만 생각하는 방식
      • page fault가 일어나야 replacement가 일어날 수 있다.
      • 현재 사용하는 방식

2. Page-Fault Frequency Scheme

  • x축 frame 갯수 / y축 page fault 비율
  • 시스템 전체를 관점으로 했을 때
    • page fault rate가 lower bound 보다 아래에 있으면 frame을 과하게 분배한 경우 -> frame 뺏기
    • page fault rate가 upper bound 보다 위에 있으면 동작하는 것에 비해서 frame이 적다. -> frame 더 주기
  • 이러한 시스템에 process의 우선순위까지 고려하는 방식이 현재 OS의 동작 방식이다.

Thrashing

1. Overview

  • Thrashing : page fault의 비율이 높은 현상 / CPU utilization이 최고점을 가지 못했는데 떨어지는 상황
  • 상황
    • 멀티 프로그래밍 환경에서 process가 많아질수록 CPU utilization이 좋아진다.
    • 특정 순간 이후로 CPU utilization이 떨어진다. -> physical memory가 꽉 찬 상황 -> swap이 많이 필요
    • page replacement (io)를 수행해야 한다.
    • io처리를 하면 CPU는 일을 못하므로 성능이 안 좋아지는 것
  • 현재 시스템의 process의 locality 총 합이 전체 메모리 크기보다 클 때 발생 -> swap이 계속 일어나야 하는 상황
  • 해결 방식 : degree of multiprogramming 수를 줄이기

2. Working-Set Model

  • 성능 측정을 위한 모델
  • delta 시간 동안에 필요한 frame의 갯수
  • delta를 움직이면서 peak가 언제인지 측정
  • working set이 적당한 것을 찾기

Other Considerations

1. Preparing

  • 하드웨어를 볼 때 부분만 보고 돌아오면 arm seak time등으로 overhead가 발생하기 때문에 한번 볼 때 끝까지 다 보고 돌아오는 것

2. Page Size Selection

  • 다양한 size의 page를 사용한다. 아래 네가지를 통해 결정
    1) fragmentation : page가 작을수록 internal fragmentation 감소
    2) page table size : page가 클수록 page entry 갯수가 감소, page table size 감소
    3) io overhead : page가 크면 overhead 감소
    4) locality : 적당한 사이즈 찾기 (trade off 개념)

3. TLB Reach

  • TLB : MMU안에 존재하는 cache 메모리
  • TLB Reach : page hit이 발생 시 실제로 접근 가능한 메모리의 총량, 높을수록 성능이 좋다.
  • TLB Reach = TLB size * page size
  • TLB size를 늘리거나 page size를 늘려야 TLB Reach가 증가한다.

4. Program Considerations (중요)

  • 설정
    • 하나의 row당 4kb의 크기 (한 row가 page table 하나의 크기)
    • page table이 1k만큼 존재
  • 프로그램을 짤 때 바깥 for문이 행, 안쪽 for문이 열로 구성
  • 예시
    • 위의 program
      • j=0일 때 처음 page의 0번째 접근, 두번째 page의 0번째 접근 ...(i가 증가함에 따라 다른 page 접근)
        -> 1024번의 page fault 발생
      • j가 증가함에 따라 page fault가 1024번 발생
      • 총 page fault = 1024 * 1024 -> 성능 안좋다
    • 아래 program
      • i=0일때 안쪽 for문 돌 동안 page 하나로 처리 가능
        -> page fault 한번
      • 총 page fault = 1 * 1024 -> 위의 program보다 성능 좋다.

5. DMA 처리

  • IO Interlock : disk가 메모리에 직접 접근할 때 buffer 관리 방식
  • OS가 DMA 전용의 메모리 buffer를 준다 (IO interlock)
  • OS만 사용하는 방식

0개의 댓글