[운영체제] Virtual memory

한결·2023년 4월 27일
운영체제
1

CS

목록 보기
10/34

KOCW.이화여자대학교.반효경.운영체제
위 강의를 바탕으로 학습 및 정리했습니다

Virtual memory

  • 가상메모리 관리는 전적으로 운영체제의 역할

Demand Paging

  • 프로그램의 코드들은 대부분 방어적
    -> 거의 대부분이 사용안됨
    -> 모든 코드들을 메모리에 올리는건 비효율적

  • Demading paging을 사용하면 필요한 부분(코드)만 메모리에 올라감
    -> I/O 양 감소, 물리적 메모리 사용량 감소
    -> 현대 컴퓨터 환경(멀티 프로그램 환경)
    -> 더 많은 사용자, 프로그램이 메모리에 올라갈 수 있음
    -> 효율적, 더 빠른 응답 시간

Memory에 없는 Page의 page table

  • G,H 는 사용되지 않는 주소
    -> invalid, Swap area엔 없음

  • 물리적 메모리에 올라가지 않는 페이지(invalid)는 disk의 swap area에 내려가있음

  • disk에 있는 invalid 페이지 접근하려면 disk에서 가져와야함 (page fault : 사용하려는 코드 메모리에 없는 상황)
    -> I/O작업
    -> CPU 운영체제로 넘어감

Page Fault

Steps in Handling aPage Fault

  • page fault 처리 과정

Performance of Demend Paging

  • page fault의 빈도에 따라 처리 시간에 영향을 줌
  • p : page fault 발생 비율

Free Frame 없는 경우

  • reference string
    • 시간순으로 페이지가 참조된 순서

Page replacement

  • victim 결정되면 디스크로 쫒아냄
    • 근데 메모리에서 victim에 write가 발생된 경우
      victim 쫒아낼 때 변경된 내용을 저장해줘야함
    • write 없엇으면 그냥 쫒아내면 됨

Optimal Algorithm

  • page fault를 가장 적게 만드는 알고리즘

  • reference string 이미 알고있다는 가정하에
    가능한 알고리즘
    -> 실제 시스템에서 사용 불가 ㅜ

  • 쫒아낼 때 가장 먼 미래에 참조될 페이지를 쫒아냄

이 뒤부턴 미래를 모르는 상태에서 운영하는 알고리즘

FIFO Algorithm

  • First in First out

  • 일반적으로 메모리 늘려주면 성능이 좋아져야 하는데
    이놈은 메모리 늘려주면 page fault 더 많이 발생해서 성능이 나빠질 수도 있음

LRU Algorithm

  • Least Recently Used

  • 메모리 관리에서 가장 많이 쓰이는 알고리즘
  • 가장 오래전에 사용된거 쫒아냄
  • 마지막 참조 시점만 봐서 이전 참조 기록을 보지 않음
    -> 이전에 엄청 많이 사용했던거고 미래에도 엄청 사용할 페이지를 쫒아낼수도 있음

LFU Algorithm

  • Least Frequently Used

  • 참조 횟수가 가장 적은 페이지를 쫒아냄
  • 이제 막 사용을 많이 하려는 페이지를 쫒아낼 수도 있는 단점 존재

LRU / LFU 예제

  • LRU
    • 마지막 참조 시점만 봐서 이전 참조 기록을 보지 않음
      -> 이전에 엄청 많이 사용했던거고 미래에도 엄청 사용할 페이지를 쫒아낼수도 있음
  • LFU
    • 이제 막 사용을 많이 하려는 페이지를 쫒아낼 수도 있는 단점 존재

LRU / LFU 구현

  • LRU
    • 참조 시간 순서로 나열해서 관리 / 참조 될 때마다 맨 아래로
    • 맨 위의 페이지가 가장 사용한지 오래된 거니까
      맨 위 페이지 쫒아냄
      -> 매번 victim을 결정하기 위해
      시간을 비교해볼 필요가 없음
  • LFU
    • 사용횟수 만큼 나열하는 방식으로 구현하면 매번 비교가 필요함 (O(n))
      -> heap을 이용해서 구현 (O(log n), 100번 비교에서 20~30 회로 줄어듬)

다양한 캐슁 환경

  • 교체(replacement) 알고리즘은 다양한 환경에서 사용됨
    -> 통칭 캐슁(빠른공간에 어떤 걸 저장하고 쫒아낼 것인가)

  • 한정된 빠른공간 -> 예) 메모리

  • 캐쉬 메모리가 메인 메모리보다 더 한정되고 빠른 공간

  • buffer caching

    • 파일 시스템에서 한정된 빠른공간(디스크의 파일 시스템)에 보관해서
      다음번에 다시 요청됐을 때 재사용을 빨리하기 위한 캐슁

  • 하나의 컴퓨터 시스템 안에서 각 매체들의 속도차이를 완화하기 위해 사용

  • Web caching

    • 웹 페이지를 읽어와서 브라우저에 띄울 때
      첫트 후에 하드 디스크에 저장해놓고
      같은 페이지를 다시 띄울 땐 멀리있는 서버에서 가져오는 것이 아닌 첫트에 받아놓은 내용을 바로 띄움

Paging System에서 LRU, LFU 가능한가?

  • 실제로 안씀

  • 이미 메모리에 올라간 페이지를 접근할 때는 운영체제의 개입 없어도 됨
    +주소변환은 하드웨어 적으로 주소 변환이 됨 -> 운영체제는 페이지가 언제 사용됐는지 모름
    -> LRU/LFU 처럼 줄세우기가 아예 불가능함

  • page fault 나서 운영체제의 개입으로 디스크에서 메모리로 올라가는 페이지는 알수가 있지만 그 외는 위의 이유 때문에 알 수가 없다

Clock Algorithm

  • LRU/LFU 말고 이걸 실제로 사용

  • 네모 : page
  • 네모안의 값 : reference bit
  • reference bit = 0 인 페이지를 쫒아냄
  • reference bit = 0 인 페이지가 사용한지 가장 오래된 페이지는 아님
    == LRU 근사
  • 시계바늘이 돌아가면서 1을 만나서 0으로 바꾸고 넘어감
  • 0을 만나면 쫒아냄
  • 와중에 또 사용되면 1로 바뀜
    즉, 바늘이 한바퀴 돌때까지 사용안된게 쫒아내짐
  • modified bit
    • page가 메모리 올라온 다음에 CPU가 write해서 수정하면 1이 됨
    • 메모리 올라온 이후로 page가 수정되면 디스크에 수정된 걸 저장한 후 쫒아내야하기 때문에 사용

Page Frame의 Allocation

  • 앞에서의 알고리즘들은 어떤 프로세스의 page인지 고려하지 않음
  • Loop를 구성하는 프로세스 전용 page안주면 Loop돌 때마다 page fault가 발생할 것이기 때문에 어떤 프로세스인지에 대한 고려가 필요함
  • Equal allocation
    • 프로그램마다 크기가 다르기 때문에 부적절
  • Priority allocation
    • CPU priority 순으로 할당

Global vs Local replacement

  • Global
    • 필요한 만큼 뺏어오는 무한 경쟁
  • Local
    • 자기 몫을 주고 그 안에서 효율적으로 쓰기

Thrashing Diagram

  • x축 : 사용중인 프로그램 개수
  • y축 : CPU사용률
  • 뚝떨어지는 부분 Thrashing이 일어낫다 표현
    • 프로그램 너무 많으면 각 프로세스에 할당 되는 메모리가 너무 작기 때문에
      page fault가 계속 발생
      -> CPU사용을 안하고 page fault 처리하는 상황만 발생해서 뚝떨어지는거
      -> 근데 운영체제 입장에선 CPU가 놀고 있다고 판단하고 실행되는 프로세스 더 늘려도 된다 판단
      -> 계속 I/O 작업만 하게되는 상황 반복

Thrashing

Working-Set Model

  • Working Set을 이루는 page들에겐 무조건 메모리 보장해줌
  • 나머지는 메모리 완전 반납하고 swap out
  • 짜투리 공간받자고 메모리에 계속 남아있는 하남자 방식이 아님

Working-Set Algorithm

  • Δ(window size)만큼 이전 범위안에 사용된 page(중복없이)들을 working set으로 간주

  • memory 부족해서 working set보장 안되는 프로세스는 가차없이 쫒아냄 (나중에 working set보장 되는 시점에 다시 들어옴)

PFF Scheme

  • Page-Fault Frequency

  • PF 비율이 범위안에 들어오면 frame할당 멈춤
  • 메모리에 올라와 있는 프로세스라도 비율 안에 있도록 관리

Page Size의 결정

  • page size 작으면 장점

    • 메모리 사용 효율 좋음
    • 내부 조각 감소

  • page size 작으면 단점

    • Page fault의 자주 발생
      -> Dist transfer 효율 감소
    • Locality의 문제
      • Locality: 어떤 메모리가 사용되면 인접 위치가 사용될 확률이 높은 성질
      • 당장 요청 안되는 걸 가져오면 좋음
profile
한결
이전 포스트

[운영체제] 메모리 관리

다음 포스트

[운영체제] 파일시스템

0개의 댓글