[Operating System] Memory Management

 

 

 

RAID는 Redundant Array of Inexpensive(Independent) Disk의 약자로 저렴한 디스크를 여러개 사용해 품질이 좋은 디스크 하나의 효과를 내는 구성방법이다. 

 

개인용 컴퓨터의 디스크는 비교적 저렴한 디스크를 사용해 용량도 적고 하드웨어 신뢰성도 떨어진다.

보통 용량이 큰 디스크는 기업이나 공공기관이 사용한다.

 

RAID가 도입된 시기에는 디스크 용량이 커질수록 가격은 훨씬 더 커졌고, 저용량 디스크를 조합해서 고품질 디스크를 구현하는 RAID 기술이 도입됐다. 

 

 

 

 

 

그림은 디스크 4개를 조합해 RAID 0 (non-redundant)구조를 구현한 예시이다.

 

strip이라는 정보 단위를 저장하고, 각 strip은 여러 디스크에 분산되어 저장된다. 

이렇게 저장하면 디스크 하나가 고장나더라도 각 파일의 1/4 만 잃어버리게 되고, 나머지 내용을 보고 손실된 내용을 일부 복원할 수 있다.

 

 

 

 

 

RAID 1 구성 방법은 RAID 0 모델이 두 개 사용된다.

백업본을 저장한다고 생각하면 된다. 한 세트만 있을 때 보다 신뢰성이 높지만.. 디스크가 많이 사용되니 가격이 비싸진다.

 

 

 

 

RAID 2 구성은 RAID 1과 비슷하게 구성되지만 오류 검출 부분인 Hamming Code를 사용한다. (checksum)

네 개의 디스크에 똑같은 위치에 해당하는 비트를 계산해서 Hamming Code에 저장한다. 

 

 

 

 

Bit-Interleaved 방식은 데이터를 비트 단위로 쪼개서 여러 디스크에 순차적으로 저장하는 방식을 의미한다. 

패리티를 계산할 때도 그 다음 디스크의 같은 위치에 저장한다. 

 

RAID 2에서는 Hamming Code를 사용해 2비트가 잘못된 경우 그 사실만, 1비트가 잘못됐을 때 어떤 비트가 잘못됐는지를 알 수 있지만 오류 검출을 위해 디스크를 더 많이 사용해야 한다는 단점이 있다.

 

 

 

 

RAID 3에서는 Bit-Interleaved Parity를 사용해 패리티 디스크를 하나만 사용한다.

디스크 4개에 흩어져있으니 병렬로 한 번에 읽어올 수 있어 4배 더 빠를 것 같지만, 하나씩 읽고 조합하는 과정이 필요하다.

모든 디스크 중 가장 늦게 읽힌 비트를 기준으로 계산하게 돼 이론상 4배를 기대하지만 그거만큼 성능이 나오지는 않는다. 

 

 

 

 

 

RAID 4에서는 Bit-Interleaved 방식을 사용하지 않고 항상 하던대로 한 디스크에 데이터를 몰아넣는다.

패리티비트는 각 디스크의 물리적으로 동일한 위치의 비트를 읽어서 저장하는데, Bit-Interleaved 방식을 사용하지 않으니 패리티 비트를 만들 때 사용되는 데이터들은 모두 독립적이다. 

 

 

 

 

RAID 5는 RAID 4와 같은 방식이지만 패리티 비트를 모든 디스크에 분산시키는 방식이다.

정보를 한 번에 잃어버리는 상황을 방지할 수 있다. 

 

 

 

 

RAID 6은 기본적으로 RAID 5와 같지만, 홀수 패리티와 짝수 패리티를 모두 계산한다.

 

 

 

 

 

 

요즘은 RAID 0과 RAID 1을 결합한 RAID 01, RAID 10 방식을 사용한다.

RAID 01은 RAID 0두 개를 RAID 1으로 조합하는 방식이고, RAID 10은 RAID 1두 개를 RAID 0으로 조합하는 방식이다.

RAID 10의 성능이 조금 더 좋다. 

 

 

 

---

 

 

 

 

메모리 관리는 프로세스 관리와 밀접하게 연관되어있다.

프로그램을 실행하려면 프로세스를 메인 메모리에 넣어야 한다. 즉, 프로세스에게 메모리 공간을 분배해 줘야 실행할 수 있다.

 

 

 

 

프로세스 A를 위해 5000번지부터 A의 크기만큼 메모리를 배분해줬다.

 

각 메모리 영역은 독립적으로 사용돼야 한다.

프로세스들은 허용된 메모리 영역만 접근할 수 있어야 하고, 운영체제는 프로세스들이 정해진 메모리 영역만 사용하는지 감시한다.

프로그램 실행 전에는 알 수 없고, 명령어를 실제로 실행할 때 CPU가 감시해야 한다.

 

 

Relocation

프로세스가 메모리에서 보조기억장치로 swap out 됐을 때, 추후 swap in 되더라도 꼭 swap out 되기 전의 위치로 가야 할 필요는 없다.

이렇게 relocation 되는 경우 프로그램을 훨씬 더 효율적으로 실행할 수 있다.

위의 사진에서도 A와 B사이 공간이 있는데, B와 C를 relocation 하면 공간을 더 효율적으로 사용할 수 있다.

 

Sharing

 

두 개 이상의 프로세스들이 같은 메모리를 공유하도록 설정한다.

 

fork를 통해 복사되더라도 메모리는 독립적으로 사용하고, 필요한 경우 공유 메모리 영역을 통해 데이터를 공유한다.

 

 

 

 

 

 

 

 

---

 

 

 

 

 

한정된 크기의 메인 메모리 공간을 여러 프로세스들에게 분배하는 방법으로  Pixed Partitioning을 사용한다.

 

운영체제는 메인 메모리를 일정한 크기의 조각으로 분할해 사용자 프로세스가 생성되면 분할해 둔 조각을 프로세스에 할당한다.

 

어떤 프로그램이 현재 몇 번째 조각에 들어있다~ 정도만 기억하면 되니 관리하기 매우 쉽지만, 1MB짜리 프로그램이 메인메모리 8MB를 사용하는 경우가 생길 수 있어 메모리 사용률이 좋지 않다. (Internal Fragment)

 

오른쪽처럼 다양한 크기로 분할해 두는 방법은 Unequal-size partitioning 이라고 부르는데.. 이래도 Internal Fragment 문제는 해결되지 않는다.

 

이런 단점 때문에Dynamic Partitioning이 도입됐다.

 

 

 

 

 

 

 

 

 

Dynamic Partitioning은 가변적으로 그때 그때 필요한 만큼씩 메모리를 할당하는 방식을 의미한다.

Internal Fragment는 발생하지 않지만, External Fragment는 발생한다. 

 

Relocation으로 빈 공간을 한 쪽으로 몰아넣으면 External Fragment가 사라지고 다른 프로세스를 할당할 수 있지만, 메모리를 읽고 쓰는 작업이기에 시간이 오래 걸려 그렇게 좋은 방법은 아니다.

 

 

 

동적 메모리 할당을 수행하기 위해 운영체제는 메모리 이용 상황을 파악하고 있어야 한다.

 

그림처럼 비어 있는 메모리가 몇 번지에서 얼마 만큼 비어있는지를 테이블이나 LinkedList 방식으로 관리해야 한다.

 

메모리를 할당하는 알고리즘으로는 네 가지가 있다.

First-Fit Algorithm

Best-Fit Algorithm

Worst-Fit Algorithm

Next-Fit Algorithm

 

 

 

 

First-Fit Algorithm

크기가 7000짜리 프로세스가 들어온다면 위에서부터 탐색해 제일 처음으로 사용할 수 있는 공간을 사용한다.

 

Best-Fit Algorithm

일단 모든 빈 공간을 쭉 조사하고 사용할 수 있는 공간과 가장 비슷한 공간을 사용한다.

 

Worst-Fit Algorithm

목록을 모두 조사하는건 같지만 크기가 가장 많이 차이나는 공간을 사용한다.

알고리즘을 적용한 후 큰 공간이 남게 되니, 해당 공간을 이용할 가능성이 높아서 사용한다.

 

Next-Fit Algorithm

직전 알고리즘을 수행했을 때 마무리된 위치부터 탐색을 시작한다.

메모리가 골고루 분산될 수 있어 First-Fit 보다 성능이 더 좋다. 

 

 

근데 가변 동적 메모리 할당 알고리즘은 요즘 사용되지 않는다.

 

최신 운영체제는 Buddy System 방식을 사용한다.

Buddy System은 Internal Fragmentation을 허용하는 동적 메모리 할당 방식으로, 앞의 두 방식을 섞어서 사용한다.

 

어차피 사용될 가능성이 적은 작은 메모리는 External Fragment로 관리하게 되면 괜히 메모리 관리용 테이블만 복잡해지니까 아예 저 공간을 그대로 프로세스에게 할당해 Internal Fragmentation으로 사용한다.

 

요즘은 메모리에 어느정도 여유가 생겼으니.. Buddy System은 메모리를 1bit라도 더 아끼는 것 보다는 운영체제의 성능을 끌어올리는 방식을 사용한다.

 

 

 

 

할당할 메모리 크기를 s, 전체 메모리 공간을 2^u 라고 하자.

Buddy System에서는 메모리의 2의 제곱 단위로 할당해주니 2^u-1 < s < 2^u 라면 2^u를 전부 할당해준다.

그렇지 않으면 메모리를 두 개로 나눠 2^u-2 < s' < 2^u-1 을 만족하는지 확인하고, 연쇄적으로 이 조건을 검사한다.

 

메모리를 회수할 때는 옆의 Buddy 공간이 비어있는지 확인하고 비어있다면 하나로 합쳐준다.

 

 

 

 

---

 

 

 

 

Physical Address

메모리 유닛 하드웨어가 사용하는 주소로, 주소가 주어지면 반도체 칩에서 그 위치를 찾아갈 수 있다.

 

Logical Address

명령어를 처리하는 CPU가 사용하는 주소지만..

CPU가 명령어를 실행하려면 Address에 해당하는 Physical Address를 알아야 한다. (physical address translation)

프로그램의 시작점을 기준으로 얼마 만큼 떨어진 곳인지를 표현한다.

 

Virtual Address

가상 주소로 Logical Address와 동일하다.

가상 메모리에서 사용되는 Logical Address를 Virtual Address라고 부른다.

가상 메모리는 보조 기억 장치를 메인 메모리처럼 사용하는 기술을 의미한다.

 

Relative Address

정해진 위치를 기준으로 주소를 매기는 방식이다.

Logical Address도 프로그램의 시작점을 기준으로 설정하니 Relative Address라고 할 수 있다.

 

 

 

 

 

90000번대 주소는 Physical Address로 반도체의 실제 주소를 의미한다.

0 ~ 100 은 프로그램 내부에서 사용하는 Logical Address이자 Relative Address이다.

 

Relative Address는 주소를 매기는 방식이고, 주소를 매기는 방식에 따라 매겨진 주소 자체가 Logical Address이자 Virtual Address이다.

 

compile-tile 바인딩과 load-time 바인딩을 수행했을 때는 Logical Address와 Physical Address가 같지만, execution-time 바인딩을 수행할 때는 두 주소가 다르다.

 

 

 

 

 

 

 

C프로그램을 컴파일하면 실행 파일이 만들어지고, 실행 파일을 실행시키면 보조 기억 장치에 Virtual Address가 만들어진다.

 

 

 

 

 

Virtual Address는 32비트 컴퓨터에서 4GB 공간을 차지한다.

안 쓰는 공간이 있더라도 Virtual Address Space는 총 4GB이고, 실제로 실행될 때는 메인 메모리에 올라가서 실행된다.

Virtual Address Space의 커널과 빈 공간은 실제로 디스크 공간을 차지하지 않는다.

 

실제로 공간을 차지하는 요소는 stack, data, code 뿐인데 여기서 code도 사실 실행 파일에 있는 코드를 공유하기에.. 사실상 stack과 data만 공간을 차지한다. 

 

code는 값이 변경되지 않지만 실행 파일의 stack과 data는 프로그램이 실행되면서 계속해서 변하기 때문에 stack과 data만 복사해서 사용한다.

 

즉, 보조 기억 장치에는 프로세스의 실제 사용 데이터만 저장되기에 몇MB ~ 수백MB 처럼 필요한 만큼만 물리 저장소에 매핑된다.

최대 크기가 4GB라는거지 물리적으로 전부 할당되지는 않는다. 

 

운영체제는 Virtual Address Space 내부 각 영역별 시작 주소와 끝 주소를 PCB에 저장하고 해당 정보가 실제로 디스크에 존재하는 것 처럼 보이게 해 준다.

 

 

 

 

 

0번지부터 3G-1번지 까지는 User Context가 저장되고, 3G번지부터 4G-1번자 까지는 System Context가 저장된다. (합쳐서 Process Context)

 

 

 

 

스택은 code, data와 다르게 커널에 붙어서 아래로 커진다.

stack과 data 사이 공간에 heap을 잡아서 사용할 수 있고, 라이브러리를 포함시켜서 사용할 수 있다. 

brk는 힙의 끝 부분을 나타낸다.

 

 

 

---

 

 

 

Logical Address를 Physical Address로 변환할 때는 Address binding을 수행한다.

명령어 안에는 다른 명령어의 주소나 변수의 주소가 등장하는데, 여기서 사용되는 주소는 모두 Logical Address라서 실제 메인 메모리의 주소가 어디인지를 알아내야 한다.

 

 

 

 

 

Compile Time

소스코드를 바이너리로 변환할 때 Address binding

컴파일 단계에서 해당 프로그램이 몇 번지에서 실행되는지 미리 알고 컴파일러에게 알려준다.

컴파일러는 Logical Address를 만들 때 해당 주소와 동일한 Physical Address를 만들어 해당 주소를 집어넣는다.

Code -> Data 순서로 컴파일하고 변수가 선언될 때 마다 테이블에 기록한다. 

컴파일러를 실행할 때 인자값으로 Base Address를 전달해주니 주소값을 정확하게 알 수 있지만.. relocation 때문에 사용하지 않는다. (swapping)

 

 

 

 

Load Time

프로세스를 메모리에 넣을 때 Address binding

컴파일 할 때는 모르고 메모리에 넣을 때 Logical Address를 Physical Address로 바꿔서 넣어준다.

컴파일 할 때는 주소 정보가 전혀 없으니 상대적 주소를 사용하다가, 메모리에 넣을 때 운영체제가 빈 메모리를 할당해준다. 

여전히 relocation 발생 시 정상 작동하지 않아 사용하지 않는다.

 

 

 

 

 

Execution Time

실제로 프로세스가 실행될 때 Address binding

미지수 값이 있는 상태로 프로세스를 메모리에 넣어준다. 

명령어를 실행할 때 레지스터에 기록해 둔 값을 사용해 시작 주소를 계산한다.

이전 두 방법과 다르게 Logical Address와 Physical Address가 서로 다르다. 

relocation 문제도 해결돼 가장 많이 사용하는 방식이다.

 

 

 

 

 

프로세스 코드 내에 Physical Address가 등장하면 relocation이 제대로 수행되지 않는다.

Execution Time Binding을 사용하면 relocation이 가능하지만.. 주소 변환 작업을 수행할 때 시간 지연이 발생하고, 이 지연을 최소화 하기 위해 하드웨어를 사용한다.

 

 

Base Register에는 해당 프로그램의 시작 주소를 저장하고, Bounds Register에는 프로그램의 끝 주소를 저장한다.

 

Logical Address는 Relative Address로 프로그램이 시작되면 레지스터에 저장된 값과 더해진다.

 

Comparator를 사용해 계산된 주소가 접근 가능한 주소인지 확인하고 범위 내에 있으면 실행하고 범위 밖이면 Segmentation Fault를 뱉는다. (CPU의 인터럽트로 Trap)