[OS] 11. 가상메모리 - (2)

[이화여자대학교 반효경 교수님의 강의를 듣고 정리한 글입니다.]

운영체제

운영체제 운영체제는 컴퓨터 하드웨어 바로 위에 설치되는 소프트웨어 계층으로서 모든 컴퓨터 시스템의 필수적인 부분이다. 본 강좌에서는 이와 같은 운영체제의 개념과 역할, 운영체제를 구성하는 각 www.kocw.net

운영체제

---

[그림과 함께 편하게 보려면 여기로]

https://adorable-aspen-d23.notion.site/OS-11-2-851c3d22a0fb4543b4b9ad0a9bd84980

[OS] 11. 가상메모리 - (2)

1. 가상메모리 등장 배경

• 물리 메모리
  • 앞서 배운 물리메모리에 프로세스를 올리는 것은 항상 ‘프로세스 전체'가 메모리에 올라와야 했다.
  • But, 물리 메모리가 아무리 커도 딱 그만큼만 올릴 수 있음
  • 프로그램은 보통 방어적으로 작성된다. (예외 코드 쏘매니) → 굳이 다 올릴 필요가 있을까?
  • 주소 변환에 하드웨어 장치가 사용될 뿐, 운영체제는 전혀 관여하지 않는다.
• 가상 메모리
  • ‘프로세스 전체'를 메모리에 올리지 않고 필요한 부분만 올려서 실행하자!
  • (프로세스를 자른다. → 필요한 부분만 페이지 테이블에 올린다. → 테이블에 올라온 페이지만 물리 메모리에 매핑한다.)
  • 주소 변환에 전적으로 운영체제가 관여한다.

2. Demand Paging

• CPU 요청이 있는 프로세스에 대해 해당 페이지를 물리적 메모리에 적재한다.
  • Page Fault
    • CPU가 요청한 페이지가 물리적 메모리에 올라와 있지 않은 경우
    • 해당하는 페이지를 디스크에서 찾아 물리적 메모리에 올려야 한다.
      • 물리적 메모리에 빈 frame이 없는 경우 → Page 교체
• 프로세스를 잘라서, 필요한 페이지만 가상 메모리에 적재
• 장점
  • 메모리 효율을 높인다.
  • 프로그램이 메모리 크기 제약을 받지 않음
  • I/O 양의 감소
    • 필요한 페이지만 올리기 때문에
    • 멀티 프로그래밍 환경에서 좋다.
  • 빠른 응답시간
  • 다만 빠른 응답 시간에 대해서는 이견이 있을 수 있다. 한 번에 모든 페이지를 올리게 되면 디스크에 I/O를 할 일이 없으니 Demand Paging이 더 느릴 수도 있다는 것이다. 그러나 한정된 메모리 공간에 더 많은 사용자 프로세스를 로드하여 동시에 실행된다면 한 번에 모든 페이지를 로드하는 것보다 **Demand Paging을 사용하는 편이 응답 시간의 측면에서도 더 낫다** 는 것이다.
  • 더 많은 사용자 수용

1. Valid/Invalid bit

• Valid
  • 페이지가 물리적 메모리에 올라와 있음
• Invalid
  • 페이지가 물리적 메모리에 올라와 있지 않음
  • 사용되지 않는 주소 영역
    • Page table은 무조건 주소 공간의 크기만큼 생성되기 때문에 사용되지 않는 주소 공간 존재

2. 요구 페이징 작동 로직

• CPU가 페이지 요청, Page Fault가 일어난 경우
  1. Page table의 해당 페이지가 invalid bit
  2. MMU가 Trap을 발생시킴운영체제 : 잘못된 요청인지 확인(없는 주소 , protection violation 등) → abort
  3. → Trap이 걸려서 CPU가 운영체제로 넘어감
  4. 정상적인 메모리 요청 → 운영체제가 물리적 메모리에서 빈 프레임 얻기
     1. 빈 페이지가 없다면 → 강제로 하나 뺏어서 페이지 교체 (Page Replacement)
  5. 해당 페이지를 디스크에서 메모리로 읽어온다.
     • Disk I/O가 끝날 때까지 CPU반납 (Blocked)
  6. Disk Read가 끝나면 Page table entry 기록한다.
     • Valid/Invalid bit에 “valid” 기록
  7. 해당 프로세스를 ready queue에 삽입한다.
     • 이후 다시 CPU를 잡아 Run할 때, page fault가 일어나지 않고 정상적으로 MMU를 통한 주소 변환이 가능해진다.

3. Page Fault 비율

• Effective Access Time = (1-p) * 메모리 접근 시간 + p * 엄청난 시간
  • 대부분의 경우는 page fault가 일어나지 않고, (0.9)
  • 0.1의 경우에 page fault가 나서 디스크 I/O접근 작업을 해야함
    • 이건 엄청난 오버헤드
    • 운영체제가 CPU받아서 디스크 접근, 접근해서 읽어오고, valid비트도 조절하고 등등..

3. Page Replacement

• Page Fault가 일어나서 운영체제가 물리적 메모리에 새로 올리려고 하는데, 아뿔싸 메모리에 공간이 없다!
  • 어떤 페이지를 쫓아내면 칭찬을 받을까?
  • Page Fault rate이 낮은 페이지를 쫓아내자!

1. Optimal Algorithm

• 가장 먼 미래에 참조되는 페이지를 replace
  • 미리 어떤 페이지가 참조될지를 다 알고 있다는 가정(사실상 불가하긴함)
• 가장 최적의 알고리즘
  • 어떤 알고리즘을 쓰더라도 이것보다 더 적은 page fault가 있을 수는 없음 (얘가 와따)
  • 다른 알고리즘 성능에 대한 upper bound제공
  • Belady’s optimal algorithm, MIN, OPT 등으로 불림

2. FIFO

• 먼저 들어온 것을 먼저 내쫓음
• FIFO Anomaly (이상)
  • page frame을 늘려주면 보통 성능이 좋아져야 하지만, 오히려 성능이 나빠지는 현상 (page fault 증가)

3. LRU(Least Recently Used)

• 가장 오래전에 참조된 것을 먼저 내쫓음
• 구현
  • LinkedList 형태로 구현해서 O(1) 시간에 구현
  • 참조되면 맨뒤에 append

4. LFU(Least Frequently Used)

• 가장 적게 참조된 것을 먼저 내쫓음
  • 최저 참조 횟수인 page가 여러개라면 ? → 임의로 선정 (별다른 알고리즘은 없음)
• 장점
  • LRU처럼 직전 참조 시점만 보는 것이 아니라, 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영 가능
• 단점
  • 참조 시점의 최근성을 반영하지 못함
  • LRU보다 구현이 복잡
• 구현
  • heap을 사용해서 O(logn) 시간에 구현
    • 트리로 자료 구성, 자식이랑만 크기 비교, swap
    • LinkedList를 이용해서 구현하면, 최악의 경우 O(n)이 걸리기 때문
• 
• MFU (Most frequently used)
  • 가장 참조 횟수가 많은 페이지를 내쫓는다.
  • 참조 횟수가 적은 페이지가 가장 최근에 참조된 것이라고 생각

잠깐! Paging시스템에서 LRU,LFU사용이 가능할까?

• 안타깝게도 NO!
  • 운영체제가 메모리 관리에 관여하긴 하지만, Page Fault가 일어날 때만 관여한다.
  • 따라서 운영체제는 물리적 메모리에 이미 올라와 있는 페이지들의 경우 언제 참조되었는지, 얼마나 참조되었는지의 정보를 알 수는 없다.
• 아니 그럼 왜 배운거에요????
  • 메모리 paging시스템에서는 사용이 불가하지만, 버퍼캐싱, 웹캐싱에서는 사용 가능하다.

5. Clock Algorithm(second chance algorithm)

• LRU의 근사 알고리즘
  • Not recently used (NRU) , Not used recently (NUR)
  • 최근에 사용되지 않은 애를 내쫓자!
  • 제일 오래 전에 사용했는지 보장은 X , 그러나 최근에 참조되지 않은 페이지를 내쫓는것이기 때문에 NRU 만족
• reference bit
  • 이미 메모리에 존재하는 page 또 참조하면(최근에 참조가 되면) 1로 변경
    • 운영체제가 아니라 하드웨어가 한다.
  • 나중에 운영체제가 page relpacement를 해야할 때 reference bit를 관찰한다.
    • 우선 1인 페이지를 0으로 변경하고 인덱스를 다음 페이지로 이동
    • 다시 돌아왔는데 bit가 0이면 해당 페이지 쫓아냄
    • 순환 큐 한 바퀴 도는 동안에 참조가 안된 페이지를 쫓아내는 것
• modified bit (dirty bit)
  • read/write 중 write로 참조가 되면 1로 설정
    • 나중에 0이면 그냥 쫓아냄
    • 1이면 적어도 한 번 수정된 것이기 때문에, backing store에서 먼저 변경 후, 쫓아냄

6. Cache

• 한정된 빠른 공간(Cache)에 요청된 데이터를 저장해 두었다가
  • 후속 요청시 캐시로부터 직접 서비스하는 방식
  • Paging System, Cache Memory, buffer caching, web caching 등
• Cache Locality
  • 공간 지역성
    • 최근에 사용했던 데이터와 인접한 데이터가 참조될 가능성이 높다.
    • ex) 배열
  • 시간 지역성
    • 최근에 사용했던 데이터가 재참조될 가능성이 높다.
    • ex) for, while → 특정 부분 반복해서 접근

1. 캐시의 시간제약

• 교체 알고리즘에서 삭제할 항목을 결정하는 것에 지나치게 많은 시간을 쓰면 안된다.
• LRU는 linkedList O(1), LFU는 O(logn)

2. Cache Line

• 필요한 데이터를 캐시에서 찾을 때 모든 데이터를 순회하는 것은 시간 낭비다.
  • 캐시에 목적 데이터가 저장되어 있을 때 바로 접근하여 출력할 수 있어야 함
  • 빈번하게 사용되는 데이터의 주소들이 흩어져 있기 때문에 캐시에 저장하는 데이터에는 데이터의 주소 등을 기록해둔 태그를 달아두어야 한다.
• 자료구조 활용
  • Direct Mapping
    • 메인 메모리를 일정 크기의 블록으로 나누어, 각각의 블록을 캐시의 정해진 위치에 매핑한다.
    • 단점
      • 적중률이 낮아질 수 있다.
      • 한 슬롯에 하나만 저장할 수 있기 때문에
        • 동일한 캐시 메모리에 할당된 여러 데이터를 사용할 때 충돌이 발생할 수 있다.
        
  • Full Associative Mapping
    • 캐시 메모리의 빈 공간에 마음대로 주소를 저장
    • 장점
      • 저장 쏘 간단
    • 단점
      • 원하는 데이터가 있는지 찾기 위해서 모든 태그를 병렬적으로 검사해야 한다.
      • 복잡하고 비용이 높다
      
  • Set Associative Mapping
    • Direct + Full Associative Mapping
    • 빈 공간에 마음대로 주소를 저장하되, 미리 정해둔 특정 행에만 저장하는 방식
      • 한 세트에 여러개를 저장할 수 있고, 교체가 필요할 때 이 안에서만 일어난다.
      • direct에 비해 검색 속도는 느리지만, 저장이 빠르다.
      • Full에 비해 저장이 느리지만, 검색은 빠르다.
      

4. Page Frame의 Allocation

• 가상 메모리, 멀티 프로그래밍 환경에서, 여러개의 프로그램이 물리적인 메모리에 함께 올라와 있다.
  • 지금까지는 물리적인 메모리 부족 → 페이지 교체 시
    • 어떤 프로세스냐에 관계없이, 그냥 오래된 거, 적게 참조한 거 등을 쫓아낸다고 함
    • 근데 사실, 한 프로세스 내에서 일련의 페이지들이 같이 메모리에 올라와 있어야 효과적이지 않을까?

1. Allocation Problem

• 각 프로세스에 얼만큼의 page frame을 할당할 것인가?
  • 명령어 수행을 위해 최소한 할당되어야 하는 frame의 수가 있다.
  • Loop를 돌고 있는데, 페이지 3개가 필요하다고 할 때, 한 번에 할당해주면 page fault가 안일어나지만
    • 최소한의 allocation이 없으면 매 loop마다 page fault

2. Allocation Scheme

• Equal alloctaion : 모든 프로세스에 같은 개수 할당
• Proportional allocation : 프로세스 크기에 비례하여 할당
• Priority allocation : 프로세스의 Priority에 따라 다르게 할당

5. Thrashing

1. Thrashing

: 프로그램에 최소 메모리도 할당되지 않아서 페이지 폴트가 빈번히 일어나는 경우

(CPU 이용 시간보다, 페이징에 더 많은 시간 사용)

• page fault rate이 매우 높아짐

• degree of multiprogramming
  • 처음 높일 때 : 메모리에 많은 프로그램이 올라오게 되면, I/O 때 다른 프로세스가 CPU를 사용할 수 있으므로 CPU Utilization이 올라감
  • 점점 더 많아지면 : 한 프로세스에 할당되는 메모리가 점점 작아져서, page fault가 자주 일어남 (Thrashing) → 페이지 교체 자주 일어남(Global로) → CPU Utilization 낮아짐
    • 게다가 OS는 CPU이용률을 감시하며, 너무 낮아지면 새로운 프로그램을 올려야 한다고 판단
    • 프로세스 당 할당된 frame의 수가 더욱 감소
      • 프로세스는 page 의 swap in/swap out으로 매우 바쁨
      • 대부분의 시간에 CPU는 한가
    • Low Throughput

Locality of reference

• 지역성
  • 프로세스는 특정 시간동안 일정 장소만을 집중적으로 참조한다.
  • 집중적으로 참조되는 해당 page들의 집합 = Locality Set

2. Global VS Local Replacement

• Global Replacement
  • 프로세스 별로 미리 할당해주지 않아도, 페이지 교체 알고리즘 하다보면 알아서 잘 뭉쳐서 할당된다.
    • 그때그때 어떤 프로세스가 메모리를 많이 요구하면 그 프로세스에 더 많은 프레임을 할당해줄 수 있음
  • Working Set, PFF
  • FIFO, LRU, LFU를 global replacement로 사용하는 경우
  • 다른 process에 할당된 프레임도 내쫓을 수 있음
• Local Replacement
  • 자신에게 할당된 frame에서만 replacement
  • FIFO, LRU, LFU를 프로세스별로 운영시 해당

3. Thrashing 해결방법 (Global Replacemet)

• Multiprogramming degree를 조절하자 (MPD)

1. Working-Set Model

• Working Set
  • 지역성에 기반하여 프로세스가 일정 기간동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page들의 집합
  • 과거를 보고 결정
  
• 운영체제는 각 프로세스의 working-set 크기를 모니터링하여 그 크기를 수용할 수 있을 만큼 프레임을 할당한다.
  • 만약 빈 프레임의 개수가 < workingSet size의 합보다 작으면
  • 일부 process를 swap out 시킨다. (중기 스케줄러 가동)
    • 모든 frame을 반납하고, swap out (suspend)
      • ex) 5개가 필요한데 3개밖에 줄 수 없다고 하면, 구차하게 받지 않고 반납
  • multiprogramming- degree 조절 → Thrashing 방지

2. PFF (Page-Fault Frequent) Scheme

• 직접 page fault비율을 봐서 MPD를 조절
  • 빈 frame이 없으면 일부 프로세스를 swap out
  • page fault rate
    • 상한값을 넘음 → frame을 더 할당
    • 하한값 이하 → 할당 frame 수 줄이기

4. Page Size

• page size를 감소시키면
  • 페이지 테이블 크기 증가
  • 장점
    • 내부 단편화 감소
    • 메모리 이용 효율 상승
      • 필요한 부분만 딱 올릴 수 있기 때문
  • 단점
    • Disk Transfer 효율성 감소
      • seek/rotation VS transfer
        • 디스크 seek 타임 엄청 긴데, 그렇기 때문에 한 번 가서 부욱 긁어오는게 더 효과적이다.
    • 지역성 감소
• 요즘 트렌드
  • → Larger page Size ! (4KB)

•