Storage-device Hierarchy
1차 저장소에는 레지스터, 캐시, 메인메모리가 있다. 이들은 모두 휘발성 메모리이고 메인메모리(=RAM)는 주로 동적 랜덤 접근 메모리(DRAM)를 가지고 있다.
우리는 프로그램들과 데이터를 메인 메모리에 영구적으로 넣어두고 싶어 한다. 그러나 주로 많은 시스템에서 2가지 이유로 이것이 불가하다:
- 보통 메인 메모리는 모든 프로그램들과 데이터를 영구적으로 저장하기에 너무 작다.
- 메인 메모리는 휘발성(volatile)이 있다 - 따라서 파워가 꺼지거나 다른 방법으로 콘텐츠들을 잃어버리게 된다.
그래서 많은 컴퓨터 시스템이 메인 메모리의 확장인 2차 저장소를 제공한다. 2차 저장소의 주 요구 조건은 영구적으로 많은 양의 데이터를 저장 가능한가이다.
가장 흔한 2차 저장 기기는 하드디스크 드라이브(HDD)와 비휘발성 메모리 디바이스(nonvolatile memory)이다.
저장 구조에서 캐시 메모리, CD-ROM, blue-ray, magnetic tapes 등을 포함하는 컴포넌트(component)들도 있다. 이들은 느리고 넓어서 특별한 상태에서만 사용된다. ex) 다른 기기들의 백업 파일들 저장
우리는 이들을 3차 저장소라고 부른다.
Memory Management
프로그램을 실행시키기 위해서는 모든 명령들은 메모리 안에 있어야한다. 또한 프로그램에게 필요한 모든 데이터는 메모리 안에 있어야 한다.
메모리 관리는 무엇이 언제 메모리 안에 있는지 결정한다.
- CPU 성능과 유저들에게 응답하는 컴퓨터를 관리한다.
운영체제는 메모리 관리와 관련된 다음의 행동들을 해야 하는 책임이 있다:
- 메모리의 어느 부분이 현재 사용되고 있는지, 누가 그것을 사용하는지 추적한다.
- 메모리 내부 및 외부로 이동할 프로세스(또는 그 일부) 및 데이터를 결정함.
- 필요에 따라 메모리 공간 할당 및 할당 해제.
Protection
메모리 공간을 분리하려면 프로세스가 액세스 할 수 있는 논리적 주소의 범위를 결정하고 프로세스가 이러한 논리적 주소에만 액세스 할 수 있도록 보장하는 기능이 필요하다.
프로세스는 오직 그들의 주소들과 그들의 주소 공간에만 접근할 수 있다.
우리는 이러한 보호(protection)를 한 쌍의 base register와 limit register들을 사용함으로써 프로세스의 논리적 주소 공간을 구분할 수 있다.
여기서 기본 레지스터는 가장 작은 합법적인 물리적 메모리 주소를 보유하며, 한계 레지스터는 범위 크기를 구체화한다.
Logical v.s Physical Address Space
- 논리적 주소: CPU에서 생성된 주소 = 가상 주소
- 물리적 구소: 메모리 유닛에서 보이는 주소
- 실행-시간 주소-바인딩 체계는 서로 다른 논리적 주소와 물리적 주소를 생성한다.
- 연산-시간과 로드-시간 주소-바인딩 체계는 주소가 같다.
- 논리적 주소 공간: 프로그램에서 생성된 모든 논리적 주소의 집합
- 물리적 주소 공간: 이러한 논리 주소들에 대응하는 모든 물리 주소들의 집합
-실행-시간 주소-바인딩 체계는 서로 다른 논리적 주소와 물리적 주소 공간을 생성한다.
Memory-Management Unit (MMU)
- 가상 주소에서 물리적 주소로의 런타임 매핑은 MMU라는 하드웨어 장치에 의해 수행된다.
Variable Partition
Multiple-partition allocation(다수의 파티션 할당)
- 멀티프로그래밍은 파티션 개수가 제한이 되어있다.
- 가변 분할(variable partition)은 효율성을 위해 만들어진다. (주어진 프로세스의 필요 부분만큼)
- 구멍(hole): 사용가능한 메모리 블록; 다양한 크기의 구멍들이 메모리 안에 흩어져 있다.
- 프로세스가 도착하면, 메모리 할당을 충분히 수용 가능한 크기의 구멍을 받는다.
- 프로세스가 나가면 파티션을 비우고, 인접한 여유 파티션들이 합쳐진다.
- OS는 할당된 파티션들과 비어있는 파티션들(구멍)에 대한 정보를 유지한다.
그러면 도착한 프로세스가 들어갈 메모리공간이 부족하면?
1. 프로세스 거절하고 에러 메시지 출력
2. 대기 큐에 넣어놓기
일반적으로 메모리 블록들은 다양하게 흩어져 있다. 프로세스가 메모리가 필요하다고 하면, 시스템은 구멍 집합에서 구멍을 찾아준다. 만약 구멍이 너무 크면 2개로 나뉜다. 하나는 프로세스를 주고, 나머지는 구멍 집합들에게 돌려준다. 프로세스가 끝나면 메모리 블록을 풀어주면, 다시 구멍 집합에 돌아간다. 만약 새로운 구멍이 다른 구멍과 인접하면 큰 거로 합쳐진다. 이런 과정을 Dynamic Storage-Allocation Problem(동적 저장소-할당 문제)이라고 한다.
즉 얼마나 비어있는 구멍들의 리스트로부터 사이즈 n을 만족 신가에 대한 문제이다.
first-fit: 충분히 큰 먼저 나오는 구멍을 할당한다. 처음부터 시작하거나 전에 찾았던 위치에서부터 시작할 수 있다.
best-fit: 충분히 큰 구멍 중 가장 작은 구멍을 할당한다; 가장 잘 맞는 사이즈를 할당하게 된다 = 사이즈별로 정리되어 있지 않는 한, 모든 리스트를 찾아야 한다.
worst-fit: 가장 큰 구멍을 찾아 할당한다. 당연히 모든 리스트를 찾아야 하고, 분할되어 나오는 큰 구멍을 만들어준다, best-fit에서 나오는 분할된 구멍보단 유용하다.(크니까)
Fragmentation(파편화)
External Fragmentation(외부 파편화): 총 메모리 공간이 요청을 만족시킬 만큼 존재하나 연속적이지 않다 = best-fit, first-fit
- 프로세스가 메모리에 올라갔다 내려갔다 하는 과정에서 큰 구멍이 여러 개의 더 작은 구멍들로 나뉘기 시작한다. 즉, 실제 사용 가능한 메모리가 작은 구멍들이 나뉘어서 송송 뚫려있으니 연속된 메모리 크기는 작다. 최악의 경우엔 모든 프로세스 사이마다 구멍이 있는 경우 공간이 충분해도 프로세스를 더 실행을 못 라게 된다.
- 최초 적합을 통계적으로 분석해 보니 최적화를 해줘도 N 개의 블록을 할당하면 0.5 N 개의 블록이 파편화로 놀고 있는 메모리가 된다. 즉, 전체 메모리의 3분의 1이 놀게 되는데, 이걸 50퍼센트 규칙 50-percent rule이라 부른다.
Internal Fragmentation(내부 파편화): 할당된 메모리가 요청된 메모리보다 조금 더 클 수도 있다; 크기 단위에 따라 할당한 메모리와 요구한 메모리 간의 차로 발생된다.
Compacrion(압축): 외부 파편화에 대한 해결책 중 하나. 즉, 구멍이 생기면 내버려 두는 게 아니라, 위치를 바꿔줘서 언제나 구멍은 하나만 존재하게 해주는 것이다.
물론 이게 언제나 가능한 건 아니다. 주소 재배치가 동적이거나 실행 시간 동안 끝나야 한다. 재배치가 정적이어서 어셈블리 단, 혹은 로드 시에 발생하면 압축이 불가능하다. 주소가 동적으로 재배치되었다면 프로그램과 자료가 이사를 가도 주소(베이스 레지스터) 이전만 제대로 신고하면 상관없으니까.
압축이 가능하면 우선 그 비용을 알아야 함. 가장 간단한 압축 알고리즘은 프로세스를 메모리의 한쪽으로 몰고, 구멍은 반대쪽으로 모는 것이다. 그러면 엄청 큰 메모리 구멍이 생긴다.(비싸다)
Pagigng
- paging을 사용하면 프로세스의 물리적 주소 공간이 연속적이지 않을 수 있다; 프로세스는 다음 것들이 가능해질 때 물리적 주소에 할당된다.
- 외부 파편화 문제 해결
- 다양한 크기의 메모리 청크 문제 방지
- 페이징 구현의 기본은 물리 메모리를 (고정된 크기의 블록) = frame으로 나누고 가상 메모리를 (이와 동일한 크기의 블록) = page로 나눈다.
- 프로세스를 실행하려면 프로세스의 페이지를 프로세스가 있는 곳(파일 시스템이나 보조 기억 장치)에서 사용 가능한 메모리 프레임에 적재한다. 보조 기억 장치는 메모리 프레임과 동일한 고정된 크기의 블록 혹은 여러 프레임의 군집으로 나뉜다. 예를 들어 가상 주소 공간이 이제 물리 주소 공간이랑 분리되어 있으니, 시스템이 264 바이트의 물리 메모리 밖에 없어도 프로세스가 가상 64비트 주소 공간을 가질 수도 있음.
- N 사이즈의 page들을 가진 프로그램을 실행시키려면, N개의 여유 frame을 찾아 프로그램을 로드시켜야 한다.
- 내부 파편화 문제는 해결 불가
- page table을 가상 주소를 물리적 주소로 변환시키기 위해 준비한다.
Address Translation Scheme
- CPU가 생성한 모든 주소는 페이지 수 page number(p)와 페이지 오프셋 page offset(d)로 나뉨:
Page number(p) - 물리적 주소 안에 있는 각 페이지들의 기본 주소를 포함하고 있는 page table를 인덱스로 사용된다.
Page offset (d) - 메모리 유닛에 보내진 물리적 메모리 주소를 정의하기 위해 섞여있는 기본 주소
- 주어진 가상 주소 공간은 2의 m제곱이고 페이지 크기는 2의 n제곱이다.
MMU가 CPU가 생성한 가상 주소를 물리 주소로 변환할 때 다음 단계를 거침:
- 페이지 수 p 구하여 페이지 테이블의 색인으로 삼음
- 페이지 테이블에서 이 색인에 대응하는 프레임 수 f 구함
- 가상 주소의 페이지 수 p를 프레임 수 f로 교체
페이지 수는 프로세스 당 페이지 테이블 page table에 대응하는 색인으로 사용함. 위의 그림 참고. 페이지 테이블은 물리 메모리의 각 프레임의 베이스 주소를 갖고 있으며, 오프셋은 참조하는 프레임에서의 위치를 의미함. 즉, 프레임의 베이스 주소와 페이지 오프셋을 합쳐서 물리 메모리 주소를 알 수 있음. 메모리의 페이징 모델은 다음 그림을 참고:
Shared Pages
- 페이징의 장점 중 하나. 공동으로 사용된 코드를 공유할 수 있다.
- 공유된 코드:
1. 읽기 전용(reentrant 재진입가능) 코드의 복사본을 프로세스를 통해 공유한다.
2. 같은 프로세스 공간을 공유하는 멀티 스레드들과 비슷하다.
3. 읽기-쓰기 페이지들의 공유가 가능하면 IPC에게 유용하다.
- 개인 코드와 데이터
1. 각 프로세스는 따로 코드와 데이터의 복사본을 갖는다.
2. 개인 코드와 데이터를 위한 페이지들은 가상주소 공간에서 어디든 존재할 수 있다.
Virtual memory(가상 메모리)
가상 메모리: 물리적 메모리로부터 떨어진 유저의 논리적 메모리
1. 프로그램의 부분만 실행을 위해서 메모리 안에 있어야 한다.
2. 따라서 논리적 주소 공간은 몰리적 주소 공간보다 더 넓을 수 있다.
3. 주소 공간들을 여러 프로세스들로부터 나뉘게 한다.
4. 더 효율적인 프로세스 생성을 하게 한다.
5. 프로그램들을 더 연속적으로 돌리게 한다.
6. 입출력이 프로세스들을 로드나 스왑이 덜 필요하게 한다.
가상 주소 공간: 얼마나 메모리 안에 프로세스들이 저장되어 있는지의 논리적 시각
1. 주소 0으로부터 주로 시작하고, 공간의 끝까지 연속적으로 주소가 있다.
2. 한편, 물리적 메모리는 페이지 프레임에 정리되어 있다.
3. MMU는 반드시 가상에서 물리로 맵핑해야 한다.
Demand Paging
- 실행할 프로그램을 보조 기억 장치에서 메모리로 올리는 방법 중 하나는 프로그램 전체를 물리 메모리에 올리는 건데, 전체 메모리가 올라오기 때문에 필요하지 않은 메모리도 올라오게 된다. 그래서 필요한 페이지만 올리는 demand paging이 있다.
:프로그램 실행 중에 추가적인 페이지를 요구할 때만 페이지를 적재해 준다. 즉, 접근하지 않은 페이지는 절대로 메모리에 올라갈 일이 없음.
- 효율적으로 메모리를 사용 가능하다.
- 유효한 상태는 연관된 페이지가 합법인 페이지이면서 메모리 위에 있다는 의미로 사용하고, 비트가 설정되지 않았을 때, 즉 무효 상태는 페이지가 유효하지 않거나(즉, 프로세스의 가상 주소 공간에 속하지 않음) 유효하긴 한데, 현재 보조 기억 장치 안에 있다는 의미로 사용한다.
- 메모리에 올린 페이지 테이블 엔트리는 기존과 같지만, 현지 메모리에 없는 페이지는 엔트리에 단순히 무효하다고 표기만 해주면 된다.
Valid-Invalid bit
각 페이지 테이블 엔트리에는 valid-invalid 비트라는 추가적인 비트가 붙어있다. 이 비트가 valid이면 관련된 페이지는 프로세스의 논리적 주소 공간에 있고 그에 따라 legal(or valid) 페이지가 된다. 만약 비트가 invalid로 설정되어 있다면, 페이지는 프로세스의 논리적 주소 공간에 없다는 것이다. 운영체제는 이 비트를 각 페이지마다 붙여 넣음으로써 페이지에 접근을 허용할지 말지 정한다.
이번에는 비트가 "valid"로 설정되면 관련 페이지가 legal이고 메모리 안에 들어간다. 비트가 "invalid"로 설정되면 페이지가 유효하지 않거나(즉, 프로세스의 논리 주소 공간에 없음) valid 하고 현재 보조 저장소에 있다.
메모리에 가져온 페이지의 페이지 테이블 엔트리는 평소처럼 설정되지만 현재 메모리에 없는 페이지의 페이지 테이블 엔트리는 단순히 무효로 표시된다. 이 상황은 그림 10.4에 나와 있다.
(해당 페이지에 대한 액세스를 시도하지 않을 경우 페이지를 무효로 표시하는 것은 효과가 없다.)
