지난 포스팅에 이어서 그 이후의 내용을 정리하려고 했지만, 우선 memory chapter에 대해서 다루도록 하고
주말에 따로 정리해서 올리도록 하겠습니다.
memory chapter는 제 '컴퓨터 구조' 카테고리를 확인해보면 간략하게 정리된 부분을 확인해볼 수 있습니다.
Mono programming이란 운영체제에서 사용하는 메모리 관리 방식 중 하나로, 한 번에 하나의 프로그램만 메모리에 적재되어
실행되는 방식입니다. 메모리에 동시에 오직 하나의 프로그램만 올라와서 실행될 수 있으며
다른 프로그램들은 해당 프로그램이 끝날 때까지 대기해야 합니다.
당연히 단점으로 만약에 프로그램이 작은 상태라면 메모리의 일부만 사용하게 되므로 메모리 사용 효율이 낮아지고,
다른 프로그램들은 현재 실행중인 프로그램이 종료될 때 까지 기다려야 하기 때문에 멀티테스킹이 불가합니다.
하지만 현재 저희는 여러가지 프로그램들을 실행시킵니다. 게임을 하면서 노래를 틀기도 하고, 인터넷을 하기도 합니다.
현재 사용하는 방식에서 메모리에는 당연히 여러가지 프로그램이 올라갈 수 있어야 하고
이를 Multiple Programming이라고 부릅니다.
하지만 Multiple programming으로 인해서 멀티태스킹을 할 수 있어서 좋지만, 문제가 발생하게 됩니다.
(a)를 Program A, (b)를 Program B라고 했을 때, 두 프로그램은 (c)와 같이 프로그램이 메모리에 적재하게 됩니다.
(a)를 보면 ADD의 주소가 28번지이고 (b)프로그램 또한 CMP라는 Instruction이 28번 주소에 있습니다.
또한 (b)에서 JMP Instruction을 이용해서 28번지의 CMP로 점프를 하게 되는데, (b)만 두고 보면 문제가 없지만
(c)와 같이 메모리에 적재된 상태에서는 문제가 발생하게 됩니다.
분명히 JMP 28을 하면 CMP Instruction이 실행되어야 하는데, (c)에서 보면 28번지에는 (a)프로그램의 ADD가 있기 때문에
의도하는 것과 같이 프로그램을 수행할 수 없게 되는 문제가 발생합니다.
위와 같이 문제가 발생하는 것을 Protection(다른 메모리 영역을 침범)이라고 하며, 이를 해결하기 위해서
Base and Limit Register를 사용하여 protection 문제를 해결할 수 있게 됩니다.
또한 Relocation문제라는 것이 발생하는데, 여러 프로그램이 동시에 메모리를 차지하고 있으므로 항상 동일한
위치에 로드될 수 없습니다. 하지만 프로그램이 어디에 위치시키든 해당 주소를 재조정해야 하기 때문에 해당 주소를
재조정하고 Relocation 문제를 해결하기 위해서 virtual address를 사용하게 되는 것 입니다.
그렇다면 Relocation문제는 어떻게 해결할 수 있을까요?
프로그램이 로딩될 때 static allocation으로 Relocation문제를 해결할 수도 있습니다.
쉽게 이야기해서 프로그램이 로딩될 때 미리 주소에 맞춰서 변환된 주소를 Instruction에 넣어주는 것 입니다.
또 다른 방법으로는 Dynamic Relocation이 있고, 이 방법이 아래의 그림과 함께 설명될 Base and Limit Register입니다.
위의 그림은 Base and Limit Register를 적용한 그림입니다.
Base register는 0번지에 있던 명령어 주소가 16384로 shift한 것을 표현한 것으로 Base register와
기존의 주소를 모두 더해주면 실제 적재된 메모리에서의 address가 나오게 됩니다.
그리고 프로세스의 다른 메모리 영역을 JMP등 branch문으로 침범하면 안되기 때문에
프로그램의 사이즈를 Limit register에 넣어주게 되면 Base and Limit register를 이용해서
protection과 Relocation문제를 해결할 수 있게 됩니다.
그렇다면 만약에 Limit register를 넘어가는 주소가 나오게 되면 어떻게 될까요?
답을 먼저 말하자면, protect violation fault가 발생하게 됩니다.
쉽게 이 과정을 거친다고 생각하시면 됩니다.
그리고 Base register와 Limit register는 program switch에 의해서 program A에서 program B로 넘어간다면,
Base register와 Limit register의 값을 program B에 맞는 주소들을 할당해주고, 만약 Program A가 Blocked된다면
Base와 Limit register의 주소들은 PCB에 저장되게 됩니다.
지금까지 물리메모리에서 monoprogramming multiple programming의 특징과 메모리에 적재할 때 발생하는
문제점을 해결하기 위해서 Base and Limit register를 이용하는 방법에 대해서 배워보게 되었습니다.
그렇다면 메모리는 한정된 공간이 있는데, ready 상태일 수도 있는 Process와 running 상태인 Process가
메모리에 적재되어 있다면 어떻게 될까요? 당연히 문제가 생기게 됩니다.
해당 문제를 해결하기 위해서 Process를 Blocked 처리를 하여 Disk에 적재하게 됩니다.
이 때 만약에 Base and Limit register의 방법을 사용하고 있다면 Swapping이라는 개념을 사용하여 Disk에 적재하게 됩니다.
Swapping을 이용할 때에는 Process의 모든 공간들을 다 같이 한꺼번에 내보내게 됩니다.
당연히 한번에 내보내는거지 왜 당연하지 않다는 듯이 이야기하지?라는 생각이 드실 수 있지만,
나중에 virtual address개념을 사용할 때에는 paging을 사용하기 때문에 부분적으로 내보낼 수 있습니다.
위는 memory allocation을 표현한 그림입니다.
(e)에서 Base and Limit register를 이용한다면 프로그램 A가 다시 메모리에 들어올 수 없습니다.
아까 이야기했듯이 나가고 들어올 때 한번에 모든 사이즈만큼의 주소가 들어갔다가 나올 수 있어야 하기 때문입니다.
그리고 위에 빗금친 영역은 Fragmentation라고 이야기하며 파편화라고도 합니다.
본론으로 돌아와서 (e)와 같은 상황에서 프로그램 A를 실행해야 한다면 어떻게 해야 할까요?
방법은 compaction을 이용하는 것 입니다.
예를 들어서, compaction은 (e)에서 C와 B를 앞으로 당겨서 A가 들어갈 공간을 만들어주는 것 입니다.
compaction을 통해서 다른 프로그램들을 옮긴다는 것은 memory를 읽고 쓴다는 것을 의미하기 때문에
오버헤드가 크게 된다는 단점을 가지고 있습니다.
만약에 위의 그림에서 B프로그램이 더 많은 메모리 공간을 사용해야 한다면 어떻게 될까요?
해당 경우는 프로세스에서 Dynamic의 영역인 heap memory와 stack memory 영역은 유동적으로 바뀔 수 있기 때문에
더 필요한 메모리 영역이 발생할 수 있기 때문에 아래와 같이 미리 추가적인 공간을 주어서 할당할 수 있습니다.
해당 여유공간은 사용되지 않기 때문에 메모리를 비효율적으로 사용한다고 생각할 수 있지만
프로그램이 running 상태에서 더 많은 memory공간을 원하게 된다면 Disk나 다른 공간에
옮겨갔다가 다시 추가로 더 공간을 할당을 해야하게 되면 오버헤드가 계속해서 발생할 수 있기 때문에
여유 공간을 두고 memory에 프로그램을 적재하게 되는 것 입니다.
그렇다면 이제 할당되는 방법은 알게 되었으니 OS 코드를 작성해서 메모리를 관리해야 할 때 어떻게 관리를 해야 할까요?
할당되는 공간과 빈 공간을 기록을 해두고 프로그램을 memory에 적재(할당)해줘야 합니다.
해당 공간을 기록해두는 방법론에는 Bit Map과 Linked List를 이용하는 방법이 있습니다.
Bit Map는 간단하게 위의 그림을 보면 쉽게 알 수 있습니다.
(b)는 Bit map을 말하는 것으로 1로 표시된 것은 프로그램이 적재되어 있는 곳을 표시하고, 0은 빈 공간을 표시하는 것 입니다.
그리고 memory를 allocation unit으로 나눠주어 사용하게 됩니다.
만약에 A가 전부 수행된다면 어떻게 될까요?
A의 Process가 memory어디를 차지하고 있는지가 PCB에 표기되어 있고,
해당주소를 Bit Map에서 찾아서 0으로 바꿔주면 됩니다.
여기서 Bit map은 간편하고 좋으니까 아무 문제도 없을까요?
그렇지 않습니다. Bit map은 사이즈에 따라서 trade off관계를 가지게 됩니다.
만약에 사이즈를 줄여서 allocation unit을 byte단위로 설정한다면 Byte를 표시하기 위해서 Bit map의 1bit이 필요하게 됩니다.
$\frac{1}{8}$의 오버헤드가 든다고 생각하시면 됩니다.
여기서 오버헤드가 든다는 것을 보고 어느 부분에서 어떻게 오버헤드가 든다는 것인지 의문이 들 수 있는데,
이 오버헤드는 memory와 관련된 오버헤드입니다.
Bit map은 항상 Physical memory 영역에 저장되어 있어야 하기 때문에 메모리의 영역을 사용하게 됩니다.
그런데 만약 Byte 단위 하나를 표현하고자 1bit의 physical memory 영역을 사용한다면 오버헤드가 크다고 할 수 있습니다.
반대로 1K Byte의 사이즈를 allocation unit이 가진다고 한다면
$\frac{1}{1024*8}$의 적은 오버헤드가 든다고 할 수 있습니다.
하지만 Trade off는 항상 존재하기 때문에 Bit Map이 작다(allocation unit이 크다면)고 무조건 좋다고 할 수 없습니다.
왜냐하면 만약에 A프로그램이 4.1KB라면 allocation unit이 1KB단위이기 때문에 5KB단위로 할당해야 합니다.
여기서 0.9KB라는 사용하지 않는 공간이 생겨서 메모리를 효율적으로 사용하지 못하게 됩니다.
여기서 사용하는 것은 추후에 이야기 하겠지만 allocation unit안에 Fragmentation이 있기 때문에
Internal Fragmentation이라고 합니다.
그래서 위에서는 이야기 하지 않았지만 memory allocation의 프로그램들로 인해서 Fragmentation이 발생하는 것을
External Fragmentation이라고 합니다.
Bit Map은 마지막 단점으로 Bit Map의 전부를 서치해야 하기 때문에 slow operation이라고 할 수 있는 단점이 있습니다.
또 다른 방법으로 Linked List 방법을 살펴보겠습니다.
Linked List는 Physical memory에 존재하지만 Bit Map과 다르게 Dynamic하게 변화할 수 있습니다.
위에 오른쪽 그림을 보시면 이해하실 수 있습니다.
그리고 어떻게 Linked List로 할당하는지 궁금하신 분은 아래 그림을 참고해보시기 바랍니다.
Linked List의 장점 중 하나는 Bit Map과 다르게 allocation unit의 크기를 어떻게 해주더라도 Bit Map과 다르게
큰 영향이 없이 사용할 수 있습니다. 왜냐하면 Bit Map을 줄여주기 위해서 allocation unit의 사이즈를 1K로 해줬지만
Linked List에서는 이를 신경써줄 필요가 없고, 노드의 숫자를 신경써주면 되기 때문입니다.
엄밀히 말하면 Linked List의 노드 숫자가 아닌 사이즈는 신경써줘야 하지만 크게 영향을 끼칠 정도는 아니게 됩니다.
이 부분에 대해서는 다음에 따로 자세히 찾아보도록 하겠습니다.
마지막으로 memory allocation에 대해서 알아보고 마무리 짓도록 하겠습니다.
memory allocation은 다음과 같이 다섯가지의 방법이 있습니다.
1. First fit
맨 앞에서 부터 끝까지 공간을 찾아가며 fit한 곳이 있다면 그 공간에 할당하는 것인데, 문제점은 맨 앞에만 메모리 공간이 없고 뒤
에는 공간이 남기 때문에 메모리를 효율적으로 사용할 수 없게 됩니다.
2. Next fit
맨 앞에 공간만 없어지게 되는 First fit의 방법이 아니라 이전에 채워진 공간 다음 순서부터 빈 공간을 찾아서 할당하는 방법으로
First fit의 단점을 보완하기 위해서 나온 방법입니다.
3. Best fit
만약 두 개의 공간을 차지하는 program이라면 memory 전체를 다 살펴본 이후에 딱 맞는 공간을 찾아서 Fragmentation을
없애기 위해서 사용하는 방법입니다. 단점으로는 맨 뒤까지 찾아봐야하는 문제점이 있고, 남는 공간 중에서 두 개의 공간이 없고
세 개나 네 개의 공간만 남아 있다면 세 개의 공간에 할당해야 하기 때문에 작은 자리만 남게 되고 문제가 생기게 됩니다.
4. Worst fit
위에서 세 개와 네 개의 공간 중에서 세 개의 남은 공간에 할당하여 작은 Fragmentation으로 다른 프로그램이 할당되지 못하게
하는 문제점을 해결하고자 아예 네 개의 공간에 할당하여 어느정도 여유있는 공간을 만들어서 다른 프로그램이 들어올 수 있도록
하자는 아이디어가 Worst fit 방법입니다.
5. Quick fit
가장 많이 사용되는 사이즈의 프로그램 크기 별로 Linked list를 이용해서 묶어내는 것을 말하는 것 입니다.
위의 Best fit, Worst fit, Quick fit에 관한 예시 그림은 아래와 같습니다.
아래는 Quick fit으로 각 사이즈에 맞게 Linked List를 이용한 방법입니다.
글 읽어주셔서 감사합니다.
'전자전기공학 > 운영체제' 카테고리의 다른 글
| [Operating System/운영체제][TLB, Multilevel page table] (0) | 2024.11.03 |
|---|---|
| [Operating System/운영체제][Memory관리,Virtual memory, Paging] (0) | 2024.10.29 |
| [Operating System/운영체제][Synchronization] (0) | 2024.10.14 |
| [Operating System/운영체제][Thread] (4) | 2024.10.08 |
| [Operating System/운영체제][Process] (8) | 2024.10.07 |