Page Replacement
배경
- 프로세스 수 증가에 따라 메모리 과다 할당 상태 발생
- 모든 프로세스가 상하는 페이지수보다 물리 메모리의 프레임 수가 적은 상황..
- 페이지 Fault로 새로운 페이지를 데리고 올때를 처리하기 위해
Page Replacement란
- 물리 메모리에 위치한 페이지를 디스크에 저장하고, 요구된 페이지가 해당 프레임을 할당 받도록 하는 방법
과정
1. 디스크에서 요구된 페이지의 위치를 찾는다(평소하던대로)
2. 물리 메모리에서 Free Frame을 찾는다.
2-1. 비어있는 프레임이 있으면 사용
2-2. 없으면 Page Replacement 알고리즘을 사용하여 교체할 프레임을 선택한다
3. 교체할 프레임을 디스크에 저장하고, 페이지 테이블을 변경한다 (기존꺼 쫓아내고 저장)
4. 요구된 페이지를 2에서 선택된 Free Frame으로 읽어들이고 해당 페이지 테이블을 변경한다.
5. 원래 실행중이던거 재시작
Page Replacement 고려사항
- 각각의 유저 프로세스에게 어떻게 프레임을 분배해 줄 것인가?
페이지 replacement Algorithm
- 페이지 교체가 필요할 때 어떻게 교체할 페이지를 고를건지?
=> 페이지 replacement 는 I/O 오퍼레이션이 발생함 -> 성능저하
=> 따라서 page replacement를 최소화하도록 알고리즘 짜야해
Optimal 알고리즘
- 앞으로 가장 오랫동안 사용되지 않을 페이지부터 먼저 교체
FIFO 알고리즘
- 먼저 들어온 프레임을 먼저 교체 (=temporal locality 고려함)
- 가장 단순함
- 멀티미디어 데이터에서는 주목받음 (=동영상 장면에서는 한번쓴 장면을 또 쓰는 일이 거의 없거든)
SCR(Second Chance Replacement) 알고리즘
- FIFO의 단점을 보완(한번 안쓰였다고 바로 추방은 너무하기때문에 보완)
- FIFO를 만들고 사용하되 참조 Bit를 두어 페이지를 관리
=> 최초로 프레임에 로드 될 때, 참조가 되었을 때 마다 1로 바꿔줌.
- '일정 주기'마다 다시 0으로 리셋됨.
=> Bit가 1이면 최근에 사용된것임으로 안쫓아내고 0인 애들만 쫓아냄
Clock 알고리즘
- SCR의 발전형태(일정 주기 라는걸 구체적으로 구현)
- 페이지 수에 따라서 시간을 달라져야한다
=> 페이지 수에 따라 달라지는 원형 큐 만듬 - But 아직까지 최적의 알고리즘은 아님
LFU(Least Frequently Used) 알고리즘
- FIFO 보다는 locality를 고려했음
- 사용 빈도가 가장 적은 페이지를 교체하는 기법
단점
- 처음에만 사용되고 뒤에서는 사용안되는 애들이 있는데 토탈 참조 숫자를 기준으로 하는건 최적이 아님..
NRU(Not Recently Used) 알고리즘
- LFU의 대안
- 최근에 사용되지 않은 페이지를 교체하는 기법
- 페이지마다 참조 Bit와 변형 Bit을 두어서 관리한다
참조 Bit
- 참조될때마다 1로 set하고 일정 주기마다 다시 0으로
변형 Bit
-
로드 되면 0
-
실제로 바뀔 때 1로
-
아직도 optimal에 거리가 멈
LRU(Least Recently Used)
- 가장 오랜 시간 참조되지 않은 페이지부터 먼저 교체함
- 페이지 사용의 Locality(지역성)을 고려하여 Optimal 알고리즘이 되려고함
구현방법
- Counter로 참조된 시간을 기록
- Queue로 한번 사용한 페이지를 큐의 가장 위로 이동시킴
-가장 위의 페이지: 가장 최근에 사용된거
- 가장 아래 페이지: 가장 오래전에 사용된거
LRU 알고리즘이 지금까지는 젤 좋기로 쓰임
Swapping
- Page Out으로 메모리 부족을 해결하지 못할때
- 대상이된 프로세스 전체를 Secondary Storage로 쫓아냄
- 새로운 프로세스가 들어왔을때 프로세스 단위로 걍 보내버림
Contiguous Memory Allocation
- 어떻게 각 프로세스에게 프레임을 할당할 것인가?
Single 파티션 할당
- 단순하게 메모리 사용
한번에 하나의 프로그램만 올라가 사용하기 때문에 메모리 전체를 하나의 프로그램으로
Multiple 파티션 할당
- 메모리에 프로그램 한번에 여러개 올려놓고 사용하자
단점
- 파티션으로 나누게 되면 비어 있는 공간 활용하면 하나 더 넣을 수 있는데 못넣음
No 파티션
- 각 프로그램 필요에 따라 전체를 사용할 수도 있고 사용안할 수도 있음.
- 페이지 Page/Swap Out 시에 다 챙겨서 떠나야하기 때문에 Garbage collection이 크다
Fragmentation
External Fragmentation
- 프로그램에게 할당 후 남은 메모리의 총 공간은 넉넉한데, 이게 연속적이지 않아서 사용할 수 없는 경우 => 아무 위치에나 박을 수 있는 NO 파티션이 해결방안
Internal Fragmentation
- 페이지 내에서 또 fragmentation 문제가 발생하는것
- 페이지 프레임은 4KB로 고정되어있지만, 4KB를 전부 사용하지 않는 경우에 Fragmentation이 발생. => But External 보다 훨 미미해서 이정도 낭비는 그냥 Flex로 넘어가~
Protection과 Relocation
Protection
- OS의 메모리 영역과 유저 프로그램의 메모리 역역, 서로의 영역을 침범하지 못하도록 보호해야함
Relocation
- 유저 프로그램은 재배치 가능한 주소로 표현되어야함 ->위치가 바뀌더라도 잘 실행될 수 있어야하기 때문
