운영체제 -메모리-

메인 메모리

cpu는 pc가 지시하는 대로 메모리로부터 다음 수행할 명령어를 가져온다. cpu는 메모리까지 접근한다. 만약 데이터가 메모리에 없다면 cpu가 처리하기 전에 메모리로 이동해야 한다.

또한 CPU가 레지스터에 비해 메모리에 접근하는 경우 많은 CPU 클록 사이클이 발생한다. 따라서 메모리와 CPU 사이에 캐시 메모리를 둔다. 지연되는 현상을 stall이라 한다

 

프로세스는 각 독립된 메모리 공간을 가지도록 보장해야 한다. 따라서 기준 레지스터와 상한 레지스터를 사용하여 프로세스의 메모리 시작 주소와 크기를 정한다. 메모리 공간을 보호하기 위해 메모리 주소 결정은 운영체제에서만 관리한다.

 

프로그램 주소 할당 과정

컴파일러가 원시 주소를 재배치 가능한 주소로 바인딩하고 링커나 로더가 재배치 가능 주소를 절대 주소로 바인딩한다.  

• 컴파일 시 주소 할당 : 절대 주소를 컴파일 시간에 한다. 만약 주소값이 변경되면 컴파일 부터 수행해야 한다
• 로딩 타임에 주소 할당 : 프로그램이 메모리에 적재 되는 순간에 할당한다. 주소값이 변경되면 프로그램 재시작  
• 실행 시간 주소 할당 : 특별한 하드웨어(MMU)를 통해 프로세스가 실행하는 중간에 메모리가 변경 가능하다. 

논리 주소와 물리 주소

CPU가 생성하는 주소를 논리 주소, 메모리가 취급하는 주소는 물리 주소라고 한다

컴파일 타임과 적재 타임에 주소를 바인딩하면 논리 주소와 물리 주소가 같다. 하지만 실행 시간에 바인딩하면 논리, 물리 주소가 다르다. 따라서 이러한 논리 주소를 물리 주소로 변경할 수 있어야 하는데 이 작업은 메모리 관리 장치(MMU)에 의해 수행된다.

 

동적적재

프로세스가 실행되기 위해서는 메모리에 프로그램이 모두 올라가야 되는데, 메모리를 효율적으로 사용하지 못한다. 따라서 main 프로그램만 메모리에 올리고 나머지는 메모리에 올라왔는지 조사하고 올라와 있지 않다면 메모리에 올리는 작업을 수행한다.

 

메모리 할당

사용자 영역과 운영체제 영역으로 두 개의 부분으로 나뉜다.

 

연속메모리 할당

프로세스마다 연속적으로 프로세스의 크기 만큼 메모리에 할당해준다. 

 

가변 메모리 할당 

프로세스마다 필요한 만큼 메모리 할당 하는 방법

 

고정 메모리 할당

메모리를 특정 크기로 잘라 특정 크기 단위로 분할하는 방법 

 

할당 방법

• 최초 적합 : 첫 번째 가용 공간에 할당한다
• 최적 적합 : 가용 공간중 가장 작은 것을 선택한다
• 최악 적합 : 가장 큰 가용 공간을 택한다

메모리 효휼 측면에서 최초 적합과 최적 적합이 좋다. 시간은 최초 적합이, 메모리 효율은 최적 접합이 좋다.

 

연속 메모리 할당 단점 : 외부 파편화와 내부 파편화가 발생한다.

* 외부 파편화 : 메모리에 프로세스를 적재할 수 있는 공간이 있음에도 프로세스 보다 작은 블록들로 나누어져 있기 때문에 할당하지 못하는 문제 (가변 메모리 할당에서 발생)

* 내부 파편화 : 프로세스를 여러개의 특정 블록 단위로 할당하므로 블록 단위보다 작은 메모리라도 블록 단위로 할당해주어야 한다. (고정 메모리 할당에서 발생)

 

페이징

프로세스의 물리 공간이 연속적이지 않다.  

물리 메모리는 프레임이라 불리는 같은 크기의 블록으로 나누어지며, 논리 메모리는 페이지라 불리는 같은 크기의 블록으로 나누어진다. 

 

CPU에서 나오는 모든 주소는 페이지 번호와 페이지 오프셋 두 개의 부분으로 나누어진다. 페이지 번호는 프로세스 페이지 테이블을 엑세스 할 때 사용된다. 페이지 테이블은 각 프레임의 시작 주소를 저장되고 있으며 오프셋은 참조되는 프레임 안에서의 위치이다. (페이지 테이블은 프로세스별 자료구조이다)

페이지 크기가 작아지면 내부 단편화는 줄어들지만 페이지를 관리하는 페이지 테이블의 크기는 커진다. 따라서 적절한 페이지 크기를 사용해야하며 현재 페이지 크기는 보통 4KB또는 8KB이다. 

 

페이지 테이블은 메인 메모리에 저장되고 페이지 테이블 기준 레지스터(PTBR)로 페이지 테이블을 가르킨다.

 

운영체제는 물리 메모리를 관리하기 때문에 페이지와 메핑된 물리 메모리 할당에 대해서 알고 있어야 한다. 따라서 운영체제가 시스템에 하나밖에 없는 프레임 테이블을 가지고 있다. 프레임 테이블은 프레임이 비어 있는지, 할당되었는지, 어느 프로세스의 어느 페이지에 할당되었는지를 나타낸다

 

페이지 테이블에서 각 엔트리에는 유효/무효 라는 하나의 비트가 있다.

유효일 경우 :  관련된 페이지가 프로세스의 합법적인 페이지임을 나타낸다.

무효일 경우 : 그 페이즈는 프로세스의 논리 주소 공간에 속한 것이 아님을 나타낸다.

 

TLB

사용이유 : 페이지 테이블에서 해당 페이지 찾아 실제 주소 찾기, 실제 주소 엑세스로 총 2번 메인 메모리 엑세스가 필요하다. 따라서 TLB라는 캐시 메모리를 사용해서 저장되어 있는 페이지를 병렬로 찾아 해당 페이지의 프레임을 바로 넘겨준다. 

 

실제 주소 찾는 과정

TLB에서 우선적으로 페이지 찾는다 

• 있을 경우 바로 페이지와 맵핑된 프레임으로 물리 주소 엑세스한다
• 없을 경우 메인 메모리 페이지 테이블에서 물리 주소를 찾고 그 물리 주소를 엑세스 한다

TLB가 가득 찰 경우 교체 정책

중요 커널 코드는 TLB에 고정한다

• LRU (least recently use) : 가장 오랫동안 사용되지 않은 페이지 내쫒는다
• 라운드 로빈 : 돌아가며 내쫒는다
• LRU(least frequently use) : 가장 적게 사용된 페이지 내쫒는다

TLB는 페이지 정보와 프레임을 맵핑 시키는 것이다. 따라서 프로세스마다 페이지 테이블이 다르므로 문맥교환이 일어나는 경우 TLB를 플러시(초기화) 한다. 

 

 공유페이지

공통의 코드를 공유할 수 있다. 공통의 코드 영역에서 프로세스는 코드 영역의 페이지 테이블만 사본으로 저장해 실제 코드 영역은 공유해서 사용할 수 있다,

 

페이지 테이블의 구조

• 계층적 페이징 : 페이지 테이블을 계층적으로 관리한다 
• 해시 페이지 테이블 : 가상 주소를 해시로 사용한다. (페이지 테이블과 페이지가 일대일이 아닌 일대다로 구성된 클러스터 페이지 테이블도 있다)
• 역 페이지 테이블: 프레임 기준으로 페이지 테이블을 만든다. 이 경우 프로세스별로 페이지 테이블을 가지는 것이 아닌 하나의 페이지 테이블을 가진다. 역 페이지 테이블은 pid와 페이지 주소를 가지고 있다. 장점은 페이지 테이블을 단순화하여 메모리 소비를 줄인다. 단점은 페이지를 찾기위해 오래 걸리며 공유 페이지를 사용할 수 없다

스와핑

프로세스 또는 프로세스의 일부분이 실행 중에 임시로 백업 저장장치(스왑영역)로 내보내고 메모리에 되돌아올수 있는 기능

실제 물리메모리보다 더 많은 메모리를 수용할 수 있는 장점이 있다. 스왑되는 후보는 유휴 상태 비활성 프로세스이다.

 

* 프로세스 전체를 스왑영역으로 보내는 표준 스와핑은 메모리와 저장장치 간에 프로세스를 이동하는 데 매우 많이 걸리기 때문에 최신 운영체제에서는 사용하지 않는다

현재는 프로세스 전체가 아닌 페이지 일부를 스왑하는 방식을 사용한다

• 페이지 인 : 백업 장치 -> 메모리
• 페이지 아웃 : 메모리 -> 백업 장치

가상 메모리

가상 메모리는 실제의 물리 메모리 개념과 개발자 논리 메모리 개념을 분리한 것이다.

 

요구 페이징

필요한 페이지만 적재한다. 요구 페이징 가상 메모리를 사용하면 프로그램 실행 중 필요할 때만 페이지가 적제된다

 

가상메모리에 페이지 테이블 무효/유효 비트는 해당 페이지가 메모리에 있냐, 없냐를 나타낸다

무효 : 메모리에 없음, 유효 : 메모리에 있음

프로세스가 메모리에 올라와 있지 않는 페이지 접근하면, 페이지 테이블에서 무효로 설정되어 있으므로 페이지 폴트 트랩을 발생시킨다.

 

1. 프로세스 내부 테이블 검사, 메모리가 유효한지 무효한지 알아낸다
2. 만약 무효하다면 프로세스 중단, 메모리에 없다면 보조저장장치에서 가져온다
3. 빈 공간 가용 프레임을 찾는다
4. 보조 장치에서 새로 할당된 프레임으로 페이지를 읽는다
5. 읽기가 끝나면 메모리에 있다는 것을 알리기 위해 페이지 테이블을 갱신하며, 프로세스가 유지하고 있는 내부 테이블을 수정한다
6. 트랩에 의해 중단 되었던 명령어를 다시 수행한다

순수 요구 페이징 : 어떤 페이지가 필요해지기 전에는 결코 그 페이지를 메모리에 적재 하지 않음

참조 지역성 : 프로그램은 어느 특정 작은 부분만 한동안 집중적으로 참조한다

 

요구 페이징을 위해서는 페이지 폴트 오류 처리 후에 명령어 치리를 다시 시작할 수 있어야 한다

 

가용 프레임 리스트 : 페이지 할당을 위해 가용할 수 있는 프레임을 리스트로 관리, 일반적으로 Zero-fill-on-demand 사용, 이 프레임은 할당되기 전에 0으로 모두 초기화 한다

 

페이지 폴트는 많은 시간이 걸리기 때문에 페이지 폴트를 최소화 해야 한다. trap -> 인터럽트 벡터 페이지 폴트 확인 -> 가용 프레임으로 페이지 메모리 적제(디스크 i/o) -> 페이지 테이블 갱신

 

요구 페이지 스왑 공간을 관리한다. 스왑공간에서 디스크 i/o는 파일 시스템보다 더 큰 블록을 사용하여 빠르다. 

페이지를 교체할 때 스왑 공간을 사용한다

 

쓰기 시 복사 : 자식 프로세스가 부모 페이지를 공유하다가 공유 중인  페이지가 쓸 때 그 페이지의 복사본이 만들어 진다. vfork : 페이지가 전혀 복사되지 않는다. 자식이 exec 하는 경우를 위해 만든 기능

 

페이지 교체

1. 페이지 위치를 찾고 빈 페이지 프레임을 찾는다
2. 비어 있는 프레임이 있으면 사용하고 없으면 희생될 프레임을 선정한다.(페이지 교체 알고리즘 사용)
3. 희생된 페이지를 기록하고 관련 테이블 갱신한다
4. 희생된 페이지에 새로운 페이지를 일고 테이블 수정한다

빈 페이지가 없을 경우 디스크 두번 접근한다(희생 프레임 기록할때, 새 페이지 읽을 때)

희생되는 페이지는 변경 비트를 확인해 변경되지 않은 페이지를 희생한다(변경되지 않았으므로 희생 프레임을 디스크에 기록하지 않아도 된다)

 

요구 페이지에는 두 가지 문제를 해결해야 한다 

• 프레임 할당 알고리즘 : 각 프로세스에 얼마나 많은 프레임 할당할 것인지
• 페이지 교체 알고리즘 : 어떤 페이지를 교체할 것인지

페이지 교체 알고리즘

• FIFO : 가장 오래된 페이지 내쫒는다, Belady의 모순- 프로세스에 프레임을 더 많이 할당 했는데 페이지 폴트율이 증가 하는 현상
• 최적 페이지 교체 : 앞으로 가장 오랫동안 사용되지 않을 페이지 교체, 실제 구현 어렵다. 
• LRU : 가장 오랜 기간동안 사용되지 않은 페이지 교체 - 시간 기록(계수기)나 스택 방법 사용한다
• 2차 기회 알고리즘 : 순환큐를 이용하여 참조 비트가 0이면 교체하고 1이면 기회를 준다
• LFU : 알고리즘 참조 횟수가 가장 적은 페이지 교체 

프레임 할당

최소한의 프레임을 할당해야 한다 : 각 프로세스에 할당되는 프레임 수가 줄어들면 페이지 폴트가 발생한다. 

 

할당 알고리즘

• 균등할당 : 프로세스 균등하게 할당
• 비례할당 : 프로세스 크기에 비례하여 할당
• 전역 교체와 지역 교체 : 전역 교체 - 희생자 프레임을 다른 프로세스를 포함한 모든 프레임에서 찾는다, 지역 교체 - 희생자 프레임을 프로세스 자신이 할당 받은 프레임 내에서 찾는다

스레싱

과도한 페이징 작업으로 인해 실제 실행보다 더 많은 시간을 페이징에 사용하고 있는 현상

• 페이지 폴트 발생 -> CPU 이용률 떨어짐 -> 더 많은 프로세스 추가 -> 더 많은 페이지 폴트 발생
• 스레싱을 중지하기 위해서 다중 프로그래밍 정도를 낮춰야 한다
• 스레싱 방지하기 위해서는 최소한의 프레임 수를 보장해야 한다
• 작업 집합 모델 : 일정 페이지 참조를 관찰하고 그 안에 들어 있는 서로 다른 페이지 집합을 이용하여 페이지를 할당한다.
• 페이지 폴트 빈도 : 페이지 폴트율의 상한과 하한을 정해 프레임을 할당한다

메모리 압축

프레임을 압축하여 가용 프레임 수를 늘릴 수 있다. 

 

커널 메모리 할당

커널 메모리는 사용자 프로세스를 할당하기 위한 페이지 리스트와 별개로 별도의 메모리 풀에서 할당 받는다

버디 시스템 : 2의 제곱 형태로 할당한다.  서로 인접한 버디들을 쉽게 큰 세그먼트로 합칠 수 있는 장점이 있다. 단 세그 먼트 내에서 단편화가 발생한다

슬랩할당 : 각 커널 자료구조 단위로 메모리 할당 

 

프리 페이징

초기 페이지 폴트를 방지하기 위해서, 필요한 페이즈를 일부 또는 전부를 한번에 메모리에 가져온다. 어던 페이지를 가져와야 하는 지 명확하지 않는 어려움이 있다

 

* 페이지 폴트를 횟수를 줄이기 위해서는 큰 페이지가 좋다