앞서 페이징에 대해 먼저 알고와야한다.
[컴퓨터(Computer Science)/운영체제(Operation System)] - Paging, 페이징, 불연속 메모리 할당 [운영체제]
Virtual Memory란 별 거 아니다.
진짜 가상메모리다.
가상 메모리는 실제 물리 메모리 개념과 개발자의 논리 메모리 개념을 분리한 것이다.
가상 주소 공간은 그 프로세스가 메모리에 저장되는 논리적인 형태를 말한다.
이런 아이디어는 여기서 나왔다.
만약 프로그램을 일부만 올려놓고도 실행할 수 있게 된다면??
**실제로 프로그램이 실행될 때 모든 부분이 실행되지 않는다.
1. 프로그램은 물리 메모리 크기에 의해 더는 제약을 받지 않는다.
** 즉, 큰 가상 주소 공간을 가정하고 프로그램을 만든다
2. 각 프로그램이 더 작은 메모리를 차지하므로 더 많은 프로그램을 동시에 수행할 수 있다.
// 응답시간은 같으면서 CPU이용률, Utilization과 처리량, throughput 이 올라간다.
//Multiprogramming이 효율이 좋아진다.
3. 프로그램을 메모리에 올리고 스왑하는데 필요한 I/O 횟수가 줄어든다.
//빠른 실행을 할 수 있다.
Virtual memory can be implemented via Demand paging
우선 Demand paging로 시작한다.
요청을 받고 page 를 메모리에 올리는 것이다.
메모리는 그림처럼 일반적으로 연속적인 공간을 차지하는게 보통이다.
물리 메모리는 페이지 프레임(page frame)으로 구성되고
프로세스에 할당된 페이지들이 실제적으로는 연속적인 것들이 아닐 수 있다.
프로세스가 실행될 때 모두 메모리에 적재해서 실행하는 것이 아니라
필요한 것을 요청받아서 메모리에 올려서 실행한다.
(실제로 프로그램 안에는 많이 쓰이는 코드가 있고 특정 경우에만 쓰이는 코드가 있어 이런 방식이 효율적이다)
아래 4가지 장점이 생긴다.
** page table은 초기화일 때 invalid 값을 가진다.
맨 오른쪽은 backing store로써 바로 사용되지 않을 페이지들은 내려가있다.
필요할 때 스와핑, swapping을 통해 올라온다.
예를 들어 invalid 한 page table에 접근했다면 해당 페이지를 물리적 메모리에 올려야 한다.
invalid page에 접근하는 것을 page fault라고 한다.
아래 page fault의 과정이 있다.
중요한 것은
빈 프레임이 있다면 바로 할당이 가능하지만
꽉 차있다면 이제 page replacement에 대한 고려를 해야한다.
아래 그림으로 보면 더욱 쉽게 이해가 간다.
1. 프로세스에 대한 내부 테이블(interanl table) 을 검사해서 그 메모리 참조가 유효인지 무효인지 알아낸다.
2. 무효한 페이지를 참조하려고 하는 것이면 프로세스는 중단된다. 만약 유효하지만 아직 메모리에 올라오지 않은 것이라면 그것을 보조 저장장치로부터 가져와야 한다.
3. 빈 공간, 즉 가용 프레임(free frame)을 찾는다
4. 보조 저장장치에 새로 할당된 프레임으로 해당 페이지를 읽어 들이도록 요청한다.
5. 보조 저장장치 읽기가 끝나면, 이 페이지가 이제는 메모리에 있다는 것을 알리기 위해
페이지 테이블을 갱신하며, 프로세스가 유지하고 있는 내부 테이블을 수정한다.
6. 트랩에 의해 중단되었던 명령어를 다시 수행한다.
//프로세스는 마치 그 페이지가 있던 것처럼 다시 접근을 시도한다.
줄여 말하면
page를 참조하여 CPU가 연산을 하기위해 page table을 접근하는데 해당 페이지가 invalid 하다면
trap이 걸려 OS가 CPU 제어를 하게 되고
Disk 에서 해당 페이지를 물리적 메모리에 올린다.
**Disk 에 접근하는 것은 시간적 오버헤드가 무척 크기때문에 page fault rate를 낮추는 것이 중요해졌다.
page fault가 일어나서 빈 프레임이 없을 경우(물리적 메모리 공간이 없을 경우)
page가 교체가 일어나는데 많은 교체 알고리즘이 있다.
그러한 알고리즘은 page fault를 낮추는 방향으로 이루어져야 한다.
그리고 최적화 하기 위해선
몇 가지 염두해 두어야 할 것들이 여기 있다.
그 다음에는 더 알아야할 것들이 있다. // 참고만 하자
바로 가용 프레임 리스트(Free frame list)라는 것이다.
page fault가 발생하면 운영체제는 요청된 페이지를 보조 저장장치에서 메인 메모리로 가져와야 한다.
페이지 폴트를 해결하기 위해 대부분의 운영체제는 이러한 요청을 충족시키기 위해 사용하기 위한 가용 프레임의 풀인 가용 프레임 리스트를 유지한다.
시스템이 시작되면 모든 가용 메모리가 가용 프레임 리스트에 넣어지고
가용 프레임이 요청되면 가용 프레임 리스트의 크기가 줄어든다.
예를 하나 들어보자
전체 10 페이지 중 실제 5페이지만 사용하는 프로세스가 있다면 , 요구 페이징을 통해 전혀 사용되지 않을 5페이지를 적재하는 데 필요한 I/O를 피할 수 있다.
그렇게 하면 다중 프로그래밍 정도를 늘려서 프로세스 수를 늘릴 수도 있다.
그렇지만 다중 프로그래밍 정도를 더 올리면 메모리 과할당(over-allocating)이 발생한다.
40개의 프레임이 있다고 하자 // 프레임은 물리 메모리를 뜻한다.
앞서 말했던 프로그램이 10페이지가 필요하지만 실제로 5페이지만 사용된다고 했다.
그래서 원래라면 4개 프로세스만 올라갈 수 있는데
늘리면 8개까지 할당할 수 있다는 것이다.
**그렇지만 10페이지짜리를 항상 5페이지만 쓴다면 10페이지 짜리로 만들리가 없다.
다시 말하면 언젠가 5페이지 이상을 쓸 때가 있는 것이다.
시스템 메모리는 프로그램 페이지를 저장하는 용도로만 사용되는 것이 아니다.
I/O 를 위한 버퍼도 상당한 양의 메모리를 사용하고, 이는 메모리 할당 알고리즘의 부담을 증가시킨다.
얼마만큼의 메모리를 I/O로 할당하고 얼마만큼의 메모리를 프로그램에 할당하느냐? 의 문제는 중요하다.
//쉽게 말하자면 10개중 5개 쓴다고 무식하게 다 넣으면 안된다는 것이다.
메모리 초과할당은 이렇게 된다.
프로세스가 실행되는 동안 페이지 폴트가 발생한다.
운영체제는 필요로 하는 페이지가 보조 저장장치에 저장된 위치를 알아내지만 가용한 프레임 목록에 가용한 프레임이 없음을 발견한다.
모든 메모리가 사용 중이라는 것이다.
운영체제는 ? 상황에서 여러가지 선택이 가능하다.
1. 프로세스 종료
2. 표준 스와핑 사용
3. 페이지 교체
우리는 여기서 page replacement를 알아보려고 한다.
만약 빈 프레임이 없다면, 즉 ? 상황일 때
현재 사용되고 있지 않는 프레임을 찾아서 거기를 비워버린다.
그 프레임의 내용을 스왑공간에 쓰고 그페이지가 메모리에 이제는 존재하지 않는다는 것을 나타내기 위해, 페이지 테이블을 변화시킴으로써 프레임을 비어 있게 한다.
1. 보조 저장장치에서 필요한 페이지의 위치를 찾는다.
2. 빈 페이지 프레임을 찾는다.
ㄱ. 비어 있는 프레임이 있다면 그 프레임 사용
ㄴ. 비어 있는 프레임 없으면 희생될(victim) 프레임 선정하기 위해서 페이지 교체 알고리즘 수행
ㄷ. 희생될 페이지를 보조저장장치에 기록, 관련 테이블 수정
3. 빼앗은 프레임에 새 페이지를 읽어오고 테이블 수정
4. 페이지 폴트가 발생한 지점에서부터 다시 프로세스 수행
역시 교체 시에는 해당 페이지가 Disk로 가기 때문에 해당 page number에 해당하는 bit를 invalid로 바꿔주고 내려가야 한다.
**만약 빈 프레임이 없는 경우에는 디스크를 2번 접근해야 한다
// 프레임을 비울 때 1번, 읽어 들일 때 1번 총 2번
그럼 해당 페이지가 교체되는 방법에 대해서 알아보자
페이징 시스템은 두 가지 중요한 문제를 해결해야 하는데
그것은 프레임 할당(frame allocation)알고리즘 과 페이지 교체(page replacement) 알고리즘이다.
++스케줄러처럼 어떻게 관리하느냐에 따라서 성능이 좌우된다.
여러 프로세스가 존재하는 경우 각 프로세스에 얼마나 많은 프레임을 할당해야 할지 결정해야한다.
그렇다면 여러 알고리즘 중 어떤 알고리즘을 쓰느냐가 중요하고 또한 이를 어떻게 평가하냐가 문제다.
**페이지 교체 알고리즘의 성능은 특정 메모리 참조 나열에 대해 알고리즘을 적용하여 페이지 폴트 발생 횟수를 계산하여 평가한다.
위 내용을 바탕으로 단적인 예를 들어보자
먼저 페이지 크기가 주어졌을 때 // 일반적으로 시스템이나 하드웨어 때문에 정해져 있다.
주소 전체를 고려하지 말고 페이지 번호만 고려하면 된다.
다음으로 페이지 p에 대한 참조가 발생하면, 참조 직후에 p에 접근하는 모든 참조는 페이지 폴트를 발생시키지 않는다.
첫 번째 참조 후에는 페이지가 메모리 상에 존재할 것이므로 오류를 발생시키지는 않을 것이다.
설명을 더하자면
특정 프로세스를 추적해서 주소열을 얻었다.
페이지 크기가 100바이트라면 이렇게 줄일 수 있다.
page fault 횟수를 알고자 하면 페이지 교체 알고리즘 외에도 이 프로세스가 현재 사용할 수 있는 페이지 프레임의 수를 알 필요가 있다.
프레임의 수가 많으면 페이지 폴트 횟수가 감소할 것이다.
//위 참조열(reference string) 같은 경우 3개 이상의 프레임을 가지면 각 페이지의 첫 번째 참조때마다 한번씩, 3번의 페이지 폴트만 발생한다.
++1,4,6, 말하는 거다.
++만약 프레임이 한개면 참조 때마다 부재가 발생할 것이다.
// 같은 페이지를 연속적으로 요구하지 않으니 자꾸 원하는 페이지가 프레임에 올라와 있을리가 없다.
추가 설명은 그림으로 하겠다.
가용 페이지 수와 페이지 폴트의 상관관계다.
이제 알고리즘에 대해서 알아보자
이론적으로는 Optimal Algorithm이 역시 최적이다.
//Belady 모순을 극복한다. (아래 설명이 있다)
최적의 핵심을 요약하자면
"앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체하자."
"Replace page that will not be used for longest period of time"
언제 page 가 참조될 지를 안다고 가정하면 이것이 최적이 되겠다.
이 알고리즘은 할당된 프레임 수가 고정된 경우 가장 낮은 페이지 폴트율을 보장한다.
//보장까지 한다고 한다. 굿굿
하지만 실제로는 알 수가 없기에 Offline algorithm이라고 한다.
**실제로 이렇게 이루어지지는 않고 예측으로 비슷하게 구현이 되고
이 알고리즘은 항상 최적이라고 보장되어있으니 다른 알고리즘과 비교할 때 많이 쓴다.
역시 가장 간단한 알고리즘은 Queue와 같은 FIFO
간단한 만큼 성능은 구리다.
어떤 페이지를 교체할 때 메모리에 가장 오래된 페이지를 빼는 것이다.
교체된 페이지가 계속해서 자주 사용되는 변수를 포함하는 경우
자꾸 왔다 갔다 하니까 페이지 폴트도 더 많이 날 수 있다.
보기엔 좋아보이는데 왜 안 좋다고 하는지 이해가 가지 않을 수 있는데 그럼 예를 통해 보자
??? 아직 잘 모르겠다고??
분명 아까 보여준 그래프에서는 프레임이 늘면 폴트가 줄어들었는데
프레임이 3개일 때가 4개일 때보다 성능이 좋은 경우가 발생했다.
// 해보면 안다.
이 현상을 belady의 모순 : Belady's anomaly 라고 하는데
프로세스에 프레임을 더 주었는데 오히려 페이지 폴트율이 올라가는 현상을 말한다.
다음은 LRU 알고리즘이다.
그나마 지역성을 이용한, time locality를 이용한 ,
최근에 쓰인 페이지는 최근에 다시 쓰일 거라는 가정이 들어있다.
현재 쓰고있는 알고리즘이다.
Latest Recently Used , 사용한 것중에 가장 오래된 것을 교체하겠다는 말이다.
괜찮은 성능을 보이고 있다.
최근의 과거를 가까운 미래의 근사치로 본다면 가장 오랜 기간 동안 사용되지 않은 페이지를 교체할 수 있다.
이 방법은 미래를 알고있다는 가정이 아닌 이미 읽은, 과거를 적용해서 페이지 교체를 하는 것이다.
**여기선 페이지가 얼마나 됐는지를 확인해야하므로 우리가 생각할 땐 다른 정보를 더해야한다.
하지만 LRU의 구현은 Linked List로 구현이 되고 페이지가 참조될 때마다 해당 리스트의 뒤에 추가시키고
맨 앞의 것(오래된 것)만 빼낸다고 하면 시간복잡도를 낮출 수 있다.
LRU도 문제인게 어떻게 구현하느냐이다.
무엇으로 미래를 예측할 것이냐??? 과거를 어떻게 적용할 것이냐???
일반적으로 2가지 방법이 있다.
1. 계수기(counter)이용
2. 스택(stack) 이용
1. 계수기 이용부터 보자면
각 페이지 항목마다 사용시간 필드를 넣어서 CPU에 논리적인 시계나 계수기를 추가하는 것이다.
마지막 참조 시간으로 오래된 것들을 예측한다.
2. 스택 이용을 보자
페이지 번호의 스택을 유지하는 방법이다.
페이지가 참조될 때마다 페이지 번호는 스택 중간에서 제거되어 스택 꼭대기에 놓이게 된다.
그렇다면 스택의 꼭대기에는 항상 가장 최근에 사용된 페이지가 올라가고
밑바닥에는 가장 오랫동안 이용되지 않은 페이지일 것이다.
하지만 스택의 구현을 배열로 하는 것이 아닌
doubly linked list로 구현한다.
++ 스택의 중간에서 포인터를 바꿔야할 수도 있으므로 그렇게 해야한다.
어떤 페이지를 참조해서 그것을 스택의 중간에서 꼭대기로 옮기는 것은 조금 비효율적이라고 생각될 수 있지만
만약 페이지 교체가 일어날 경우 맨 아래만 확인해서 빼면 되니까 그 경우는 괜찮은 방법이다.
얘 또한 Belady 의 모순이 발생하지 않는다.
다음 알고리즘은 Least Frequently Used
가장 적게 쓰인 페이지를 쫓아내겠다는 말이다.
참조횟수를 알아야 하므로 페이지에 정보가 추가되어야 한다.
LFU에서 참조횟수를 찾을 때는 이진탐색으로 찾아서 시간복잡도를 낮춘다.
Tree구조로 자식이 참조횟수가 많게 구현한다.
root node를 없애고 tree를 정리하는데에 log n 시간이 걸리겠다.
위의 2개를 비교해보자면
아래 그림을 보고 이해해보자
위에서 말했듯이 알고리즘의 구현은 아래와 같이 한다.
보충 내용은 아래를 보면 된다.
메모리 계층적, 메모리 특성을 이용하여 성능을 높이는 것이다.
page fault의 경우 trap이 발생하여 OS가 제어하게 되는데
replacement algorithm이 제대로 구현되지 않으면 캐시라고 할 수 없게 된다.
하지만 위에서 말했지만
실제로 page fault가 일어나고 trap 이 걸려서 OS가 제어를 얻게 된다면
언제 참조했는지, 몇 번을 참조했는지 OS가 알 수가 없다.
그래서 실제로는 다른 도움없이 OS가 알아낼 수 있는 방법이 없어서 적용을 할 수 없다.
위의 설명에서 나와있듯이
page 가 이미 메모리에 올라와 있다면 해당 참조 시각 등의 정보를 OS가 알 수 없다.
LRU에 대한 List 업데이트도 안된다는 것이다.
그래서 다른 알고리즘을 만들어냈다.
Clock Algorithm이다. 최근에 사용되지 않은 것들을 교체 대상으로 정하는 방법이다.
**시계처럼 작동해서 이름이 그렇게 되었다.
예를 들어 아래 시계같은 것을 보자
각 사각형은 페이지를 의미한다.
이미 메모리에 존재하는 페이지를 참조한다면 reference bit 을 1로 두게된다.
시계를 돌면서 1을 만나면 해당 페이지의 bit를 0으로 바꾸고 다음 것을 조사한다.
0을 만나게 되면 0인 해당 페이지가 교체 대상이 된다.
하드웨어의 도움을 받아 reference bit을 만들어내고 LRU와 비슷하게 동작하게 되는 것이다.
**modified bit이라는 비트도 있는데 해당 페이지가 read가 아닌 write로 접근될 수도 있어서 그렇다.
backing store에 수정 내용을 반영해야하기 때문에 있다.
그렇다면 프로세스에 프레임(물리적 메모리)를 할당하는 방법은 뭘까?
필요한 것만 올린다며.. 그게 얼만큼일까??
즉, 얼마만큼 프레임을 써야 해당 프로세스가 문제없이 작동하는 것일까?
예를 들어 프레임을 10개만 준다고 치면 만약 11개가 동시에 쓰여야 할 때 오류가 날 것이다.
100개를 준다고 하고 최대 10개만 쓰면 90개가 낭비된다.
** 특정 프로세스가 다른 프로세스의 페이지까지 쫓아내버리면 안되니까! 정해주어야 한다.
각각의 프로그램에게 미리 할당해주는 것이 중요해졌다.
3가지 방법이 있다.
1. 균등 할당 : 프로그램마다 격차가 크기 때문에 별로다.
2. 비례 할당 : 부팅 시간에만 많이 필요한 프로그램의 경우가 있다.
3. 우선순위 할당 : 페이지 우선순위에 의한 할당
물론 따로 할당해주지 않아도 Global Replacement같은 OS가 능동적으로 조절하여 정상적으로 작동할 수 있지만
할당을 하게 된다면 Replacement는 Local에서만 일어나게 된다.
**Global -> 다른 프로세스의 페이지 관여 가능
하지만 할당을 잘못할 경우 아래 상황이 발생한다.
예상보다 fault가 많이나 성능이 현저하게 떨어지는 것을 말한다.
** 현저하게다. 그냥 떨어지는 것이 아니라 눈에 띄게
다중 프로그래밍 정도가 높아지면
프로세스가 점유할 수 있는 절대적인 프레임이 어쩔 수 없이 줄어들게 되고
성능이 현저히 저하하는 시점이 오게되는 것이다.
그럼 결국 모든 프로세스가 성능이 저하가 된다.
그래서 해당 문제를 해결하기 위한 방법을 또 찾아냈다
지역성을 이용하고, Working-set이라는 것을 정의하여
프로세스가 실행하는데 최소한의 페이지 집합을 올려놓는 것을 보장해야 한다.
만약 이것이 안된다?
그렇다면 되는 것만이라도 받는 것이 아니라 그냥 모두 반납해버린다.
(프로세스 종료와 마찬가지)
그렇다면 해당 페이지 집합인 Working Set을 어떻게 아느냐??
바로 알 수는 없다. 실행을 통해 알아내는데
Window를 만들어 Working Set을 만들어내는 근거를 만들고 Working-set을 만들어낸다.
하지만 Working Set은 고정된 것이아니다.
시간이 흐르면서 Working Set도 바뀌는데
이는 일정 시간만 참조를 유지한다고 생각하면 된다.
(Window 크기만큼이겠다.)
역시나 Trade-off 관계다.
Working Set이 너무 크면 역시나 프레임을 점유하는 부분이 많아질 것이고
적어도 지역성을 활용하지 못해서 오버헤드가 커질 수 있다.
page fault rate에 따라 frame을 더 주거나 빼앗거나하는 그러한 전략이다.
이 역시도 해당 프로세스가 frame이 더 필요할 때 줄 frame이 없다면 최대한 주는 것이 아닌
해당 프로세스의 페이지를 모두 빼버리는, Swap out 하는 조치를 취한다.
역시 페이지 사이즈도 결국 trade-off 다.
하드웨어가 결정하지만.. 아래의 상황이 발생한다.
너무 작아도... 너무 커도 비효율이 발생한다.
하지만 요즘 트렌드는 Larger라는 것을 보아하니
시간보다 공간을 쓰는 것이 낫다고 생각하는 추세이다.
'컴퓨터(Computer Science) > 운영체제(Operation System)' 카테고리의 다른 글
| File System, 파일 시스템 [운영체제] (0) | 2020.06.10 |
|---|---|
| 운영체제에서 스와핑(Swapping) (0) | 2020.06.10 |
| Paging, 페이징, 불연속 메모리 할당 [운영체제] (0) | 2020.06.08 |
| Memory Management, 메모리 할당 방식 [운영체제] (0) | 2020.06.06 |
| 동기화를 위한 하드웨어 지원, Hardware Support for Synchronization (0) | 2020.06.04 |