Virtual Memory

Demand Paging

요청시 메모리에 올린다. 실제로 필요할 때 page를 메모리에 올리는 것
당장 필요하지 않는 것은 backing store, disk, swap area에 있다.

효과

• I/O 양 감소: 필요한 것을 올리기에
• 메모리 사용량 감소: 동시에 많은 것이 올라갈 수 있음
• 빠른 응답 시간 : system wide하게. 더 의미있는 페이지가 올라가고, 한정된 메모리를 더 잘 씀
• 더 많은 사용자 수용

그래서 Valid / Invalid bit을 사용함
Invalid : 사용되지 않는 주소 영역, 페이지가 물리적 메모리에 없는 경우
invalid bit이 set돼있으면 Page Fault ➡️ 요청한 것이 메모리에 없을 때 trap(s/w interrupt) 발생 시킴.

Page Fault 란?

OS의 대처가 정의되어있음

• invalid bit set page에 접근시 MMU가 trap 발생시킴 ➡️ page fault trap
• OS는 kernel mode로 들어가 page fault handler가 invoke됨

Page Fault 처리

1. invaid reference? 잘못된 요청인지 아닌지 확인하기. 그 후 abort process
2. empty page frame 가져오기. 없다면 뺏어온다.
3. 해당 페이지를 disk에서 메모리로 읽어온다.

• disk I/O로 해당 프로세스 preempt 후 block
• disk read 종료 후 entry 기록 후 valid set
• ready queue에 process 다시 줄 세우기

4. 다시 CPU가 오면 run. 중단된 instruction 재개

➡️ 오버헤드가 엄청 남. (page fault, swap out, restart 등)

Free Frame이 없을 경우

• Page replacement: 어떤 frame을 뺏을지 결정해야 함
• Replacement Algorithm : Page fault rate 최소화.
  되도록이면 page fault가 안나고, 메모리에서 직접 처리가 가능하도록 replace하기.

Optimal Algorithm

미래를 알고 있다고 가정 (reference string을 알고 있다.)
page fault를 가장 적게하는 알고리즘
가장 먼 미래에 참조되는 page 선택

하지만 미래 참조를 모른다.
다른 알고리즘의 성능에 대한 upper bound를 제공.

FIFO Algorithm

미래를 모르니 과거를 통해 선택
먼저 들어온 것을 먼저 내쫓음
하지만 Frame이 늘어나면 page fault가 늘어나는 경향이 있음

LRU Algorithm

가장 최근에 덜 사용된. 들어온 이후로 사용 횟수를 기준으로
가장 잘 사용되는 알고리즘. page fault를 가장 줄일 수 있음.

단점: 그 이전의 기록을 고려하지 않는다

구현

Linked List 이용 ➡️ O(1) : 가장 앞쪽을 선택하면 된다.
줄을 세워 가장 앞에 있는 것이 LRU
가장 뒤에 있는 것이 MRU
새로 참조 되는 것은 가장 뒤쪽으로 이동시킨다.

LFU Algorithm

참조 횟수가 가장 적은 페이지를 선택

• 최저가 여러 개면 : 임의로 선정 혹은 가장 오래 전에 참조된 것을 선택

단점: 이제 막 참조가 시작되고 있는 것이라 이후에도 또 참조되는 것일 수도 있음 (참조 연속)

구현

Heap 이용 ➡️ O(logn)
참조가 한번 증가한다고 가장 참조 횟수가 많은 것이 아니라서 모든 항목과의 비교가 필요함.
LL을 사용하면 O(n)이 걸리게 된다. 그래서 min heap을 이용한다.

다양한 캐슁 환경

Cahching
빠른 공간인 캐쉬에 요청된 데이터를 저장해두고 또 요청하면 캐쉬에서 제공하는 방식
다양한 분야에서 사용한다.

• 시간 제약
  쫓아낼 것을 고를 때 지나치게 많은 시간이 걸리면 안된다.
  Buffer 이나 web caching의 경우 : O(1) ~ O(logn)

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

OS가 참조 횟수, 참조 시점 등을 관리해야 하는데 virtual은 OS가 관리하지 않고, CPU가 넘어와야 알기 때문에 사용할 수 없다. 즉, Page fault일 때만 OS가 CPU를 얻기에 모른다.

그래서 Clock Algorithm

LRU의 근사 알고리즘.
Second chance algorithm, NUR, NRU (not recently used)

• Cicular list 이용
• Reference bit 사용 : H/W가 ref bit을 1로 바꾼다.
  포인터가 이동하는 중에 ref bit이 1이면 0으로 바꾸고, 0이라면 그 페이지를 교체 대상으로 선정
• 추가로 modified bit 이용 (개선 사항)
  dirty bit이 0이면 write X이니 메모리에서 그냥 쫓아내지만, 1이라면 write O이라 disk에 새로 올려둔 뒤 쫓아내야 함. 그래서 0인 것 부터 우선적으로 쫓아 낸다.

Page Frame의 Allocation

원래는 어떤 프로그램의 page인지 신경쓰지 않아, page 개수의 불균형 있음

Allocation의 필요성

• 명령어 수행을 위해 최소 할당 필요 frame 수가 있다.
• 하나의 program만 올라오는 비효율 방지 <=???

Allocation Scheme

• Equal_ : 모든 프로세스에 같은 개수 할당. 프로그램마다 크기가 달라서 비효율 발생
• Proportional_ : 프로세스 크기에 비례하여 할당. 시간에 따라 필요한 크기가 다를 수 있어 비효율
• Priority_ : 우선 순위에 따라 할당

Global vs Local Replacement

• Global
  Replace시 다른 Process에 할당된 frame을 뺏어 올 수 있다.
  Process 별 할당량을 조절하는 방법
  FIFO, LRU, LFU를 사용하면 알아서 조절되는데, Worling set, PFF 알고리즘이 더 효과적

• Local
  자신에게 할당된 frame 내에서만 쫓아내기

Thrashing

할당이 적어서 page fault가 빈번히 일어남
프로세스의 원활한 수행에 필요한 최소한의 page frame수를 할당 받지 못한 경우

• Page fault rate이 매우 높아짐
• CPU utilization이 낮아짐
• OS는 MPD를 높여야 한다고 판단
• 또 다른 프로세스가 추가됨.
• 무한 반복으로 프로세스는 매우 바쁘지만, CPU는 한가함

➡️ Mutiprogramming degree MPD를 조절해야함.
특정 MPD까지는 CPU utilizaion이 높지만, 일정 수준을 넘어가면 Thrashing 발생
그래서 working-set, PFF 알고리즘을 이용함

Working-set Alogrithm

• Locality of reference
  프로세스는 특정 시간동안 일정 장소만 집중적으로 참조. 이렇게 집중적으로 참조되는 page의 집합을 locality set이라 함

_Model

Locality에 기반하여 한꺼번에 메모리에 올라와있어야 하는 page들의 집합을 Working Set이라 함
한꺼번에 올라와 있도록 보장해줘야 함
해당 집합이 전체다 올라와있어야 수행되고, 그렇지 않다면 모든 frame을 반납 후 suspend된다.

• Thrashing 방지
• MPD 결정

_Algorithm

• Working set 결정
  과거를 통해 추청. Window 이용.
  window size를 특정 시간으로 두고. 해당 시간 크기 만큼을 window라 함.
  이 시간 만큼은 쫓아내지 못함
  즉, 참조된 후 특정 시간 동안 해당 page를 메모리에 유지 후 버리는 것.

• 방법
  Working set size의 합이 page frame 수보다 큰 경우 : 일부 프로세스를 swap out 시켜 남은 process의 working set을 우선적으로 충족. 여유가 생기면 그때 올린다.

Page-Fault Frequency PFF Scheme

추정하지 않고, page fault rate을 직접 관찰. 시점과 어느 프로세스인지 관찰
bound가 있어 upper 혹은 lower을 관리함

• Upper bound 위 : working set이 보장되지 않는 것으로 보고 frame을 더 할당한다
• Lower bound 아래 : frame이 쓸데 없이 너무 많이 할당된 것으로 보고 할당된 frame을 줄인다.
• 빈 frame이 없으면 일부 프로세스를 swap out

➡️ page fault가 일정 수준이 되도록!

Page size 결정

• 감소시키면

  • 페이지 수 증가
  • 페이지 테이블 크기 증가 : 낭비
  • 내부 조각 감소
  • 필요한 정보만 올라와있어 메모리 이용이 효율적

  하지만

  • Disk transfer의 효율성 감소.
    Disk에 가서 Seek가 늘어남. ➡️ 시간 오버헤드. 일일히 찾아야기 때문에
    그래서 한번에 많은 것을 올리는 것이 좋음
  • Locality 활용 측면에서 좋지 않음
    한번 page fault가 난 이후로 올라와있다면 page fault가 거의 나지 않기에 한번에 많이 올라간 것이 나음.

  ➡️ 페이지 크기가 큰 것이 좋음. 그래서 요즘은 증가시키는 추세

File systems

File

A named collection of related information

• 하드디스크 같은 비휘발성의 보조기억장치에 저장
• 동일한 논리적 단위로 볼 수 있게 함
• 연산 : create, read, write, delete, reposition

File attribute (metadata)

파일을 관리하기 위한 각종 정보들. 파일의 내용은 아님

File system

OS가 파일을 관리하는 부분
파일, 파일 메타데이터, 디렉터리 정보 등을 관리
저장 방법, 보호 등을 결정함

Directory

파일의 메타데이터를 보관하고 있는 일종의 파일
내용 : 하위 파일들의 메타 데이터
연산 : search for file, create a file, delete a file, list a directory, rename 등

Parition (Logical Disk)

OS는 논리적 디스크를 보고 관리함
물리를 여러 파티션을 두어 나눔
file system 혹은 Swap area로 이용함

Open()

파일의 메타데이터를 메모리에 올려둠

fd=open("/a/b")

1. 프로세스가 해당 명령어를 하면 system call로 CPU가 OS에게로 넘어간다.
   root-> a-> b 순서로
2. 논리 디스크에서 해당 파일의 metadata를 찾는다.
3. 이를 open 한다. 즉, 커널 메모리 영역의 Open file table에 올려둔다.
4. 또 찾을 것이 있다면 해당 메타데이터를 통해 위치를 찾아간다.
   반복
5. 최종으로 open한 메타데이터의 위치인 fd(file descriptor)을 PCB에 저장한다.

open file table은 system-wide하여 한개만 존재한다.

read(fd)

fd를 매개로 넘겨 읽어온다. 파일 크기를 지정함
1. system call로 CPU가 OS에 넘어간다.
2. PCB에 저장해둔 fd를 통해 해당 메타데이터를 찾아간다.
3. Open file table에서 찾은 해당 메타데이터로 논리 디스크에서 해당 위치를 찾아간다.
4. 그곳의 content를 읽어서 커널 메모리 영역 한 위치에 일부 읽어 둔다.
5. 읽어둔 것을 copy해서 프로세스에게 전달한다.

4번 == Buffer Caching

OS는 논리 디스크에서 읽어오기 전 이 부분을 먼저 확인하고 있으면 이것을 전달함.
OS가 이것을 계속 관리하기에 paging과 달리 LRU, LFU가 가능하다. 왜냐하면 파악하고 있으니깐.

Process마다 어느 논리 디스크 부분을 접근하고 있는지 offset이 필요하다.

File Protection

접근 권한과 어떠한 접근인지에 대한 관리가 필요하다.

Access Control 방법

1. Access control Matrix

행에는 파일, 열에는 사용자를 두어 행렬로 권한을 표시해둠
➡️ sparse matrix 형태로 낭비가 큼

Linked List로 구현
1. ACL
파일이 주체가 되어 사용자 목록을 연결함
2. Capability
사용자가 주체가 되어 파일 목록을 연결함

➡️ 그래도 오버헤드가 있다.

2. Grouping

모든 user을 owner, group, public의 세 그룹으로 구분하여 3비트씩 총 9비트로 표현
각 그룹 마다 권한을 표시해둔다.
가장 효율적인 방법

3. Password

파일 마다 password를 두는 방법
➡️ 굉장히 많아지고, 관리가 어려워짐

File System의 Mounting

서로 다른 파티션이라도 접근 가능하도록
한 파티션의 어떤 directory에 다른 파티션의 root를 연결해둠

Access Methods

시스템이 제공하는 파일 정보 접근 방식

• 순차 접근
  카세트 테이프처럼 a,b,c의 순서를 가진 파일 목록이 있을 때, a에서 c로 가려면 무조건 b를 거쳐야 함.
• 직접 접근
  LP 레코드 판처럼 특정 위치에 바로 접근 가능. 임의의 순서로 접근 가능.
  하지만 관리에 따라 순차 접근만 가능한 것이 있다.