09. Segmentation

충남대학교 컴퓨터공학과 류재철 교수님의 "운영체제 및 실습" 강의를 필기한 내용입니다.

다소 잘못된 내용과 구어적 표현 이 포함되어 있을 수 있습니다.

Segmentation §

Segmentation 의 장단점 §

• 우선 장점은 모듈 단위로 끊기 때문에 모듈의 protection과 data shraing이 잘된다는 거고
• 단점은 이제 external fragmentation이 발생한다는 것과 이것을 최소화하는 것이 힘들다는 것이다

Address Translation §

• 이전에도 한번 설명한거같은데
• 일단 Seg# 를 인덱스로 하고 Seg Table Ptr을 이용해 테이블에 접근하고
• 거기서 Base는 Segment의 시작주소가 담겨있으므로 이거에 offset을 더하면 된다
• 그리고 Length는 Segment의 길이로 offset은 이것보다 커서는 안된다
• Paging과 Segmentation의 Address Translation 차이점을 잘 기억해라

Segmentation Paging §

• 그래서 보통은 Segmentation과 Paging을 섞은 Segmentation Paging을 사용한다
• 얘는 Module단위로 Segment으로 나뉘긴 하는데 이 각각의 Segment들은 일정한 크기의 Page로 나뉘는 것
• 따라서 Logical address도 ( Seg# - Page# - offset ) 순서로 구성된다

Address Translation §

• 보면 이제 일단 Seg Table Ptr를 이용해 테이블에 접근하고 Seg# 를 인덱스로 해서 해당 원소에 접근한다
• 근데 여기서 중요한 것은 Seg# 를 인덱스로 한 곳에는 Page Table의 주소가 들어있다. 즉, Segment table은 Process마다 하나씩 갖지만 Page Table은 Segment마다 하나씩 갖게 된다
• 그렇게 Page table로 접근해 Page# 를 인덱스로 해서 frame# 을 알아낸다
• 그리고 offset앞에 frame# 을 딱 붙여주기만 하면 변환이 마무리되는 것

• 따라서 주소와 테이블 인스턴스는 저렇게 구성된다
• 아까 말한것처럼 Segment Base에 Page Table의 시작주소가 들어가게 되는 것
• 그리고 Page Table도 기존처럼 변경 유무를 저장해 replacement를 쉽게 하는 등의 기능들을 지원하기 위해 Pbit와 Mbit같은 Control Bits가 존재한다

OS Policies for Virtual Memory §

• 아래의 용어들을 다 알아야된다

Fetch Policy §

• Fetch Policy : 언제 페이지를 하드에서부터 갖고올 것이냐
• Demand Paging : 요구가 있을때 갖고옴. 즉, 참조를 할때 그제서야 갖고오는 정책
  • 당연히 메모리는 적게먹는다. 하지만 Page fault가 많이 일어나게 되는 단점이 있다
• Prepaging : 하드에서 갖고올때 걔만갖고오는게 아니고 다음에 쓸거같은애들도 같이 갖고 옴
  • 예를들면 page# 1 을 가져올때 page# 2도 나중에 쓰게될 확률이 높으므로 얘도 같이 가져오는 것
  • 메모리는 좀 더 먹지만 page fault가 적게 일어난다는 장점이 있다
  • 따라서 오늘날 주로 쓰이는 OS정책임

Placement Policy §

• Placement Policy : best fit 같은애들. segment를 빈공간 어디에 적재할 것인가
• 당연히 paging기법을 사용하면 이런거를 고민할일이 없기 때문에 요즘은 별로 중요하지 않은 정책이다

Replacement Policy §

• Replacement Policy : Page fault가 일어났을 때 어떤애를 선택하여 아래로 내려보낼 것인가 - 교체대상 선정
• Frame Lock : 커널같은 중요한 프로세스들은 하드로 내려가면 안되기 때문에 lock을 걸어서 replacement 대상에서 제외하는 것

• Replacement Algorithm 예시 - 이거 시험문제 나온다 - 어떤 알고리즘을 선택했을때 앞에서 배운 Anomaly(이상현상)이 일어나는지 생각해볼것 - 정 모르겠으면 구글링해서 찾아봐라 - 안알려주노 ㅅㅂ
• 위에 나열돼있는 숫자들이 요청된 페이지 번호, 그리고 그 아래가 프로세스에 할당된 프레임의 모습이다 - 3개로 일정하고 자신의 프로세스 내에 있는 페이지를 버리므로 local이라고 할 수 있다 - 예시에서는 초기에 적재되는 page fault는 무시하고 page fault가 일어나 replace가 일어나야되는 것만 카운트했다
  • OPT(Optimal) : Replacement가 일어났을 때 미래의 페이지 사용을 보고 안쓰이거나 가장 나중에 쓰이는 (혹은 가장 최근에 사용된 - 가장 최근에 사용된 놈은 다시 사용할 가능성이 비교적 낮다고 판단)페이지를 내려보낸다 - 당연히 미래의 일을 알아야되므로 구현이 불가능 하며 다른 알고리즘과의 비교를 위해 존재하는 것이다 - 위의 예시에서는 3번의 Fault가 일어나며 제일 좋은 성능을 보여주지만
  • LRU(Least Recently Use) : 제일 오래전에 사용된 놈을 버리는 구조
  • FIFO(First In First Out) : 이건 뭔지알제? 제일 먼저 들어온놈이 먼저 나가는 구조 - 얘는 LRU랑 헷갈리면 안된다 - LRU는 제일 오래전에 사용된거고 FIFO는 제일 오래전에 메모리로 올라온거임
  • CLOCK(Secondary Chance Algorithm) :

• 이게 뭔뜻이냐면 원 밖에 있는 숫자는 frame# 을 의미 하고 저 한칸한칸에는 해당 프레임에 할당된 page# 와 몇번사용(참조)했는지(use)가 저장되어있다
• 그리고 저 시계바늘이 룰렛마냥 방출될 애를 가리키는 역할이다
• 일단 이러한 구조때문에 CLOCK이라는 이름이 붙어있는 것
• 그리고 이 알고리즘이 구동하는 방식때문에 Second Chance Alg라는 이름이 붙었는데
• 저 시계바늘이 가리키고있는 놈의 use가 0이 아니면 얘를 방출시키지 않고 다음칸으로 넘어가며 use를 0으로 초기화하기 때문에 한번 더 기회를 준다는 의미에서 저런 이름이 붙은 것이다
• 이제 반대로 시계바늘이 가리키고있는놈의 use가 0일 경우에는 그놈을 방출시키고 새로운 페이지를 들이는 것
• 따라서 위의 예시에서 frame# 2, 3의 use가 0으로 바뀌고 4번에 새로운 페이지가 들어오며 들어옴과 동시에 한번 사용하기 때문에 use는 1로 되어있는 것이다
• 이렇게 되면 use가 0이라는 것은 시계바늘이 한바퀴 돌때동안 사용되지 않았다는 뜻이므로 가장 오래전에 사용된거랑 비슷하다 - LRU와 유사한 효과, 성능을 낸다
• 반대로 use가 0이되고 나서 시계바늘이 한바퀴 돌때동안 사용되었다면 다시 use가 올라가므로 시계바늘이 다시 돌아왔을 때 방출되지 않고 다시 0으로 바뀌게 되는것
• Page Buffering : 얘는 뭐냐면
  • 만약 메모리의 일정부분을 free로 유지하기 위해 페이지 한놈을 하드로 내려보냈다고 해보자
  • 근데 실행되다가 이놈이 다시 필요해진 순간이 왔을때 page table로 가서 Pbit를 보면 당연히 하드로 내려갔으므로 없다고 뜰것이다 이말이야
  • 근데 만약에 아직 이자리에 다른 프레임이 overwrite되지 않았으면 이놈은 free이긴 해도 데이터는 그대로 남아있을거란말이지
  • 그래서 바로 IO를 때려 하드에서 갖고오기보다는 데이터가 아직 overwrite되지 않았을 수도 있으므로 free인 저 공간을 다시 조사해 원래의 페이지가 남아있으면 다시 Pbit를 바꾸고 그대로 사용하는 개념이다

Resident Set Management §

• Resident Set Size : 한개의 프로세스에 몇개의 프레임을 할당할 것 인가
  • Fixed : 고정된 갯수의 프레임을 할당
  • Variable : 가변갯수의 프레임을 할당 - 요즘 추세란다

• Working Set Model : 걍 단순하다 - 특정 시점에 Window size(할당되는 프레임 최대 갯수)만큼의 최근 페이지 참조(위의 예시에서 한 시점 기준 window size만큼 위에있는만큼의 페이지를 묶어서)를 보고 그거를 집합으로 묶어 그 시점에의 할당 프레임 갯수를 정하는 것
  • 알고리즘이 간단하고 Locality가 반영된다는 장점 이 있음
  • 하지만 실제로 써보니까 Locality도 제대로 반영 안되고 에 따라 너무 할당되는 갯수도 달라지고 window size를 정하기도 어려운 등의 문제가 있더라

• Variable-Interval Sampled Working Set(VSWS) - 얘는 이제 page fault rate의 상한선과 하한선을 정해놓고 할당갯수를 변화시키면서 rate가 너무 높으면 할당갯수를 늘리고 rate가 하한선보다 떨어져서 할당갯수가 너무 많으면 줄이고 하는식으로 유동적으로 할당갯수를 줄이는 방식이다
• Replacement Scope : 하드로 내려보낼 페이지를 정하는 범위
  • Global : 현재 프로세스가 아닌 다른 프로세스의 페이지를 내려보냄 - 속도를 위해 요즘은 얘를 사용한댄다
  • Local : 현재 프로세스의 페이지를 내려보냄

Cleaning Policy §

• Cleaning Policy : 프로세스가 종료되고 프레임들을 비우는 것에 대한 정책
• 메모리에 있는 페이지가 변경되었을 경우에 변경될때마다 하드에 있는 페이지를 바꿔주기(Demand Cleaning)보다는
• 메모리에 있는놈이 하드로 내려갈때 변경사항을 한번에 업데이트해주는 방법(Precleaning)을 이용한댄다

Load Control §

• Load Control : 프로세스를 메모리에 올려주는 Loader와 관련된 정책 - 몇개의 프로세스를 올려 multiprogramming level을 어떻게 가져가 최적의 cpu utilization을 낼 것인가(Thrasing을 내지 않을 것인가) - 위에서의 Resident Set Management와도 연결되는 내용
• 여기서 multiprogramming level이 너무 높아 page fault가 너무 많이 일어나 프로세스를 내쫒을때는 다음과 같은 룰들을 적용한다(이게 전부는 아님 - 참고)
  1. 우선순위가 낮은놈
  2. fault를 많이 일으키는 놈
  3. 마지막으로 실행된놈
  4. 가장 적은 프레임을 가지고있거나
  5. 가장 사이즈가 큰 프로세스