[Virtual Memory] Frame management

일부 시스템이서 가상 메모리(virtual memory)를 제공하기 위해 연결 리스트를 사용한다. 

가상 메모리는 프로세스가 실제 메모리에 있지 않은 상태에서도 수행될 수 있게 하는 주소 공간 매핑이다.

가상 메모리의 장점 중 하나는 프로세스가 실제 메모리보다 큰 주소 공간을 사용할 수 있게 해준다는 점이다. 또 여러 프로세스들이 동시에 실행되면서 메모리를 공유할 수 있다는 점이다.

가상 메모리에서 실행되는 프로세스는 가상 주소(Virtual address)를 사용한다. 가상주소는 프로세스에게 실제 주소(physical address)처럼 보이지만 사용하기 전에 시스템이 변환해 주어야하는 것이다.

주소변환은 페이지 테이블을 사용하는데 전용 하드웨어를 사용하므로 속도가 빠르다.

각 프로세스는 가상 주소 공간의 페이지와 셀제 메모리의 프레임을 매핑시켜 주는 페이지 테이블을 갖는다.

프로세스가 특정 가상 주소를 참조할 때 실제 어느 프레임에 이 페이지가 존재하는지를 결정하기 위해서 페이지 페이블의 해당 항목을 조사한다.

프로세스가 프레임에 없는 가상 주소를 참조하면 페이지 오류가 발생하면서 프레임이 실제 메모리에 할당된다. 프로세스의 페이지들이 왜 실제 메모리에서 제거되는지는 다른 문제이다. 페이지 제거의 한 이유는 다른 페이지들에 비해 드물게 접근되고 해당 프레임을 다른 페이지가 필요로하는 경우이다.

두 함수 alloc_frame, free_frame이 할당될 수 있는 프레임을 관리하기 위해 연결리스트를 사용한다. alloc_frame 함수는 사용가능한 프레임의 리스트에서 하나의 사용가능한 프레임의 번호를 얻는다.

특정 페이지에 대해 어느 프레임에 이 페이지가 존재하는지를 나타내기 위해 이 번호를 페이지 테이블에 넣는다.

free_frame 함수는 실제 메모리에서 페이지가 삭제될 때 프레임 번호를 전달받아 사용가능한 프레임의 리스트에 다시 넣는다.

두 함수가 호출되기 전에 운영체제가 사용가능한 프레임들을 모두 이 리스트에 넣는다고 가정한다.

프레임 할당은 빈번한 삽입과 삭제를 수반하고 삽입과 삭제가 리스트의 head에서 수행되므로 연결 리스트는 프레임을 관리하는 좋은 방법이다. alloc_Frame과 free_Frame의 실행 시간 복잡도는 각각 복잡도가 O(1)인 list_rem_next와 list_ins_next를 단순하게 호출하므로 O(1)이다.

[참조] Algorithms in C