[운영체제] Virtual memory(2)

이 글은 개인의 학습을 목적으로 정리한 글입니다. 이점 참고하고 읽어주세요;)

---

캐싱 기법: 한정된 빠른 공간에서 데이터를 저장해서 다음에 같은 요청이 오면 느린 메모리까지 가지 않고 속도가 빠른 캐시에서 바로 처리

* cache memory: CPU와 메인 메모리 사이에 존재. 

* web caching: 브라우저에서 웹서버에 페이지를 요청할 때, 사전에 호출했던 페이지라면 굳이 웹서버까지 가지 않고 캐시에서 바로 가져옴

 

캐시 replacement에서 시간 제약: replacement에 너무 많은 시간이 소요되면 안 됨.

 

LRU(가장 예전에 참조): 캐시 안에 n개의 데이터가 있을 때, 일단 최근에 호출된 프로세스를 MRU page로 보내면 되기 때문에 시간 복잡도가 O(1)(비교가 필요 없음)

 

LFU(가장 적게  참조): 줄 세우기 개념은 LRU와 유사하지만, 각 page별로 참조 횟수를 비교해야 하기 때문에 최악의 경우 O(n)의 시간 복잡도. heap을 사용하더라도 O(log n)의 시간 복잡도

 

-> 때문에 replacement의 시간 복잡도는 O(1)에서 O(log n)까지 허용

 

요청한 page가 물리적 메모리에 올라와있는 valid 상태 -> 그 주소를 읽어와서 실행

요청한 page가 물리적 메모리에 없는 invalid 상태 -> page fault 발생 -> 디스크와의 swaping 혹은 replacement 즉, I/O가 필요함 -> 이는 프로세스가 직접 접근이 불가능하기 때문에 page fault trap이 발생하고, CPU 제어권이 프로세스 A에서 운영체제로 넘어감 -> 운영체제가 디스크에 접근해서(디스크 역시 IO device) 필요한 page를 가져와서 물리적 메모리에 올리거나, 물리적 메모리에 자리가 없다면 replacement 진행

여기서 어떤 page를 쫓아낼지 운영체제가 확인. 그런데 여기서 운영체제가 과연 가장 오래전에 호출된 page, 혹은 참조 횟수가 적은 page를 알 수 있는가? 알 수 없다...

운영체제는 page table에서 valid 상태이기 때문에 이미 물리적 메모리에 올라간 page의 정보를 운영체제는 알 수 없음. 접근 시간, 호출 시간 등등의 정보를 알 수 없음. 하지만 page fault가 나면 그때는 운영체제에게 CPU가 넘어가기 때문에 이 경우에만 디스크에서 물리적 메모리로 page를 올리면서 호출 시간 등등의 정보가 운영체제에게 넘어감.

 

운영체제는 paging 과정에서 절반의 정보만 알고 있음. 때문에 LRU, LFU와 같은 알고리즘을 paging 시스템에서 사용할 수 없음

---

시곗바늘이 가리키는 네모들이 각각의 page들. 네모 안의 숫자는 reference bit.

reference bit: 해당 page가 최근에 호출이 되면 bit를 1로 바꿔서 참조되었다는 걸 표시. 이는 운영체제가 아닌 하드웨어가 하는 작업

 

운영체제가 하는 작업 ->

reference bit이 1인 page를 만나면 그 페이지는 쫓아내지 않고 대신 reference bit만 1로 변경. 시곗바늘이 한 바퀴 돌아오는 동안에 적어도 한 번의 참조가 있었다는 뜻이기 때문.

reference bit이 0인 page를 만나면 그 페이지를 쫓아냄. 시곗바늘이 도는 동안 참조되지 않았기 때문.

 

LRU와 같이 가장 오래전에 호출된 page는 아닐지라도, 적어도 시곗바늘이 도는 동안에는 참조되지 않은 page를 쫓아냄. 

* modified bit: 메모리에서 write가 발생하면 하드웨어가 이 bit를 세팅. 어떤 page가 쫓겨날 때 modified bit가 0이라면 그 page는 디스크에서 메모리로 올라와서 변경되지 않았기 때문에 그냥 메모리상에서 쫓아내기만 하면 됨. 하지만 modified bit가 1이라면 디스크에서 메모리로 올라온 다음 변경이 있었기 때문에 메모리에서 쫓아내기 전에 디스크에 변경 사항을 저장한 뒤에 쫓아내야 함. -> 가능한 modified bit가 1인 페이지는 덜 쫓아내고 0인 page를 위주로 쫓아내면 디스크에 변경사항을 저장하는 리소스 소비가 줄어들어 조금 더 효율적인 CPU 운용이 가능함

 

이 clock algorithm을 page replacement에서 사용함.

---

Page Frame Allocation: 각각의 프로그램에게 어느 정도의 메모리를 나눠주는 것.

 

Global Replacement: 메모리 전체에 대해 replacement 실행. 이를 실행하다 보면 어느 정도 allocation이 조절. 

Local Replacement: 자신에게 할당된 영역에 대해서만 replacement 실행.

---

프로그램에게 최소 메모리도 할당되지 않아 page fault가 너무 자주 일어나는 상황을 Thrashing이라고 부름.

 

degree of multiprogramming: 사용되는 프로그램 개수

-> 프로그램 개수가 늘어날수록 CPU utilization이 증가. 

이렇게 CPU Utilization이 증가하다가 Thrashing이 발생하면 page fault가 빈번히 발생하면서 utilization 감소(어떤 프로세스가 CPU를 잡아도 page fault 때문에 운영체제가 메모리에서 page를 쫓아내고 디스크에서 가져오고 하는 작업 발생) -> 메모리에 프로그램이 너무 많이 올라가서 각 프로그램에 필요한 최소한의 메모리도 없어서 계속 page fault가 발생. 

그런데 운영체제는 CPU Utilization이 낮으면 메모리에 올라간 프로그램의 개수가 적은 것으로 판단하고 메모리에 프로그램을 더 올림. 이렇게 악순환이 반복됨.

이를 해결하기 위해서는 메모리에서 동시에 진행되는 프로그램 수를 조절. 이게 바로 working-set algorithm과 page frequency

---

Locality of reference: 프로그램들이 메모리에서 원활하게 실행되기 위해서는 최소한의 공간을 확보해야 함. 

또한 프로세스는 특정 시간 동안 일정 장소만을 집중 참조. ex) for 루프가 실행되는 동안에는 for 루프 page만 집중적으로 참조. 또는 어떤 함수를 구성하는 page만 집중 참조. 

 

Working-set: 이렇게 어떤 프로그램이 실행될 때 빈번히 참조되는, 집중되는 set을 working set이라고 함. 적어도 메모리에 한 번에 다 같이 올라와야지 page fault가 발생하지 않음.

만약 working-set이 5개가 필요한데 3개의 공간만 확보받을 수 있다면, 차라리 3개의 공간을 모두 반납해버림(thrashing 발생을 막기 위해)

 

Working-set: 과거를 참조해서 결정. 

시점 t1으로부터 델타만큼의 시간을 window size로 구성해서, 델타 시간 내에 존재하는 page들을 working-set으로 설정. 이 크기는 때마다 다름. 

특정 프로세스를 올릴 때 working-set이 보장되지 않으면, 차라리 자원을 반납하고 남은 프로세스라도 working-set을 보장받을 수 있게 해 줌.

---

직접 page fault rate를 파악. 만약 해당 프로그램이 page fault를 많이 일으키고 있다면 page를 더 할당해줌

page fualt 발생 비율이 너무 높다면 page를 더욱 할당,

page fault 발생 비율이 lower bound보다 낮다면 메모리를 빼앗음

빈 frame이 없다면 일부 프로세스 자체를 swap out 시켜서 남은 프로세스들의 원활한 실행을 보장

 

---

page 크기는 보통 4KB. 

메모리 주소 공간 역시 page로 자름. 요즘엔 32bit에서 64bit로 증가. page 크기가 작으면 page table이 커져야 하는데 이는 낭비로 이어짐.

disk transfer -> head가 움직이는 seek 작업을 동반. 이게 시간이 많이 듬.

 

때문에 최근에는 4KB보다 큰 크기의 page를 사용하는 시스템도 등장.