2024. 6. 2. 13:18ㆍCS/Operating System
Thrashing
동시에 사용하는 프로세스의 수를 계속 늘리게 되면 CPU 사용률도 계속 증가하다가 임계점을 넘어가면 CPU 사용률이 줄어드는 현상이 생긴다.
- 메모리가 부족해지는 순간에 Thrashing이 생기면서 대부분의 시간을 OS가 디스크를 왔다 갔다 하면서 Page fualt를 계속 해결하면서 CPU가 사용되지 못한다.
- 메모리가 overcommitted 된 상황이라고도 하며, overcommitted라는 용어는 시스템이 사용할 수 있는 용량보다 훨씬 더 많은 프로세스, 메모리를 사용하는 상황을 말한다. Thrashing 현상이 일어나면 OS는 page fault를 줄이기 위해 어떻게 해야 할지 모르고 page fault만 계속 일어나면서 I/O는 계속 일어나고 CPU는 계속 I/O만 기다리게 된다.
- 해결법은 메모리를 좀 더 사던지, 프로세스를 더 이상 띄우지 못하게 하던지가 있다.
Working Set Model
Working Set :어떤 프로세스가 현재 잘 돌아가기 위해서 필요한 페이지들의 집합
- 프로세스의 working set 안에서는 dynamic locality가 생긴다.
예를 들어 위의 사진에서 프로세스 A가 페이지 0, 1, 2, 3만 계속 액세스 하면서 실행된다면 Working Set은 4개가 된다.
Working Set은 수학적 정의를 보자.
WS(t, w) = { 시간 간격 (t, t-w) 동안 참조된 페이지와 같이 정의할 수 있고 t, w를 파라미터로 받는다. t는 현재 시간, w는 working set window size가 된다. (t, t-w) 사이에서 액세스 되는 페이지를 WS라 할 수 있다.
Working set size
- 몇 개의 페이지가 있어야 프로세스가 이 순간에 잘 돌아가는지를 체크하는 것이고, 프로세스의 locality 특성에 의해 결정된다.
- 예를 들어 초반에 10000 size 배열을 생성하고, 초기화하는 작업을 생각해 보면 WSS는 클 것이고 locality는 좋지 않을 것이다.
- 그 후 10~100 사이를 for문을 계속 돌면서 무언가를 수행한다면 WSS는 작아지고 locality는 좋다.
- 당연하게도 WSS는 작아야 좋고, thrashing을 방지하기 위해서 WSS만큼의 페이지를 할당할 수 있어야 한다.
thrashing을 방지하기 위해 WSS를 파라미터로 멀티프로그래밍의 정도가 결정된다.
- WSS에 딱 맞도록 total frame의 수를 조절하면서 프로세스를 띄울 수 있을 것이다.
Working set page replacement
프로세스 A가 어느 순간에 WSS가 10이라면 페이지 replacement를 어떻게 할지 정할 수 있다.
- 최근 k번의 메모리에 대한 접근동안 working set을 계산한다.
- 대략적인 working set을 알아야 한다.
- current virtual time이 필요하다. current virtual time은 프로세스가 실제로 사용된 CPU time의 양이다.
- working set에 속하지 않은 페이지는 evict한다.
- 이 작업을 위해 마지막에 사용된 시간이 PTE에 있어야 한다.
- 주기적으로 R bit를 0으로 만드는 작업을 수행한다.
- 모든 page fault에서 evict할 페이지를 찾기 위해 page table scan이 일어난다.
- R = 1이면, timestamp를 현재 virtual time으로 설정
- R = 0이고 Tcurrent - Tlast > t(windows size)이면, evict the page
- R = 0이고 Tcurrent - Tlast < t 이면, 아무것도 하지 않는다.
current virtual time : 2204
각 페이지별로 last use time과 R bit이 존재한다.
메모리가 부족해지면 화살표 방향대로 스캔을 수행한다.
R bit가 1이라면 이전에 스캔하고 다음에 돌아올 때까지 해당 프로그램에 액세스가 일어난 것이고, 그 시간도 기록해 두었다. 또 스캔하면서 마지막에 액세스 된 시간을 기록해 둔다.
R bit가 0이라면 예를 들어 1213|0 페이지를 보면 마지막 액세스가 1213초이다. current virtual time과의 차이를 age라 하는데, age가 쓰레시 홀드값보다 크다면 날려버린다. R bit가 0이어도 age가 쓰레시 홀드값보다 작으면 그대로 둔다.
만약 t를 600이라 생각한다면 어떤 게 날아갈까? 밑에서부터 보자.
1번은 age가 600보다 작으므로 살려둔다.
2번, 3번, 4번은 살려두고 5번은 age가 600보다 크므로 빼버린다.
PFF (Page Fault Frequency)
각 프로세스에 대해 page fault가 얼마나 일어나는가를 모니터링한다.
PFF가 threshold(기준값) 보다 높다면
- 좀 더 많은 메모리를 할당한다.
- 항상 옳지는 않은 게 FIFO의 벨라디 모순을 생각하면 메모리를 많이 준다고 해결되지는 않는다.
PFF가 너무 낮다면
- 메모리를 뺏어온다.
PFF가 증가하는데 할당할 수 있는 프레임이 없다면
- 프로세스를 선택해서 중지시킨다거나 할 수밖에 없다.
Shared Memory
프로세스 간의 virtual address space는 서로 볼 수 없고 보호되어야 한다.
share data는 매우 어렵다.
- 웹 서버나 프록시서버 같은 건 copying 없이 메모리 안에서 공유할 필요가 있다.
- 라이브러리는 공유해서 execute 해야 한다.
- share data에는 read write를 할 수 있어야 한다.
shared memory를 사용하여 프로세스들이 특정한 메모리 조각을 공유해서 서로 레퍼런스 할 수 있게 할 수 있다.
shmget, shmat는 라이브러리 함수인데 어차피 그 내부는 시스템콜을 호출한다.
Shared Memory Implementation
- 페이지 테이블을 사용해서 shared memory를 어떻게 구현할 수 있을까?
- 공유하려는 대상 프로세스의 PTE를 같은 프레임을 가리키게 하면 된다.
- protection도 잘 관리할 수 있다. 페이지는 각각의 Protection bit를 가지기에 각각의 Protection bit를 통해 프로세스 A의 page table에 read write를 주고 프로세스 B의 page table에는 read만 주면 된다.
- 주의할 점이 메모리에서 디스크로 메모리가 내려간다면 invalid 비트를 공유하는 프로세스 테이블에 모두 세팅해줘야 한다.
- 공유하는 프로세스끼리 virtual page가 동일해야 할까? virtual page가 동일하다는 의미는 영역을 별도로 따로 지정해서 save 해놨다가 언제든 부르면 사용할 수 있어야 한다는 것이다.
- virtual page가 다르다면 Flexible 하다. address space conflicts가 생기지 않는다. 하지만 shared memory segment 안에서의 포인터는 유효하지 않다. 예를 들어 프로세스 B에서 포인터를 받거나 쓰거나 했는데 그걸 그대로 옮겨서 프로세스 A에 적용하면 원하는 대로 동작하지 않는다.
- virtual page가 동일하다면 flexible은 굉장히 떨어지겠지만 포인터를 쓸 수 있다는 장점이 생긴다.
Copy on Write
프로세스를 fork를 불러서 만들면 address space를 몽땅 복제해서 child에 넘겨준다. 매우 느리고 비효율적이다.
address space를 효율적으로 공유하려면 스레드를 사용해서 address space를 공유할 수 있었다.
쓰레드를 사용하지 않고 프로세스를 만들고 싶은데, address space를 효율적으로 공유하고 싶다면 vfork 시스템 콜을 사용할 수 있다.
- vfork 시스템 콜을 호출하면 child를 새로 만들지 않고 parent와 공유하게 된다.
- 그런데 parent와 address space를 공유하면 동기화 문제가 생겨버린다. 동기화 문제를 막기 위해 parent를 block 시키고 child만 동작시킨다.
- child가 금방 죽어버린다거나, exec로 다른 코드로 아예 바뀌기를 parent가 기다리고, child가 종료되면 parent는 child의 수정 사항을 확인할 수 있다.
- child가 exec()를 바로 실행할 때 유용하다.
또 다른 방식으로 Copy On Write를 사용할 수 있다.
- fork를 부를 때 COW 메커니즘을 설정해서 부르면 child process에 페이지 테이블을 복사해서 넘겨주고 각 테이블 엔트리에 COW 필드를 둬서 마킹해 둔다.
- 마킹을 해둔 PTE를 read 할 땐 그냥 읽는다.
- write는 어떤 과정을 거치게 될까?
- write 연산에서 동기화 문제가 생길 수 있으므로 COW 필드를 보고 protection fault를 발생시킨다.
- 그럼 OS는 COW 필드를 보고 페이지를 복제해서 페이지 테이블 매핑을 바꾼다.
- 이건 각 페이지별로 동작하기에 write가 일어난 페이지에만 복제가 일어나고 write가 일어나지 않은 페이지는 공유하게 된다. child가 바꾸려고 하는 몇몇 데이터들의 프레임들 몇 개만 copy 해주면 address 전체를 복제하지 않고도 효율성 좋게 공유하게 된다.
- write 연산을 다시 시작한다.
Copy On Write는 Shared memories 느낌으로 page table만 복제하고 메모리를 공유해서 사용하다가 write가 일어나면 그때서야 copy on write를 보고서 protection fault가 발생하면서 write가 일어난 프레임만 복제하는 것이다.
- COW는 사실 메모리에서만 쓰이는 건 아니다. VMware에서도 많이 사용한다. 디스크에 있는 이미지를 가지고 가상 머신이 돌아가게 될 테고 VM이 추가되면 디스크에 있는 이미지는 거의 동일한데 복제하게 될 것이다. 너무 비효율적이기에 COW 기법을 사용해서 뭔가 변경되면 그 부분만 복제하는 것이다.
Memory mapped files
Mapped files는 프로세스들이 file I/O를 메모리 참조를 사용해서 하게 하는 기술이다.
- 일반적으로 file I/O는 open 해서 read write 하는 게 일반적이다.
mmap()을 통해서 특정 파일을 메모리에 매핑해서 쓰는 방식을 사용할 수 있다.
- PTE는 file data가 있는 피지컬한 frame에 virtual address를 매핑한다.
- <Virtual address base + N> = <offset N in file>이 된다.
처음에는 모든 페이지를 invalid 상태로 두고, invalid 페이지에 접근하면 OS는 파일로부터 페이지를 읽어오게 된다.
피지컬한 메모리에서 evict 되면 OS는 페이지를 파일에 쓰게 된다.
mmap을 unmap 하게 될 때 page가 clean 하다면 매핑을 해제하고 끝이고 dirty상태라면 파일에 다시 써주고 매핑을 해제한다.
mmap이 성공하고 나면 address pointer를 받게 된다. 리턴 받은 address pointer를 addr이라 하면, addr은 virtual address이고 addr은 frame을 가리키고 있고 frame은 파일을 가리키고 있다.
메모리에 매핑했으므로 fd는 그냥 닫아버려도 된다.
처음에는 매핑하더라도 invalid 상태로 페이지 테이블에만 할당된 상태가 된다. 그리고 해당 파일에 접근이 일어나면 프로텍션 폴트가 일어나면서 프레임 할당이 일어난다. 파일이 8KB라 치면, 앞에 접근이 일어난다면 앞의 4KB만 페이지 할당이 일어난다. 액세스가 일어날 때 할당이 일어나는 것이다.
장점
- 파일과 메모리에 같은 방식으로 접근할 수 있다. 그냥 포인터를 사용하면 되는 것이다.
- copying이 줄어든다.
- 같은 파일을 매핑함으로써 메모리를 공유할 수 있다.
단점
- 언제 메모리에 올라오고 언제 디스크에 내려가서 기록이 될지 컨트롤을 할 수 없다.
- 내부에서 streamed I/O를 제공하는데, 그 방식의 이점을 얻을 수 없다.
참고
- real file에 의해 백업되지 않은 virtual address space는 anonymous VM page라 한다.