장기 스케줄러가 disk(풀)에 대기중인 프로세스들 중에서 ready queue로 옮겨질 process들을 선택한다고 했다. 이는 한정된 메모리 때문에 메모리(ready queue)에 모든 프로세스를 옮겨둘 수 없어 프로세스를 선별해 올리는 것이었다.
하지만 최근에는 가상메모리라는 메모리 자원을 추상화하고, 프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능하도록 하는 기법으로 물리 메모리 크기에 제약받지 않고 더 많은 프로그램들을 동시에 실행할 수 있게된다. 응답시간은 유지되고 CPU이용율과 처리율이 높아진다.(swap또한 감소)
결론적으로 가상메모리란, 실제의 물리 메모리 개념과 사용자의 논리 메모리 개념을 분리한 것이며, 메모리를 추상화, 필요한 프로세스만 올리게하는 등 더 큰 메모리처럼 사용할 수 있는 기법 이다.
Virtual Address Space
사용할 수 있는 가상 메모리 주소 집합.
실제 메모리 공간은 아니다. 하지만 프로그램은 할당받은 가상 주소 공간이 진짜 메모리인 것 처럼 사용한다.
가상메모리의 실제 공간은 하드디스크 + RAM이 된다
가상 메모리의 기본 아이디어는 프로세스는 가상 주소를 사용하고, 데이터를 read/write할 때에는 물리 주소로 변환해 접근한다는 것.
가상 주소 공간은 code, data,heap,stack영역으로 구성되어있다.
page에 대해서 학습했을 때, 물리 메모리를 frame, 논리 메모리(프로세스 점유)를 page라는 이름으로 고정크기 블록으로 분리한다. 라고 했는데
할당된 가상주소공간을 특정 크기 단위로 나눈 하나의 메모리 블록을 page라고 하는 것임.
- address 복습 : 프로세스 주소
- 논리적 주소(logical address)
가상주소. (virtual address). CPU가 생성하며 프로세스마다 독립적으로 가지는 주소 공간이기 때문에 프로세스 내부에서 사용.(프로세스참조주소)- 물리적 주소
프로세스가 실행되기 위해 실제로 메모리에 load되는 위치.(실제메모리주소)- adress binding
프로세스의 logical 주소를 물리적 메모리 주소로 연결시켜주는 작업(cpu가 보는 주소인 logical address와 메모리hw의 위치인 물리적주소 연결)
필요한 Page만 실행 중 보조저장장치에서 메모리로 적재시키는 방법. 가상메모리를 구현하는 방법이다.
page fault는 매우 적은 확률로 발생해야 효율적이다. 그러면 현실적으로 페이지 부재는 어느정도로 발생할까? 이는 지역성의 원리(Locality of reference)로 인해 페이지 부재 확률은 매우 낮다. 지역성의 원리는 '메모리 접근은 시간적 지역성과 공간적 지역성을 가진다'는 의미이다.
- 시간적 지역성: CPU는 어느 메모리 공간을 읽은 후, 시간이 지나도 그 공간을 다시 읽을 확률이 매우 높다는 것을 말한다.
- 대표적인 예로 반복문이 있다. 반복문은 하나의 코드 공간을 여러 번 읽는다.
- 공간적 지역성: CPU가 메모리 공간을 읽을 때는 인접한 범위 내에서 읽는다는 의미이다.
- 프로그램은 대부분 절차적인 순서로 구현되어 있어 순서대로 읽는 경우가 빈번
페이지 폴트가 발생할 경우 스왑(disk)영역에서 메모리 영역으로 불러와야 하는데, 이런 페이지 폴트가 빈번하게 발생할 경우, 해당 로딩 시간 때문에 사용자에게 큰 불편. 그렇기 때문에, 메모리에서 사용될 가능성이 높은 프로세스 모듈을 미리 스케쥴링해서 메모리에 적재해 주는 방법을 고안하는 것이 필요. : 페이지 교체 알고리즘. 페이지 교체 알고리즘에서는 '지역성'이 중요한 스케줄링 기준이 된다.
간단 중간 정리 )
paging은 정리하자면 프로그램이 동작하기 위한 메모리(램)을 효율적으로 사용하기위해, 논리메모리-물리메모리 개념으로 구분, 하드디스크만큼의 용량을 ram으로 사용(가상메모리)하여, 지금 필요한 부분만을 메모리에 올리고 나머지는 cpu에게는 메모리에 올라가있는 것 처럼 취급( 이 때 디스크에 저장되있는 모듈들은 실제 메모리 주소가 존재하지 않으므로 cpu입장에서는 일괄적으로 논리메모리를 바라보고, 실제 메모리에 올라가있는 경우에만 논리 메모리를 물리 메모리로 매핑)하는 방법에서, 메모리 관리자가 사용하는 '배치'=메모리 분할 방식 중 하나이다. 가상 메모리를 일정 크기로 쪼개 프로세스를 나눠 메모리를 할당하는 방식이다. '페이지'가 분할된 논리 메모리의 단위이고, 매핑되는 물리메모리는 '프레임'이라고 함. 그렇다면 demand-paging은? 프로세스는 페이지 단위로 나누어져 불연속하게 메모리를 할당한다고 했는데, 특정 모듈(페이지)가 필요해지게 되는 경우, 메모리에 해당 모듈을 요청해 물리메모리를 매핑시키는, 재배치방법이다.
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()를 호출하는 경우를 위해 마련된 것
프로세스(페이지)는 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 알고리즘은 각 페이지마다 마지막 사용 시간을 유지해 페이지 교체 시 가장 오랫동안 사용되지 않은 페이지를 선택한다.
하드웨어 지원이 필요.(마지막 사용시간 유지)
LFU (Least Frequently Used) 페이지 교체 알고리즘
가장 적게 사용된 페이지를 교체. (계수알고리즘)
NUR ( Not Used Recently )
최근에 사용하지 않은 페이지부터 교체. 각 페이지마다 참조비트(R) , 수정비트(W)를 갖고 (R,M)짝으로 페이지 순서를 구분
읽기,쓰기 동일일 경우 쓰기가 큰 것을 우선 교체대상으로 삼는다.
멀티 프로세스들에게 제한된 free memory를 어떻게 할당할지. 각 프로세스는 몇 프레임씩 할당받아야하는지에 대한 정책.
메모리 할당에는 최소한 할당해야하는 페이지들이 존재한다. 각 프로세스에 할당되는 프레임 수가 줄어들면 페이지 부재율은 증가하고 프로세스 실행은 늦어지게됨.
할당 알고리즘
비균등 메모리 접근 : 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를 만들 수 있다.