OS - (8) Virtual Memory

Virtual Memory

Background

장기 스케줄러가 disk(풀)에 대기중인 프로세스들 중에서 ready queue로 옮겨질 process들을 선택한다고 했다. 이는 한정된 메모리 때문에 메모리(ready queue)에 모든 프로세스를 옮겨둘 수 없어 프로세스를 선별해 올리는 것이었다.

하지만 최근에는 가상메모리라는 메모리 자원을 추상화하고, 프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능하도록 하는 기법으로 물리 메모리 크기에 제약받지 않고 더 많은 프로그램들을 동시에 실행할 수 있게된다. 응답시간은 유지되고 CPU이용율과 처리율이 높아진다.(swap또한 감소)

결론적으로 가상메모리란, 실제의 물리 메모리 개념과 사용자의 논리 메모리 개념을 분리한 것이며, 메모리를 추상화, 필요한 프로세스만 올리게하는 등 더 큰 메모리처럼 사용할 수 있는 기법 이다.

Virtual Address Space

메모리-물리메모리-가상메모리 정리 잘 되어있는 포스팅

• Virtual Address Space
  사용할 수 있는 가상 메모리 주소 집합.
  실제 메모리 공간은 아니다. 하지만 프로그램은 할당받은 가상 주소 공간이 진짜 메모리인 것 처럼 사용한다.
  가상메모리의 실제 공간은 하드디스크 + RAM이 된다
  가상 메모리의 기본 아이디어는 프로세스는 가상 주소를 사용하고, 데이터를 read/write할 때에는 물리 주소로 변환해 접근한다는 것.

  
  가상 주소 공간은 code, data,heap,stack영역으로 구성되어있다.

  • code : 기계여(코드를 컴파일, 어셈블리어 변환된 프로그램 코드파일)
  • data : 전역변수, static변수의 할당을 위해 존재하는 공간.
  • heap : 동적 할당되는 공간. 사용자가 직접 관리하는 공간. 사용자에 의해 메모리 공간이 동적으로 할당되고 해제된다.
  • stack : 지역 변수가 저장되는 공간.

  page에 대해서 학습했을 때, 물리 메모리를 frame, 논리 메모리(프로세스 점유)를 page라는 이름으로 고정크기 블록으로 분리한다. 라고 했는데
  할당된 가상주소공간을 특정 크기 단위로 나눈 하나의 메모리 블록을 page라고 하는 것임.

  • python의 virtual address space
    파이썬은 모든 객체를 private heap영역에 저장, data영역과 stack영역은 사용하지 못한다. 연산할 때는 값을 heap으로부터 레지스터로 가져오고, ALU(logical unit, 연산장치)로 넘겨 연산 수행, 결과값은 stack저장->register->heap 순으로 재전달한다. 참고 : 파이썬 메모리 관리

  • address 복습 : 프로세스 주소
    • 논리적 주소(logical address)
      가상주소. (virtual address). CPU가 생성하며 프로세스마다 독립적으로 가지는 주소 공간이기 때문에 프로세스 내부에서 사용.(프로세스참조주소)
    • 물리적 주소
      프로세스가 실행되기 위해 실제로 메모리에 load되는 위치.(실제메모리주소)
    • adress binding
      프로세스의 logical 주소를 물리적 메모리 주소로 연결시켜주는 작업(cpu가 보는 주소인 logical address와 메모리hw의 위치인 물리적주소 연결)

Demand Paging

필요한 Page만 실행 중 보조저장장치에서 메모리로 적재시키는 방법. 가상메모리를 구현하는 방법이다.

• Valid - Invalid bit
  사용되지 않는 주소 영역인 경우, 페이지가 물리적 메모리에 없는 경우의 bit. <-> Valid
  처음에는 모든 Page가 Invalid로 초기화되고, 사용되면 Valid로 변경된다.
• Page Fault
  메모리에 해당 모듈(페이지)이 적재되어있지 않은 경우, 즉 스왑 영역에 해당 모듈(페이지)이 있는 경우.
  어떤 페이지가 물리 메모리에 없을 때 발생하는 인터럽트(사용할 수는 있지만 아직 메모리에 적재되지 않은 상태와 가상주소공간상에 정의되지 않은 경우 둘다 해당. , page table의 valid-invalid bit이 invalid.), Page fault가 발생하면 운영체제가 해당 페이지를 물리메모리에 올려준다.
  page fault는 인터럽트기 때문에 ISR을 수행하는 처리과정을 거친다.
  
  1. virtual address 요청
  2. TLB를 확인해서 논리주소를 가지고 해당하는 프레임번호 f가 있는지 확인.
     • TLB Hit시 바로 메모리 접근, (f,d)를 가져온다.
     • Miss 시 페이지 테이블 참조해야함.
  3. TLB Miss시 논리주소(p,d)를 가지고 테이블 접근
     • p에 해당하는 f가 valid하면 메모리에 접근해 로드
     • invalid하다면 Page Fault Interrupt (OS로보냄)
  4. OS가 메모리 접근 시 주소(page block)를 확인하고, 물리 메모리에서 빈공간을 찾는다. 없다면 적절하게 다른 프레임을 교체시켜야함. free frame 확보 필요.
  5. 저장소에서 매치되는 page를 frame에 올린다. 저장소 접근은 I/O이므로 프로세스는 wait상태. context switching이 발생한다. -> 끝나면 page table 업데이트 및 invalid bit valid로 변경.
     -> 프로세스는 ready queue로 옮겨지고 일반적으로 스케줄링 절차를 따름.
  6. process가 CPU를 다시 할당받게되면 page fault 트랩 처리가 완료. restart해 page fault를 유발했던 명령어부터 다시 수행해 해당과정 재실행 (Process Counter(PC)를 증가시키지 않기 때문에 PC 증가 시 해당 명령어는 강제 pass)

page fault는 매우 적은 확률로 발생해야 효율적이다. 그러면 현실적으로 페이지 부재는 어느정도로 발생할까? 이는 지역성의 원리(Locality of reference)로 인해 페이지 부재 확률은 매우 낮다. 지역성의 원리는 '메모리 접근은 시간적 지역성과 공간적 지역성을 가진다'는 의미이다.

• 시간적 지역성: CPU는 어느 메모리 공간을 읽은 후, 시간이 지나도 그 공간을 다시 읽을 확률이 매우 높다는 것을 말한다.
  • 대표적인 예로 반복문이 있다. 반복문은 하나의 코드 공간을 여러 번 읽는다.
• 공간적 지역성: CPU가 메모리 공간을 읽을 때는 인접한 범위 내에서 읽는다는 의미이다.
  • 프로그램은 대부분 절차적인 순서로 구현되어 있어 순서대로 읽는 경우가 빈번

페이지 폴트가 발생할 경우 스왑(disk)영역에서 메모리 영역으로 불러와야 하는데, 이런 페이지 폴트가 빈번하게 발생할 경우, 해당 로딩 시간 때문에 사용자에게 큰 불편. 그렇기 때문에, 메모리에서 사용될 가능성이 높은 프로세스 모듈을 미리 스케쥴링해서 메모리에 적재해 주는 방법을 고안하는 것이 필요. : 페이지 교체 알고리즘. 페이지 교체 알고리즘에서는 '지역성'이 중요한 스케줄링 기준이 된다.

간단 중간 정리 )
paging은 정리하자면 프로그램이 동작하기 위한 메모리(램)을 효율적으로 사용하기위해, 논리메모리-물리메모리 개념으로 구분, 하드디스크만큼의 용량을 ram으로 사용(가상메모리)하여, 지금 필요한 부분만을 메모리에 올리고 나머지는 cpu에게는 메모리에 올라가있는 것 처럼 취급( 이 때 디스크에 저장되있는 모듈들은 실제 메모리 주소가 존재하지 않으므로 cpu입장에서는 일괄적으로 논리메모리를 바라보고, 실제 메모리에 올라가있는 경우에만 논리 메모리를 물리 메모리로 매핑)하는 방법에서, 메모리 관리자가 사용하는 '배치'=메모리 분할 방식 중 하나이다. 가상 메모리를 일정 크기로 쪼개 프로세스를 나눠 메모리를 할당하는 방식이다. '페이지'가 분할된 논리 메모리의 단위이고, 매핑되는 물리메모리는 '프레임'이라고 함. 그렇다면 demand-paging은? 프로세스는 페이지 단위로 나누어져 불연속하게 메모리를 할당한다고 했는데, 특정 모듈(페이지)가 필요해지게 되는 경우, 메모리에 해당 모듈을 요청해 물리메모리를 매핑시키는, 재배치방법이다.

Copy-On-Wirte

demanding paging에서 프로세스를 빠르게 시작하기위해 첫 명령어가 포함된 페이지를 메모리에 올린다. 그러나 fork()시스템 호출을 통해 프로세스를 생성할 때에는 page 공유와 비슷한 방법으로 첫 demand paging조차 생략하는 것이 가능. 프로세스 생성 시간을 줄일 수 있고, 프로세스에 새롭게 할당되어야 하는 페이지 수도 최소화 가능.

fork()를 하면 부모 프로세스의 페이지들을 실제로 자식 프로세스에 복사해 줌으로써 자식 프로세스의 주소 공간을 구성해 주고 대부분의 자식 프로세스들은 주소 공간이 마련되자마자 exec() 시스템 호출 (부모로부터 복사해온 페이지들은 다 쓸모 없는 것들이 됨)

exec
프로세스를 새로운 프로그램을 실행하는 프로세스로 대체하는 시스템 콜 함수.
fork()와 다르게 자식 자식 프로세스를 생성하는 것이 아닌 현재 프로세스의 프로그램 코드를 새로운 프로그램 코드로 바꿔주고 프로그램 코드, 메모리, 파일 등 프로세스 자원이 새로 바뀌게 됨.( 새로운 프로그램 실행 프로세스로 대체되므로 반환값 x
보통 동작하는 방식은 fork()를 통해 자식 프로세스를 생성하고 자식 프로세스에서 exec()를 통해 새로운 프로그램을 돌리게 된다.

-> 부모의 페이지들을 다 복사해오는 대신 쓰기 시 복사(copy-on-write)방식을 사용할 수 있다
자식 프로세스가 시작할 때 부모의 페이지를 당분간 함께 사용하도록 한다(복사페이지) -> 둘중 한 프로세스가 공유중인 페이지에 write를 할 때 해당 페이지를 Copy하는 방식.

일부 운영체제는 vfork()(virtual memory fork)라는 시스템 호출을 제공
vfork()는 쓰기 시 복사를 사용하지 않으므로 자식 프로세스가 부모 주소 공간의 페이지를 수정하게 되면 변경된 페이지가 재실행 시 부모 프로세스에 그대로 보여진다.
vfork()를 사용할 때에는 자식 프로세스가 부모 주소 공간의 페이지들에 변경을 가하지 않도록 주의해야 한다. vfork()는 자식 프로세스가 만들어지자마자 exec()를 호출하는 경우를 위해 마련된 것

Page Replacement

프로세스(페이지)는 Demanding page에의해 필요할 때 마다 메모리에 올려서 사용한다. 이 때 물리(실제) 메모리가 Full이라면(over allocation). 기존 페이지 중 하나를 Disk(가상메모리)로 내리고 새로운 페이지를 물리 메모리와 매핑해주어야 한다.

이 때 어떤 페이지를 올려야하는 페이지와 교체해줄까를 결정하는 방법론들은 FIFO,Optimal,LRU등이 있다.

• FIFO 페이지 교체 알고리즘
  가장 오래된 페이지를 내보낸다.
  성능은 좋지 않다. Belday anomaly(모순) 발생함. -> 프로세스에 할당된 프레임을 증가시켰는데 오히려 page fault율이 증가하는 현상.
  ex) 1,2,3,4,1,2,5,1,2,3,4,5 순으로 demanding page이 주어질 때,
  frame 3개라면 1(miss) ,2(miss) ,3(miss) ,4(miss) ,1(miss) ,2(miss) ,5(miss) ,1,2,3(miss) ,4(miss) ,5로 page_fault는 6번.
  frame이 4개라면 1(miss) ,2(miss) ,3(miss) ,4(miss) ,1,2,5(miss) ,1(miss) ,2(miss) ,3(miss) ,4(miss) ,5(miss) 로 page fault는 7번

  나중에 요구되더라도 현재 메모리에 올라와있다면 time을 최신으로 갱신시켜주는 것이 아니고 처음 메모리 할당된 페이지순으로 교체 대상이 되기 때문에, 오히려 한 번 교체되는 것이 앞으로 적재되기 때문에 다음 요구 주기가 올 때 까지 메모리에 남아있어 miss되지 않는 경우가 생기는 것.
  

• 최적(Optimal) 페이지 교체 알고리즘
  앞으로 가장 오랫동안 사용되지 않을 페이지를 예측해서 교체하는 것. 실제 구현이 어렵다. (SJF와 유사)

• LRU (Least Recently Used) 페이지 교체 알고리즘
  가장 오래 전에 사용된 페이지를 교체.
  LRU 알고리즘은 각 페이지마다 마지막 사용 시간을 유지해 페이지 교체 시 가장 오랫동안 사용되지 않은 페이지를 선택한다.
  하드웨어 지원이 필요.(마지막 사용시간 유지)

  • counter : 각 페이지 항목마다 사용시간 필드를 넣고 CPU에 논리적 시계나 카운터를 추가.
  • stack : 페이지 번호의 스택을 유지. 페이지가 참조될 때 마다 페이지 번호는 스택 중간에서 제거되어 top에 놓이게된다. (보통 이중연결리스트 구조. ) -> 오버헤드 발생, 맨 밑에있는 스택이 상단으로 이동될경우 많은 주소변환 필요.

• LFU (Least Frequently Used) 페이지 교체 알고리즘
  가장 적게 사용된 페이지를 교체. (계수알고리즘)

• NUR ( Not Used Recently )
  최근에 사용하지 않은 페이지부터 교체. 각 페이지마다 참조비트(R) , 수정비트(W)를 갖고 (R,M)짝으로 페이지 순서를 구분
  읽기,쓰기 동일일 경우 쓰기가 큰 것을 우선 교체대상으로 삼는다.

  • 2차 기회 알고리즘(LRU Approximation)
    페이지가 선택될 때 마다 참조 비트를 확인해서 0이면 교체, 1이면 다시 한번 기회를 주고 다음 페이지(FIFO)로 넘어가는 방식. 초기 참조 비트는 0이며 프로세스가 실행되면서 참조되는 페이지의 비트는 하드웨어가 1로 셋팅.
    -> 개선하여 참조비트와 변경비트(reference/read , modify/write)로 나누어 (0,0) (0,1) (1,0) (1,1) 우선순위로 교체.=NUR

Allocation of Frames

멀티 프로세스들에게 제한된 free memory를 어떻게 할당할지. 각 프로세스는 몇 프레임씩 할당받아야하는지에 대한 정책.

• global replacement : 메모리 상 모든 프로세스 페이지에 대한 교체 작업 수행
  프로세스가 교체할 프레임 (victim frame)을 다른 프로세스에 속한 프레임을 포함한 모든 프레임을 대상으로 찾는다.
• local replacement : 메모리 상 자기 자신의 프로세스 페이지에 대해서만 교체 작업을 수행
  각 프로세스가 자기에게 할당된 프레임 중에서만 교체될 희생자를 선택할 수 있다.

메모리 할당에는 최소한 할당해야하는 페이지들이 존재한다. 각 프로세스에 할당되는 프레임 수가 줄어들면 페이지 부재율은 증가하고 프로세스 실행은 늦어지게됨.

• 스레싱(Thrashing)
  메모리에 올라가는 프로세스 개수가 증가했을 때 오히려 CPU이용률이 감소하는 현상.
  
  과도하게 프로세스를 할당(멀티 프로그래밍 레벨 과도 증가)하면 반복적으로 페이지 폴트가 발생해 과도하게 페이지 교체 작업(메모리와 backing store 사이에 page in/out 작업, 비용이 크다)이 빈번히 일어나서 실제로 어떤 실행도 하지 못하게 된다.
  • 해결 방법1 : global replacement보다 local replacement를 사용하는 것. (메모리 사용 효율 떨어지는 단점)
  • 해결 방법2 : 프로세스당 충분한/적절한 수의 프레임(메모리)할당
    적절한 프레임은 얼마나 되는 프레임을 말하는지 생각하기 전, 프레임 할당은 크게 정적/동적 할당으로 나뉜다.
    • 정적 할당
      • equal allocation(균등할당) : 모든 프로세스에게 똑같은 수의 프레임 할당.
      • proportional allocation(비례 할당) : 프로세스 크기에 따라 프레임을 할당 프로세스 크기가 크더라도 적게 사용될 수 있어 비효율적.
    • 동적 할당 : 실행 중에 프레임을 할당
      • working set model : 프로세스가 실행중일 때 어느 페이지를 사용하는지 실험에서 locality가 성립한다는 결과가 있다고 한다. 특정 시간에는 일정 범위의 페이지를 주로 참조.이를 통해 특정 시간에 따라 사용하는 페이지의 개수 만큼 프레임을 할당해줄 수 있다. (프로세스를 미리 수행해봐야 알기 때문에 비현실적)
        -> working set은 locality의 방법과 유사하나, 과거 working set(현재 시간에서 일정 시간(working set window) 이전동안 사용되었던 페이지의 집합) 개수 만큼 프레임을 할당한다.
      • Page-Fault Frequency(PFF)
        할당된 프레임 수가 적을수록 페이지 부재 비율은 늘어남. OS 내부에서 프로세스 페이지 부재 횟수를 검사하고, uppder bound와 lower bound를 설정한다. 만약 upper보다 많은 페이지 부재가 발생하면 프레임을 더 많이 할당해주고, lower보다 더 작게 발생하면 할당 프레임 개수를 줄여준다.

• 할당 알고리즘

  • 균등 할당 : n개의 프로세스에 m개의 프레임씩 분할.
  • 비례 할당 : 프로세스 크기 비율에 맞추어 프레임을 할당
  • 우선순위 할당 : 비례 할당 방법을 사용하면서 프레임 비율을 프로세스 크기가 아닌 우선순위를 사용하여 할당.

• 비균등 메모리 접근 : NUMA ( Non-uniform memory access )
  cpu마다 local memory가지고있고, 특정 cpu는 메인 메모리의 일정 영역을 다른 영역보다 빠르게 접근할 수 있다. process할당 시 OS가 CPU에 가까운 메모리에 free frame을 할당한다.

각 프로세스별로 CPU와 메모리에 접근하는데 걸리는 시간이 달라 latency group을 만들어 더 빠른 접근이 가능한 그룹을 우선순위로 할당해준다. 멀티 프로세싱 시스템에서 어떤 프로그램을 먼저 실행할지 결정해주는 latency group

일반적인 하드웨어는 작은 프로세서 집합(GROUP= NUMA 노드)에 사용되는 시스템 버스를 여러개 구성한다.
각 프로세서 그룹에는 자체 메모리 존재, 자체I/O채널이 있는 경우도 있다. CPU는 일관된 방법으로 다른 그룹과 연결된 메모리에 엑세스 하는데, numa는 로컬 메모리와 외부 메모리를 사용하므로 다른 영역에 비해 일부 메모리영역에 엑세스하는 시간이 오래 걸리고, 로컬 메모리와 외부 메모리의 구분은 현재 실행중인 스레드에 대한 참조 위치에 따라 구분된다. 로컬 메모리는 현재 CPU와 같은 노드에 있는 메모리이며 스레드가 현재 실행중인 노드에 속하지 않는 메모리가 외부 메모리임. 공유 리소스를 중심으로 프로세서를 그룹화하여 soft numa를 만들 수 있다.