CPU는 우리가 작성한 코드를 바로 이해해서 읽지 못함.
우리가 작성한 코드를 컴파일러를 이용해서 010101과 같은 형태로 바꾸어주어야 이해하고 읽을 수 있음.
이때 내가 SomeString이라는 코드를 썻다면 SomeString을
Symbolic Address라고 하고 이를 컴파일러를 통해
010101과 같은 이진법의 숫자형태로 바꾼것을 Logical Address(논리주소)라고함.
A라는 프로그램과 B라는 프로그램이 있다고 치자.
이 두프로그램의 코드 주소는 어떻게 정해질까?
A라는 프로그램의 코드들의 주소가 0번부터 19번까지
B라는 프로그램의 코드들의 주소가 20 ~ 39로 정해 지는 것이 아니라
둘다 0 ~ 19로 정해진다. 각각 프로그램마다 중복되는 논리 주소를 가지고 있다는 것이다.!!!
그래서 논리 주소를 가상주소라고도 부름.
그럼 같은 주소를 썼는데 어떻게 구분하냐?>
이 논리 주소앞에 하나의 주소가 더 더해진다.
Ex) A:0200 … 0219 B:0400 … 0419
이를 Physical Address(물리주소)라고 함.
그럼 Symbolic Address에서 왜 바로 Physical Address로 바꾸지 않냐?
CPU는 논리주소만 읽을 수 있고 현재 실행중인 프로세서의 내부 주소만 알면되지 어떤 프로세서인지는 알 필요도 알수도 없기 때문이다.
어떤 프로세스인지도 모르는데 어떻게 정보를 읽는게 가능함?
MMU(Memory Managment Unit)이 도와주기 때문!
MMU는 시작주소인 Base register와 마지막 주소를 가진 LImit register와 간단한 산술연산기를 가지고 있다.
CPU가 가지고있는 논리주소에 MMU가 가지고 있는 시작 주소를 더해서 물리주소를 만들수 있게 되고 이를 통해서 메모리에서 프로세스가 가진 정보를 정확히 찾을 수 있는 것.
Ex) CPU의 논리주소(16) + MMU의 Base register (0200) -> 0216
하지만 그전에 Limit register가 요구하는 물리주소가 적절한 프로세서의 주소인지 체크를함.
만약에 limt이 0219인데 0324물리주소에 있는 메모리를 읽으려고 하면 엉뚱한 프로그램의 정보를 가지고 오기 때문에 Limit register와의 비교가 선행된다.
만약, Limit register의 범위를 넘는 값을 요청하면 어떻게 되나?
Limit register의 범위를 넘는 값을 요청하게되면 CPU운영권한이 OS(운영체제)로 넘어가게 되고 만약 악의적인 접근일 경우 해당 프로세서를 멈춘다.
메모리에 프로그램이 할당된 모습은 항상 예쁘게 정렬이 되지 않는다.
메모리에 프로그램이 올라가고 내려갈때마다 틈을 만들수 있다.
이러한 틈들은 작을 수 있지만 모여서 큰 공간을 차지하게 되어 메모리를 낭비하게 만든다.
만약 이러한 틈들로 인해 당장에 급한 프로그램을 못올리게 된다면 큰 낭패를 볼것이다.
이때, 현재 올라가있는 프로그램중 하나를 하드디스크 영역의 Swap Area로 임시적으로 보내고 메모리에 프로그램을 할당하는 Swapping기법이 사용된다.
하지만, 이 Swapping기법은 메모리에서 하드디스크로 왔다 갔다하면서 시간이 많이 소요가 되고, 어떤 프로그램을 하드디스크로 보낼지 우선순위 정하는 것도 쉽지 않다.
결국, 이러한 문제를 해결하기 위해 프로그램을 조금씩 잘라서 올리기로 함.(Paging기법)
이를 실행하기 위해, 우선 물리적인 메모리를 동일한 크기로 자른다.
이 동일한 크기를 Frame이라고 함.
그리고 프로그램들을 Frame과 동일한 크기로 자른다 이를 Page라고 한다.
그 후 당장 필요한 page만 메모리에 올리고 나머지는 Swap Area에 둔다.
하지만 Paging기법은 여러 프로그램들의 페이지가 분산되고 순서가 헷갈리게 된다.
그렇기 때문에 MMU의 일이 많이 복잡해짐. => PageTable를 사용하게됨!
Base Register => Page Table Base Register
Limit Register => Page Table Length Register
CPU가 MMU에게 논리주소로 요청을 하게 되면 MMU에서 계산이 끝난 값으로 Page테이블을 참조해서
찾아낸 Frame주소로 이동해 해당 페이지의 정보를 가지고 옴.
PageTable이 저장된 곳은?
PageTable의 행의 개수는 해당 프로그램의 크기를 일정한 수로 나눈것
행의 갯수는 백만개 이상이 대다수.. 인데 이를 프로세스마다 하나씩 가지고 있으니 CPU는 안되고
하드디스크에 넣기에는 목적을 잃어버림. 따라서 메모리에 저장됨.
??메모리를 아끼려다가 메모리에다가 뭔가를 추가해 버림.
그럼, 공통된부분을 묶어서 메모리를 아껴보자!
프로세서끼리 공통된 부분을 Shareed Page를 선언. 절대 바뀌지 않고 Read Only임.
메모리는 아꼇으나 속도가 느려짐
Why? 페이지테이블도 메모리에, 페이지도 메모리에 있기 때문에 CPU가 메모리에 두번 접근해야함.
그래서! TLB(Translation Look-aside Buffers)라는 하드웨어의 추가 지원을 받게 된다.
CPU가 논리 주소로 정보를 요청하면, PageTable에 접근하기전 중간에 낀 TLB부터 확인한다.
그리고 만약 값이 있으면 TLB에서 바로 Frame주소로 변환하고 바로 CPU로 값을 준다.
없으면 어쩔수없이 전처럼 사용함.
하지만 대부분의 프로세서는 한번 참조한 곳을 다시 참조할 확률이 상당히 높다.
Before) CPU -> 메모리 -> CPU -> 메모리 -> CPU
after) CPU -> TLB -> 메모리 -> CPU
이 과정에서 리눅스(운영체제)의 역할?
- 가상 메모리로 사용자 프로세스 속이기
- I / O 장치 관리
CPU를 점유중인 프로세스들은 자신이 온전하게 메모리에 올라와있다고 생각한다.
그렇기 때문에 에러를 내지않고 정상적으로 작동을 할 수 있게 되는 것이다.
하지만 사실은 현재 동작에 필요한 부분만 물리메모리에 나머지는 Swap Area에 있다.
이렇게 물리메모리와 Swap Area를 합쳐서 만들어낸 공간을 가상 메모리라고 한다.
CPU가 논리주소를 요구하던것들이 사실 다 가상메모리 주소, 가상 주소였던 것이다!
주소를 변환하고 메모리에서 페이지를 찾아내는 것은 사용자 프로세서와 하드웨어의 영역이지만
하드디스크와 같은 입출력장치를 컨트롤 하는 것은 운영체제이다.
CPU가 TLB와 메모리에 없는 정보를 요구하게 된다면??
- MMU가 프로세스를 일시 정지시긴다(Page Fault)
- 운영체제가 CPU를 컨트롤하게 되고 프로세스가 정지된 이유를 살핀다(비정상 적이라면 STOP)
- 운영체제가 Swap공간에서 메모리로 필요한 page를 가지고 오고 TLB에 주소를 등록한다.
- PageTable에도 vaild값과 함께 업데이트 함.
- Swap Area에서 페이지를 가져오는 시간이 매우 길어서 중간에 다른 프로세서에게 CPU가 넘어갈 수 있다.
- 이경우에는 기존 프로세서는 자기 차례를 기다리는 대기 큐에 들어가게됨.
- 여기서 알수 있는 점은 Page Fault의 발생 빈도가 낮을 수록 성능이 좋다는것.
- 대부분 같은 곳을 다시 참조하는 특성이 있기 때문에 높은 확률롷 빠르게 처리할 수 있다.
Page Fault가 많이 발생해서 메모리에 더이상 page가 올라갈 Frame이 없다면 어떻게 되나?
기존 Frame을 차지한 Page중 하나를 내쫒는 데 이를 Page Replacement라고 한다.
그리고 어떤 Page를 비울지는 운영체제가 정하게 된다.
이때 LRU(마지막으로 참조된 시점이 가장 오래된) 알고리즘을 사용하면 좋겠지만
왜냐하면 그만큼 안쓰이고 있다는 거니까~~
하지만 운영체제는 자신이 pageFault를 관리했던 page들만 알고 있어서 사용할 수 없다.
대신! Clock Algorithm을 사용함
Clock Algorithm은 메모리에 올라와있는 page마다 한개의 reference bit를 갖게함.
비트가 1일경우 최근에 사용된 페이지, 0일경우 최근에 사용되지 않은 페이지.
비트를 바꾸는 건 주소변환을 담당하는 하드웨어가 담당함.
page fault가 발생하면 OS가 frame을 돌면서 쫒아낼 page를 찾는다.
쫒아낼 page를 찾는 중 가리킨 frame이 최근에 사용된 reference bit가 1이었다면 0으로 바꾸고 다음 frame이 page로 이동함. reference bit가 0인놈을 찾을떄 까지 반복하다가 해당 frame을 만나면 해당 frame의 페이지를 쫒아냄.
이 reference bit도 pageTable에 추가됨.
즉, Clock Algorithm은 운영체제가 하드웨어의 도움을 받는 알고리즘임.
- 가장 참조가 오래된 page는 찾지 못하지만 가장 최근에 참조된 page는 피할 수 있는 기법.
- 쫒아낼 page를 찾았다고해서 바로 쫒아내는 것이 아님.
- CPU를 점거하고 있는 프로그램으로부터 변경사항이 있는지 확인을 한 후에 변경사항이 있다면 하드디스크에도 변경사항을 반영해서 저장해야함.
프로세스가 점점더 많아져서 각 frame에 너무 다양한 page들이 있다면 한 프로세스 당 실행할수 있는 page가 점차 점차 줄어들 것이고 이는
page replacment가 계속해서 발생할 수 있는 환경을 제공하게됨.
모든 프로세스들이 page를 교체한느라 바쁜 와중 CPU는 상대적으로
여유로워짐.
이를 본 운영체제는 더 많은 프로세스를 올리게 되고 악순환이 시작됨.
이런 현상을 Thrashing이라고 한다.
- 쓰레싱이 발생하는 원인
- 멀티 프로그래밍 환경
- 해당 프로세서가 필요로 하는 최소 프레임 갯수 > 제공된 프레임 갯수
2번쨰 원인은 우리가 해결할 여지가 있으므로 알고리즘을 통해 시도함.
Locality Model
프로세스는 페이지마다 지역성을 가지고 있다는 아이디어
즉, Locality는 특정한 시점에서 프로세스가 실행하기 위한 page들의 집합이다.
Locality만큼 frame을 할당해주면 Thrashing을 막을 수 있다는 결론.
Thrashing현상을 해결하기 위해 운영체제는
WorkingSet
- 현 프로세스의 해당 시점으로부터, 과거의 Working set window 크기만큼의 instructions 를 보고, 얼마만큼의 페이지가 들어가있는지 확인한다.
- 이 페이지들의 집합을 Working set (WS)이라 하고, 이 크기를 Working set size (WSS)라고 한다.
따라서, OS들은 프로세서들의 WS를 모니터 하면서,WS를 충분히 수용할 수 있는 프레임을 할당한다.(할당되는 프레임 수는 매번 가변적일수 있음)
- 새 프로세스를 수용할 수 있을 만큼의 빈 프레임이 존재하면, 새 프로세스를 실행시킨다.
- 반대로, (모든 프로세스의 WSS의 합) > (실제 사용가능한 프레임 수) 일 경우, 하나의 프로세스를 일시 중단한다.
PFF(Page-Fault Frequency)
Page-falut rate의 상한값과 하한값을 두고
상한값을 넘으면 frame을 뻇어온다
하한값보다 낮아지면 frame이 더 필요한것이니 frame을 늘린다.
출처 및 참고:
https://dailyheumsi.tistory.com/139 - working set알고리즘
https://kouzie.github.io/operatingsystem/%EA%B0%80%EC%83%81%EB%A9%94%EB%AA%A8%EB%A6%AC/#clock-algorithm Clock - Algorithm
http://egloos.zum.com/sweeper/v/2988646 - dirty bit
댓글