OS

<운영체제> CHAPTER 6 교착 상태 교착 상태(Deadlock) -> 둘 이상의 프로세스가 각자가 가지고 있던 자원을 보유한 채로 외부적 조치가 없는 한 영원히 그 상태에서 기다리고 있는 상황 교착상태의 문제점 -> 1. 프로세스가 더 이상 실행되지 못 하여 사용자에게 응답해주지 못 한다. 2. 보유된 자원들이 교착 상태에서 벗어나기 전까지는 전혀 활용되지 못한다는 점이다. 교착상태와 무한대기의 차이점 -> 무한 대기가 교착 상태와 다른 점은 오랜 시간 후에라도 무한 대기로부터 벗어나 외부적 조치가 없어도 서비스를 받을 수 있다는 것(무한 대기는 운영체제 상 처리 규칙이 한 쪽으로 치우쳐 있기 때문에 생김) 자원이란? (자원의 분류) 소프트웨어 -> 데이터, 메세지 // 하드웨어 -> 하드 디스크, 드라이브, 메모리, CPU 선점 -> 운영체제에 의해 사용 도중 뺏길 수 있는, 다른 프로세스에게 할당해주었다가 다시 원래의 프로세스에게 할당해줄 수 있음 // 선점 불가능 -> 사용 도중 뺏을 수 없음 – 공유하면 여러 데이터가 섞일 수 있으니까 선점 자원을 활용하는 이유 -> 다중 프로그래밍의 성공을 위해, 선점 불가능 자원을 활용하는 이유 -> 시스템의 정상적인 진행을 위해 순차적 재사용 가능(Serially Reusable) -> 먼저 할당된 자원이 사용 후 반납되었을 때 자원 자체는 계속 존재하여 또 다른 프로세스에게 할당이 가능함) – CPU, 메모리, 테이프, 하드디스크, 버퍼, 프로그램 // 소모성(Consumable) -> 사용 후 사라지는 자원 // 시그널(Signal) -> 일시적으로 생성되었다가 사용 후 없어짐 - 메세지 프로세스는? 실행 중인 프로세스가 자원에 대해 취할 수 있는 행동은 두 가지가 있다. 1. 필요한 자원에 대한 요청을 할 수 있다. 이 때 다시 두 가지의 경우가 발생한다. (1) 요청된 자원이 사용 가능하면 이 자원을 사용하면 되고 (2) 다른 프로세스가 사용 중이라면 반납되어질 때까지 대기 상태로 기다려야 할 것.(대기 프로세스는 자력으로 그 상태에서 벗어날 수 없다.) 2. 사용이 끝난 자원을 반납할 수 있다. 자원에 대한 요청과 반납은 실행 중인 프로세스가 System call을 함으로써 운영체제에 의해 이루어진다. 교착 상태의 원인은? 교착 상태는 4가지 조건들이 모두 갖춰질 때 발생하게 되고 만약 이 중에 하나라도 부정할 수 있다면 교착 상태는 발생하지 않는다. 1. 자원의 배타적인 사용 -> 자원이 한정적이더라도 모두 공유가 가능하다면 교착 상태는 발생할 수 없다. (but 바람직 하지 못 하다. 상호배제가 엉망이 될 수 있기 때문에, 근본이 흔들릴 수 있기 때문이다. so, 이 조건을 break 해서 교착 상태를 깨진 않는다. ) 2. 자원의 부분 할당(Partial Allocation) -> 필요한 자원을 일부분씩 확보, 실행해 나가다가 어느 시점에 할당이 불가능한 자원 때문에 이미 확보한 자원들을 소유한 채 대기 상태가 되어버리는 과정을 겪으면서 교착 상태에 빠질 가능성을 높이는 것이다. (이걸 피하려고 자원을 한 프로세서가 다 가져가서 할 수 있으나 다른 프로세서가 일을 못하므로 안 된다. ) 3. 자원의 선점 불가능성 -> 선점이 불가능한 자원을 억지로 선점이 되도록 하면 자원들은 대기할 필요가 없으므로 교착 상태라는 것은 없앨 수 있다. 허나 JOB이 엉망이 되니 결국, 자원의 선점 불가능성을 고수할 경우 교착 상태의 원인이 되는 것을 알 수 있다. 4. 자원에 대한 환형 대기 (Circular - Wait) -> 프로세스들이 자신의 자원은 보유한 채로 서로 상대방의 자원을 요청하고 결과적으로 대기 상태가 되어버리는 일련의 과정에서 교착 상태가 발생 가능하다. (Cycle) 옛날에는 교착 상태가 생기면 해당 프로세스를 kill하거나 Rebooting 해서 해결했다. 하지만 세월이 지나면서 분산 또는 병렬 처리가 일상이 되면서 교착 상태에 대해 보다 깊은 관심과 연구가 필요할 수 밖에 없게 됐다. 예방기법(4가지 원인을 하나씩 없앰) 1. 자원의 배타적 사용 조건을 배제 -> 모든 자원을 공유 가능 자원으로 하여 교착 상태의 발생을 차단하겠다는 것인데 그럴 수가 없는 프린터나 테이프 장치 등은 프로세스들이 차례로 사용해야되기에 이 조건을 배제하여 교착 상태를 예방하기는 불가능하다. 2. 자원의 부분 할당을 배제 -> 부분 할당을 배제한다는 말은 모두 할당하겠다는 말이다. 즉, 프로세스들은 각자 자신이 필요한 모즌 자원을 미리 할당받아 실행을 시작하도록 하는 방법이다. 그러나 이는 모든 자원이 확보되지 못 한 프로세스는 대기상태에 있게 된다는 것과 같다. 즉, 일부 자원만 확보되면 시작할 수 있음에도 불구하고 모든 것을 할당 받을 때까지 기다려야 하고, 할당이 가능했던 일부 자원들은 사용되지 못해 낭비되는 현상이 발생하게 되는 것이다. 또 다른 문제점은 무한 대기를 겪게 될 프로세스가 발생할 수 있다는 점(아까 할당이 가능 했던 자원 중 몇 개가 그 동안 다른 프로세스에게 할당. 실행을 계속 늦출 수밖에 없음.) 3. 지원의 선점 불가능을 배제 -> 모든 자원이 선점 가능하도록 할 경우, 비정상적인 종료와 함께 심할 경우 처음부터 다시 시작해야 하는 불이익을 받게 되는 것이며, 이 말은 지금까지 해왔던 일들이 모두 무효가 되는 것. 4. 자원의 환형 대기 상황을 배제 -> 사이클을 형성하여 교착 상태가 됌. if) 만약 자원을 일직선 상에 순서를 정해놓는다면? 그래도 무한 대기를 피해갈 수 없다. 순서를 지켜야 하기 때문에 당장 필요없는 자원을 먼저 할당 받아야 하고, 실제로 필요한 자원을 확보하기 위해 지금 당장 필요 없는 순서상의 하위 자원들을 확보하느라 많은 시간을 보내야 함.  가장 큰 문제점 : 자원의 심각한 낭비, 특정 프로세스의 무한 대기 가능성 회피 기법(예방 기법에서는 교착 상태의 발생 조건을 배제하는 방식, 회피 기법은 다른 알고리즘.) 1. 안전 상태 -> 시스템에 있는 모든 프로세스가 유한(Finite) 시간 내에 정상적으로 종료될 수 있는 상태. 반대는 불안전(Unsafe) 상태. 안전 상태는 교착 상태가 발생할 수 없는 상태를 말하고 불안전 상태라고 해서 교착 상태임을 말하는 것은 아니지만 교착 상태로 갈 가능성이 있으며 그럴 경우 방지책이 없다는 것을 의미한다. 결국, 회피 기법은 시스템의 상태가 안전 상태로만 가도록 지속적으로 제어해주는 것. 은행가 알고리즘이 제대로 작동하기 위해서는 시스템에 대한 몇 가지 가정이 요구된다. (1) 시스템 내의 프로세스 수가 고정되어 있어야 한다. (2) 자원의 수 역시 고정되어 있어야 한다. (3) 각 프로세스가 요구할 자원의 최대 개수가 알려져야 한다. (4) 각 프로세스는 할당받은 자원을 사용 후 반드시 반납해야 된다. 현실적으로 1, 3번같은 경우 지켜지기 힘들어서 은행가 알고리즘은 교착 상태를 말할 때 이론적인 접근의 방편으로 언급된다. 2. Dijkstra의 Banker's 알고리즘 프로세스 현재 보유량 최대 요구량 P1 1 4 P2 4 6 P3 3 8 여유량 2 얘는 안전하다. P2먼저 시작하면 P1, P3도 가능하니까. 결국, 안전 상태의 판단은 "현 상태에서 모든 프로세스가 정상적으로 종료할 수 있는 길이 적어도 하나 이상 있는가"에 달려있다. 프로세스 현재 보유량 최대 요구량 P1 1 4 P2 4 6 P3 3 8 여유량 1 얘는 어떤 프로세스도 자신의 최대 요구량에 이르지 못하는 상태가 된다. 알고리즘의 요지는 표에서 P1, P3의 자원 요청은 그 결과가 불안전 상태이므로 할당해 주지 않고, P2의 요청을 받아들임으로써 시스템의 상태를 안전 상태로 계속 유지해 나가는 것이다. Habermann의 알고리즘도 있다. 탐지기법 교착 상태의 발생이 허용되고 이것을 어떤 방법으로 찾아내어 적절한 대응을 하겠다라는 것. 탐지 프로그램이 알 수 있는 적당한 형태로 시스템 내에 표현되어 있어야 할텐데 그게 바로 자원 할당 그래프(Resource Allocation Graph, RAG)라고 부른다. 운영체제가 관리하는 모든 자원들은 그들에 대한 정보가 프로그램이 처리할 수 있는 형태로 저장되어 있다.(Table, Array, Vector, Matrix, List) RAG의 이론 1. RAG는 방향성(Directed) 이분(Bipartite) 그래프이며 노드(Node, vertex)와 에지(Edge)들로 이루어져 있다. 노드들은 프로세스와 자원을 표현하며 에지들은 프로세스와 자원들 간의 할당과 대기 상황을 나타낸다. 프로세스 노드를 동그라미로, 자원 노드를 네모로 표현하고 자원 -> 프로세스는 할당되었다는 의미이고 그 반대는 그 자원으로 인해 대기 상태 또는 요청중임을 나타낸다. so, 이 두 가지 경우로 나눠질 경우 RAG로 교착 상태를 탐지하는 방법이 어려워지므로 요청 중이라는 상황이 생기지 않게 시스템이 바로 대처하면(즉시 할당 상태(Expedient State)) 할당 아니면 대기로만 나눠져 탐지 작업이 용이하다. 2. RAG에서 자원 노드는 그 자원의 타입을 나타내고 그 안의 작은 동그라미는 자원의 개수를 나타낸다. 3. 한 자원 형에는 자원의 개수를 나타내는 정수가 있으며 임의의 노드 A로부터 B로 향하는 에지의 개수는 |(a, b)|로 나타낸다. 이렇게 RAG에 대한 그래프 제거(Graph Reduction)법으로 교착 상태를 탐지하게 되는 것이다. RAG에서 자원으로 향하는 에지가 없는 프로세스란 활동 가능한 프로세스이며 이를 unblocked process또는 Sink라고 부른다. 이런 프로세스들은 자원에 대한 요청이나 반납을 실행할 수 있으며 이로써 RAG도 실행시킬 수 있다. RAG의 모든 싱크에 할당된 자원을 모두 반납하면 이전에 대기가 되었던 프로세스들이 싱크가 될 수 있을 것이다. 이 작업을 계속 하여 RAG의 모든 싱크에 대해 에지가 모두 제거되어 버리면(Completely Reducible) 교착 상태가 없다고 판단하게 되며, 만약 지워지지 않는 엣지가 있다면 프로세스들이 교착 상태에 빠져있는 것으로 결론이 난다. 어떤 싱크로부터 어떤 순서로 제거해 갈지에 대해서는 똑같으니 걱정하지 않아도 좋다. 그림 6.4에서 R1형과 R2형은 각각 2개와 1개의 자원을 가지고 있고 현재 싱크는 R3밖에 없으므로 P3로 향하는 엣지를 제거하고 그 결과 반납되는 자원을 P2에게 할당해 준다면 P2가 싱크가 되어 다시 에지들이 제거될 수 있을 것이다. 그림 6.5에는 P2에서 R1으로 향하는 에지가 2개 보이는데 이것은 R1형의 자원 2개가 필요하다는 요청을 나타낸다. 그리고 얘는 P3가 반납해봤자 P2를 싱크로 만들어주지 못하기때문에 애초에 RAG에 교착 상태가 있다는 것을 탐지하게 된다. 탐지 기법에 사용되는 또 다른 방법이 있다. 그래프 탐색(Search)방법이다. 요청 후, 대기 상태가 될 때 교착 상태가 형성시킬 가능성이 있는데, 이 때의 대기 상황을 나타내는 에지로부터 방향을 따라 경로를 탐색해보면 두 가지 결론이 가능하다. 탐색 도중 싱크가 발견되면 교착 상태는 없다고 판단한다. 두 번쨰로 노드 자신으로 되돌아오는 사이클이 발견되면 교착 상태가 된 것으로 판단할 수 있다. (모든 자원 형이 한 개씩의 자원을 가질 경우다. 그렇지 않을 경우의 사이클 발견은 단지 교착 상태의 가능성을 높이는 필요 조건일 뿐이다.) // 모든 가능 경로를 탐색해도 싱크가 발견되지 않는다면 교착상태가 있다는 것 한 자원형에 다수 개의 자원이 있을 경우에는 knot라는 자료 구조의 발견이 곧 교착 상태의 발견이 된다. 복구기법 교착 상태로부터 벗어나기 위한 방법. 두 가지 방식으로 나뉜다. 1. 프로세스 종료(Process Termination) 방식 -> 교착 상태를 형성한 프로세스 중 몇 개를 강제로 종료시켜 이들로부터 반납된 자원으로 복구하게 되는데 문제는 어떤 프로세스들을 종료시킬 것인가이다. 종료 비용(Termination cost – 강제 종료되는 프로세스가 잃게 되는 양으로부터 산출되는 비용)을 따져 종료 비용이 최소인 프로세스 부터 종료시켜 나간다. 조금 다른 방법으로는 가능한 모든 부분집합을 만든다. 최소의 비용이 드는 부분집합에 속하는 프로세스들을 한꺼번에 종료시키는 방식을 취하기도 한다. 종료 비용의 잣대는 프로세스의 우선순위나 종류, 실행된 시간의 크기, 남은 시간, 실시간 등등 이다. 비교적 간단하나 비용을 계산하기가 번거롭다. 2. 자원의 선점에 의한 방식 -> 프로세스들이 요구하는 자원이 지금 남아있다면 교착상태에 빠지지도 않았을 것이 자명하므로 그 자원들은 이미 누군가에 의해 사용 중이라는 말이 된다. 결국 선점하여 프로세스에게 줘야된다. 선점 시의 최소 비용을 따져야 된다. 프로세스의 강제 종료는 그 동안의 일을 없었던 것으로 하고 처음부터 다시 해야 하기 때문에 복구 비용을 키우는 주요인이 되며 시스템의 입장에서는 큰 낭비 요인이다. 낭비를 줄이기 위한 방법으로 검사점 지정(Checkpointing) 과 재시작(Restart)을 들 수 있다. 검사점은 중간 중간에 그 시점까지의 실행결과를 보존하고 표시한다. 가장 최근의 검사점부터 하나씩 되돌리는 것이고 이 과정에서 교착 상태를 되돌릴 수 있다면 최종적으로 되돌려졌던 검사점에서 보존된 내용으로 재시작을 할 수 있게된다.. CHAPTER 7 메모리 관리 프로그램이 실행되기 위해서는 메모리에 올라와 있어야 한다. 따라서 메모리를 잘 관리하면 프로그램의 실행 성능을 높여 CPU의 효율적인 사용과 사용자에게 빠른 응답성을 가능하게 하므로, 운영체제의 효과적인 메모리 관리는 당연히 요구되는 일이다. 그리고 이 장에서는 프로그램이 나눠지지 않고 연속적으로 적재되는 경우를 다룬다. 7.1 메모리 구성과 관련하여 정해져야 할 것들은? 다중 프로그래밍의 정도(Multiprogramming Degree) -> 한 번에 하나의 사용자 프로그램만이 메모리에 있을 수 있도록 할 것인가, 아니면 여러 개의 프로그램이 같이 있도록 할 것인가. (여기서 정도란 메모리에 있는 프로세스의 개수) 그리고 정도 n일 경우에는 메모리 분할을 어떻게 하느냐에 따라 프로세스에 다르게 부여할 수 있다. 메모리의 분할을 미리 정해두고 고정적으로 운영할 경우 고정(Fixed) 또는 정적(Static) 분할이라고 하고, 미리 정해두지 않고 프로세스의 크기나 개수에 따라 변동시켜 나갈 때를 가변(Variable) 또는 동적(Dynamic) 분할이라 한다. 고정분할의 경우, 각 프로세스가 들어갈 분할을 지정하고 항상 그 분할로 적재할 것인지, 아니면 상황에 따라 다른 분할로의 적재도 가능하도록 할 것인지를 결정해야 한다. (프로세스가 시스템에 있는 동안 메모리와 디스크 사이를 오갈 수 있으니까.) 프로그램과 프로세스의 차이 프로세스란 실행하고자 하는 내용을 담고 있는 프로그램과 정상적인 실행을 위해 시스템으로부터 제공돼야 하는 제반 환경을 묶어 부르는 말. 프로그램이란 프로세스를 형성하는 한 축을 담당함. 즉, 프로그램은 실행 때 필요한 데이터를 자연스럽게 포함한다. 7.2 메모리의 관리는? 1. 적재 기법 (Fetch Strategy) 언제 메모리에 할당할 것인지. 두 가지가 있다. 요구(Demand) 적재 -> 적재의 요구가 있을 때 (대부분) 예상(Anticipatory) 적재 -> 적재의 요구가 있을 것으로 예상하고 미리 적재함. 2. 배치 기법 (Placement Strategy) 프로세스들을 메모리 공간의 어디에 적재할 것인가. 위에서 말한 고정 분할(지정된 분할로만 적재)과 가변 분할. 3. 교체 기법 (Replacement Strategy 메모리 공간이 부족할 경우 새로 적재돼야 할 프로세스를 위해 이미 메모리에 있는 프로세스 중 어떤 것을 골라 디스크로 내보내고 공간을 확보할 것인지. 4. 할당 기법(Allocation Strategy) 프로세스에게 메모리 공간을 얼마 정도로 줄 것인가를 결정하는 것(지금은 프로그램 전체를 수용할 수 있는 크기로 줌) 7. 3단일 프로그래밍 단일 프로그래밍이란 한 번에 하나의 프로세스만이 메모리에 적재되고 실행이 종료되면, 다음 프로세스가 적재되는 시스템을 말한다. 메모리에서 커널이 차지하는 공간을 제외한 나머지 전부가 하나의 프로세스에게 주어지게 된다. 프로세스가 차지하고 남은 공간은 종료할 때까지 낭비될 것이다. 메모리의 크기가 적재할 프로그램의 크기보다 크거나 같으면 문제가 없지만, 그렇지 않을 경우 프로그램의 일부분만을 먼저 적재하여 실행시킨 다음 나머지 부분들 다시 적재하여 실행을 이어가는 방식 -> 오버레이(Ovelay) 방식 프로그램의 실행 중 커널 영역을 침범하지 못하도록 하는 보호 기법 -> 경계 레지스터 경계 레지스터에 커널과 프로그램의 경계 주소 값을 넣어두고, 프로그램이 실행되면서 참조하는 메모리 주소 값이 이 경계 값을 침범할 경우 트랩으로 실행을 중지시키면 될 것이다. (운영체제를 손상시킬 가능성 방지) 고정 분할에서의 다중 프로그래밍 메모리를 여러 개의 분할로 나누어 놓고, 각 분할에는 하나의 프로세스만을 수용하도록 함으로써 다중 프로그래밍을 구현하는 방식. 이미 정해진 분할은 고정이므로 크기와 개수가 변하지 않고, 이 때의 다중 프로그래밍 정도의 최대치는 분할의 개수와 같게 될 것이다. (고정함으로써 갖는 이점은 관리의 쉽고 편리함, 오버헤드가 적다는 것. 단점은 다양한 상황에 유연하게 대처하지 못하는 점이다. -> 유연함은 복잡도를 동반한다.) 프로그램들이 컴파일될 때 주소지정이 이루어지는 경우, 메모리 할당은 절대 로더에 의해 언제나 지정된 분할로 들어가도록 될 것이다. 비어있으나 활용되지 못 하는 다른 분할들의 낭비를 자초하게 될 것이므로 재배치(Reloactable) 번역과 로더를 사용하여 비어 있는 어느 분할로도 들어갈 수 있도록 해주는 게 타당하다. 이렇게 해도 여전히 고정 분할이 가지는 문제는 무엇일까? 가장 큰 분할보다 더 큰 프로그램의 수용을 할 수 없다는 것. 이것은 오버레이 방법으로 해결할 수 밖에 없다. 그리고 메모리 보호에 있어서 단일 프로그래밍 때보다 좀 더 주의를 요구하는데, 사용자와 커널 사이 뿐만 아니라 사용자와 사용자 사이에도 침범하지 못하도록 해야 한다. 분할1의 사용자와 빈자리까지 합친 분할 하한, 분할 상한까지 경계 레지스터가 있다. 고정 분할이 가지는 또 하나의 문제는 메모리 공간의 단편화(Fragmentation)이다. 분할 내에는 프로세스를 수용하고 남는 공간이 있기 마련이다. 이런 공간은 낭비될 수 밖에 없으며 이를 분할 내의 낭비 공간이라는 의미에서 내부(Internal) 단편화라고 부른다. 분할의 크기 자체가 작아서 프로세스를 아예 수용하지 못 하면 이 때는 외부(External) 단편화라고 부른다. 운영체제 과제에 있던 것 -> 워드 단위로 참조되고 있는 page 시스템 내애서 내부단편화가 일어나지 않는 page size가 존재할까? 존재한다. 말 그대로 사이즈를 1워드로 한다면 조각조각 나눠져 모든 프로그램을 수용할 수 있으나 실질적으로 그 페이지에 따른 페이지 테이블을 다 만들어줘야되기 때문에 매우 비효율적이라 현실적으로 불가능하다. 7.5 가변 분할에서의 다중 프로그래밍 가변 분할이란 분할의 시기와 개수 그리고 크기가 사전에 정해진 바 없이, 프로세스를 수용할 때 그 크기만큼 메모리 공간을 할당해 줌을 말한다. 다중 프로그래밍의 정도를 조절할 수 있으며 내부 단편화를 방지할 수 있지만, 관리가 복잡해짐으로 해서 생기는 오버헤드는 감수해야 한다. 사용 중인 공간과 빈 공간에 대한 리스트의 헤더포인터(Header Pointer)를 각각 used와 free로 부르고 K는 커널이 차지하는 공간이다. (Linked list로 연결되어 있다.) free를 탐색해 적재가 가능한 빈 공간을 찾을 때 어떤 노드를 선택할 것인가는 위에서 말한 배치기법이며 다음과 같은 것들이 있다. 1. 최초 적합(First - fit) free 리스트의 첫 노드부터 시작하여 제일 먼저 발견되는, 요구되는 크기보다 더 큰 빈공간을 가지는 노드에서 할당해주고 탐색을 마친다. 2. 최적 적합(Best - fit) free 리스트를 끝까지 탐색하여 요구되는 크기보다 더 크되, 그 차이가 제일 작은 노드를 찾아 할당해 주는 방법이다. 3. 최악 적합(Wosrt - fit) free 리스트를 끝까지 탐색하여 요구되는 크기보다 더 크되, 그 차이가 제일 많이 나는 노드를 찾아 할당해 주는 방법이다. 최초 적합은 Free 리스트에 대한 탐색을 중간에 끝낼 수 있으나 최적과 최악은 끝까지 탐색해야 하므로 시간적 부담이 크다. 최적에서는 가장 들어맞는 노드를 찾음으로써 큰 빈 공간을 가지는 노드들을 그대로 유지시킬 수 있다. 그러나 남는 크기는 매우 작을 것이고 이런 빈 공간들은 이 후의 적재에 거의 활용되지 못하는 단점을 가진다. 홀(Hole) -> 빈 공간이기는 하지만 크기가 아주 작아서 실제로는 할당될 가능성이 희박하고 결과적으로 낭비되는 공간.(외부 단편화의 대표적인 예) 최악적합은 할당 후 남는 크기도 비교적 큰 빈 공간이 되도록 하여 이후의 적재 요구에 대비하겠다는 의도임을 알 수 있다. 대부분 최초가 최적보다 실행 속도가 빨라 최초 적합을 사용하면 되겠다. 그러나 최초적합은 적재 가능성을 항상 리스트의 처음부터 따져나가 노드의 크기가 점점 작아지는데 이런 문제의 보완은 free 리스트를 순환 구조로 한 다음, 할당이 가능한 노드가 선택될 때마다 헤더 포인터를 이 노드 다음으로 옮기게 하는 방법이 있다. (next - fit) 하지만 이 또한 어쩔 수 없이 대부분 홀이 되는데 실제로 메모리의 3분의 1이 홀이 된다. 결국 작은 빈 공간을 합쳐 더 큰 빈 공간을 만드는 작업이 요구되는데, 언제 어떻게 합칠지에 따라 다음과 같이 두 가지로 분류될 수 있다. 인접한(Adjacent) 빈 공간의 병합(Coalescing) 빈 공간으로 반납될 때 인접한 빈공간이 있다면 이들을 합쳐 좀 더 큰 빈 공간을 만들어 주는 방식이며, 프로세스가 메모리를 반납할 때마다 실행되고, 인접한 공간이 비어있지 않다면 병합하지 않는다. 빈 공간 전부의 통합(Compation) 흩어져 있던 빈 공간들을 전부 합쳐 하나의 큰 빈 공간으로 만든다. 병합과는 달리 사용중인 공간의 위치 이동이 발생하며 이것은 메모리에 있는 모든 프로세스들의 주소 재배치를 의미하므로 상당한 시간을 요구한다. 또한 통합이 진행되는 동안 모든 프로세스들의 실행이 중지되므로 시스템에 있는 자원들 역시 상당 부분 낭비될 것이다. 메모리의 관리에서 고정 분할과 가변 분할을 타협한 절충안을 생각해 볼 수 있다. 이를 버디(Buddy) 메모리 관리라 한다. 프로세스의 적재 요구가 있을 때 메모리는 요구한 크기보다 크되, 차이가 가장 작게 나는 2의 승수(power) 크기로 분할되어 할당되며, 이 때 같은 크기로 분할된 인접 공간을 버디라 부른다. 내부 단편화가 발생하나 고정 분할보다는 나아질 수 있다. 반납되는 빈 공간은 분할 시에 정해졌던 자신의 버디가 빈 공간일 때 병합되어 크기를 2의 배수로 늘려나간다. 버디 시스템은 고정과 가변의 절충이나 그 자체가 메모리 관리 기법으로 사용되기에는 여전히 부족하다. 하지만, 버디로 관리하는 아이디어는 병렬프로그래밍에서 활용될 수 있고, 실제로 이 아이디어를 보완하여 UNIX에서 커널에 할당되는 메모리를 관리할 때 사용되기도 한다. 오늘날, 프로그램의 일부를 비 연속적으로 할당하여 실행하고 있다. 이렇게 할 경우 다중 프로그래밍의 정도를 높여 결과적으로 시스템 성능을 향상시킬 수 있으며, 아무리 큰 프로그램도 수용하여 실행시킬 수 있게 된다! CHAPTER 8 가상 메모리 운영체제는 주어진 메모리의 크기 아래서 프로그램을 작은 조각으로 나누어 그 중에 일부분만을 메모리에 적재하되, 그것도 적재가 가능한 곳으로 흩어 (비연속적) 넣어줌으로써, 사용자는 메모리에 대한 고민으로부터 벗어날 수 있게 되는 것이다. So, 많은 사용자를 수용할 수 있고, 더 중요한 것은 모든 사용자가 메모리의 크기로부터 자유로울 수 있게 된다. 제한적인 크기지만 엄청나게 큰 메모리가 있는 것처럼 여겨지기 때문에 가상(Virtual) 메모리라고 부른다. 8.1 가상 메모리(Virtual Memory)를 위해서는 모든 프로그램은 작은 조각들로 나눠지는데, 조각들의 크기를 모두 같도록 하면 한 조각을 페이지(Page)라 부르고, 서로 다르게 하면 조각들 각각을 세그먼트(Segment)라 부른다. 페이지든 세그먼트든 그 크기가 메모리와 디스크 사이에서 한 번에 전송되는 전송 단위(Block)가 된다. 가상 메모리 관리에서 페이지로 나누었을 때는 페이징, 세그먼트로 나눴을 때는 세그먼테이션 시스템이라고 한다. 가상 메모리 관리를 위해 가장 먼저 해결되어야 할 부분은 주소(address)의 사상(Mapping)이다. 프로그램에서 참조하는 주소를 가상 주소(Virtual address), 실제 메모리상의 주소를 실주소(Real address)라 한다. 주소를 지정할 때 몇 가지 경우가 있다. 1. 주소의 지정이 컴파일 시에 이루어질 때. 참조하는 주소가 실주소가 되어 프로그램은 항상 메모리의 지정된 곳으로만 적재되어야한다는 것과 같다.(고정 분할과 절대 로더의 경우다) 주소의 사상이 필요없지만 두 주소가 아예 같으므로 융통성이 배제된다. 2. 재배치의 경우. 메모리의 위치를 적재될 때마다 바꿀 수 있으나 프로그램 전부가 통째로 연속적으로 메모리에 적재되어야 한다는 전제를 가진다. 프로그램의 첫 번째 줄을 0번으로 하고 여기에 Offset을 더해 얼마나 떨어져 있는지를 나타낸다. 즉, 실주소 = 시작주소(MMU – 재배치 레지스터가 갖고있음) + 상대주소(Relative Address) 이다. 그러나 프로그램이 조각나고 이 조각들의 메모리 적재가 연속적이지 않다며 쓸모 없게 된다. 3. 프로그램들이 디스크에 조각난 모양으로 적재. 메모리에 비연속적으로 다른 프로그램들의 조각들과 섞여 적재된다. 프로그램에서 참조하는 주소, 가상주소는 참조하고자 하는 명령어나 변수 등이 자신의 프로그램 내에서 몇 번째 조각에 있으며, 그 조각 내에서 어느 위치(Offset)에 있는지 알려준다. 예를 들어 프로그램에 goto 10이라는 명령어가 있다면 컴파일 된 후, goto 10은 실행코드의 형태, <3, 5>로 바뀌게 된다. 즉, 세 번째 조각의 5번째 위치(Offset)에 있다는 소리! (세 번째 조각의 5번째 위치면 사실상 <2, 4>가 된다. 첫 위치가 0이니까) 8.2 페이징(Paging) 페이징을 위해서는 모든 프로세스들이 같은 크기의 조각들로 나뉘어야 하는데, 이 때 한 조각을 페이지라 부른다. 메모리 역시 프레임(Frame)이라 불리는, 페이지와 같은 크기로 나누어져 있으며 일련 번호가 매겨져 있다. 한 프로세스의 전체 페이지들은 디스크에 저장되고, 이 중 몇 개가 메모리에 비연속적으로 다른 프로세스들의 페이지들과 섞여 적재된다. 그리고 이중에 디스크와 메모리를 오가며 교체되는 단위가 페이지이고 이게 곧 사상의 단위가 된다. OS는 가상주소를 실주소로 변환하기 위해 프로세스당 하나의 페이지 테이블을 만들어 두어야 하는데 이게 페이지 사상 테이블(Map table)이라 부르며 이 테이블의 크기는 해당 프로세스의 페이지 개수에 비례한다. k개의 페이지를 가지는 프로세스의 페이지 테이블은 k개의 엔트리(Entry)로 구성되고 엔트리 하나의 크기는 보통 4B로 잡는다. 엔트리에 들어 있는 정보는 우선, 이 페이지가 메모리에 적재되어 있는가를 나타내는 존재(Residence) 비트로서 적재된 경우 1, 아닐 경우 0의 값을 갖는다. 존재 비트의 값에 따라 1의 경우에는 적재되어 있는 프레임 번호를, 0의 경우 이 페이지가 저장되어 있는 디스크의 주소를 나타내는 필드(Field)들이 각각 있다. 존재 비트가 1일 경우 가상주소 = 페이지 번호(p) + 페이지 내에서의 위치(d) p * 엔트리 크기 + 기준 레지스터 값(a) -> 프레임 번호(f) f * 페이지 크기 = 이 프레임의 시작주소 프레임의 시작주소 + d = 실주소에 접근 페이지 테이블은 메모리의 커널 영역에 보관되며, 실행 중인 프로세스의 페이지 테이블 시작 주소는 페이지 테이블 기준 레지스터(Page table Origin Register)에 들어있다. 존재 비트가 0일 경우 페이지가 메모리에 없음을 말하므로 디스크 주소로부터 이 페이지를 메모리에 적재해야 된다. 그 다음 엔트리의 존재 비트를 1로 바꾸고 적재된 프레임 번호를 기입한 후 사상을 계속 진행하면 실 주소를 얻게 된다. 페이지 테이블들을 모두 메모리에 보관하기 힘들면 몇 개는 디스크에 두게 된다. 페이지 테이블을 메모리에 두는 이유는 가상 주소의 사상을 위해 먼저 페이지 테이블에 접근 후, 알아낸 실주소를 가지고 실제 워드에 접근을 하니까 즉, 두 번의 메모리 접근이 요구된다. so, 이 시간을 줄이기 위해 기본적으로 사상이 요구될 가능성이 높은 테이블들은 디스크가 아니라 메모리에 두어야 한다. 8.2.1 TLB(Translation Lookaside Buffer)의 사용 TLB는 고속 캐시의 일종으로, 주소로 접근되는 일반 메모리와는 달리 키(Key)값으로 찾고자 하는 워드를 동시에 접근하는 연관 메모리로서 검색이 빠른 반면 비싼 하드웨어다. 용량을 크게 할수록 좋기야 하겠지만 가성비를 따져 페이지 테이블의 일부 엔트리만 수용하는 게 좋다. 최근에 빈번하게 검색된 엔트리들을 TLB에 넣되, 페이지 번호(p)를 키 값으로 동시 검색을 하므로 TLB에 저장되는 각 엔트리는 페이지 번호도 함께 표시되어 있어야 한다. 가상주소의 p를 키 값으로 먼저 TLB부터 검색하며 해당하는 f가 있다면 바로 실주소로 간다. 검색되는 엔트리들의 페이지는 모두 메모리에 적재되어 있으므로 존재 비트를 확인할 필요가 없다. 만약 검색에 실패하면 페이지 테이블에서 사상이 진행되고 그 엔트리는 TLB에 추가된다. 꽉 차면 교체가 필요하다. TLB가 겁나 크다면 여러 프로세스의 일부분도 같이 넣어둘 수도 있으나 엔트리 들이 페이지 번호와 함께 프로세스의 번호도 가지게 해야되고 검색 시의 키 값 역시 두 개를 사용해야 된다. TLB의 검색 성공 확률을 적중률(hit ratio)라 한다. 책에 뭐라뭐라 있다. 1. TLB -> 2. 페이지테이블 -> 3. 페이지 부재 8.2.2 페이지의 보호(Protection)와 공유(Sharing) 페이지 테이블의 각 엔트리에 해당 페이지에 대한 보호 비트(Protection bits)를 두어 허용되는 접근을 설정할 수 있다. 예를 들어, 쓰기 작업에 대한 보호비트의 값이 1이면 이 페이지에 대한 쓰기가 허용되고 0이면 트랩을 일으킨다. 페이지의 주소 공간 보호는 offset의 크기가 페이지의 크기를 넘지 않으면 안전하다. 다수의 사용자가 한 부의 응용 프로그램을 공유하여 실행한다는 것은 공유 프로그램 내에서 각자의 실행 위치가 다른 한편, 사용되고 만들어지는 각자의 데이터는 자신들의 주소 공간에 가지도록 한다는 말이다. 이 때 공유되는 프로그램은 코드의 내용이 실행 도중 변하지 않아야 하므로 재진입 코드로 컴파일 되어있다. 페이징에서의 공유는 프로세스 각자의 페이지 테이블에서 엔트리에 같은 프레임 번호를 가지도록 함으로써 쉽게 구현할 수 있다. 페이지는 프로그램 즉, 명령어 코드가 들어 있는 코드 페이지와 데이터가 들어있는 데이터 페이지로 나눌 수 있다. 코드 페이지는 명령어를 가지므로 가상주소를 참조하는 반면, 데이터페이지는 그럴 일이 없다는 것이다. 코드페이지가 공유되기 위해서는 재진입 코드여야 하고, 공유된 데이터 페이지에 대한 쓰기는 5장에서 배운 상호배제의 해결을 전제해야 된다. 보면 공유되는 코드 페이지의 위치는 같은데 이는 당연한 것이다. 어떤 프로그램이 실행하는 프로세스에 따라 명령어가 접근하는 주소가 달라진다는 경우는 있을 수 없다. 즉, 공유되는 페이지의 위치는 다른 프로세스 더라도 goto 명령어를 실행했을 때 모두 같다! 8.2.3 페이징에서 사상 테이블의 구성 32비트를 사용해 주소를 표현하는 시스템에서 하위 12비트를 offset으로 사용한다면, 페이지의 크기는 2^12이 되고 페이지 크기는 4Kbyte 가 되고 사상 테이블은 최대 100만개 2^20의 엔트리를 가질 수 있을 것이다. 엔트리의 크기를 4Byte로 잡더라도 페이즈 테이블의 크기는 4Mbyte가 되므로 매우 큰 크기가 되어 메모리에 모두 저장하기에는 벅차게 되므로 페이지 테이블을 작게 나누어 필요한 부분만을 메모리에 적재하기 위해 계층 구조를 갖도록 구성할 수 있다. 20비트를 10비트씩 나누어 상위 10비트는 루트 페이지 테이블의 엔트리 위치로, 하위 10비트를 나누어진 테이블 내의 엔트리 위치를 나타내도록 하면 어떨까? # 상철이 os 1. 전원을 키고 바탕화면이 나오기까지의 과정을 설명하자(카카오) - **운영체제도 하나의 프로그램이다.** 1. 전원 킴 2. BIOS - mother보드에 꼽혀있는 걸 다 확인함. 문제가 있으면 실행을 안함. 3. 부트로더 이미지를 메모리로 복사 4. OS 이미지를 메모리로 복사 5. 보호모드로 전환 2. 커널과 쉘의 차이가 무엇인가 1. 쉘은 사용자와 대화하는 것. CMD같은 느낌. 2. 커널은 하드웨어와 통신. 3. 쉘이 있는 이유는 커널과 직접적으로 통신하게 되면 커널에 영향을 끼칠수도 있기 때문에. 3. 인터럽트 vs 트랩 vs System call 1. 인터럽트같은 경우는 하드웨어와 커널 간의 통신. 또한 인터럽트는 모든 예외를 다 설명하기도 한다. 2. 트랩은 자바나 C에서 제로 나누기. 소프트웨어적인 문제들. 3. 시스템 콜은 function에 해당. 시스템에 자원에 해당할 때 4. 컴파일러와 인터프리터의 차이 1. 컴파일러는 다 읽고 한방에 실행. 실행하기 까지 오래걸리지만 실행하고나서는 빠름. 한방에. 기계어로 한방에 꼽아서 속도가 빠르다. 대신 한방에 모든 걸 처리해야되기 때문에 2. 인터프리터는 고레벨 -> 중간레벨 -> 행마다 실행. 파이썬, 자바스크립트, 자바. 인터프리터는 보안에 좋다. 한줄씩 하다가 문제가 있으면 막기 때문에. 5. 컴파일 과정을 설명해보시오 1. 소스 프로그램이 들어오면 object module을 링커로 뽑고 동적으로 할당하게 되면 다이나믹 링크로 뽑는다. 6. 파이썬의 print와 C의 printf시 일어나는 것을 각각 고르시오(시스템콜, 인터럽트, 트랩) 1. 다 시스템 콜 2. C언에서는 write라는 시스템 콜이 일어난다. (strace라는 걸로 알아볼 수 있다) 3. 파이썬에서는 C로 일어나느 포팅 위에 일어난다. open C하고 나서... write. 7. 자바의 컴파일 과정을 설명해보시오 1. .java - javac - .class(byte) - jvm - jit - run 2. 한줄씩 자바 인터프리터를 해서 느렸지만 jit 컴파일러를 써서 엄청 빨라졌다. 3. JVM이 동적 할당이나 그런 것들. 8. 아래의 코드가 어떻게 메모리에 올라갈까 -> 하드가 어떻게 돌아가는지. int main(void) 1. 메모리 코드 영역에 .java 파일이 올라가고 코드를 읽는다. 2. 전역/정적 변수들이 데이터 영역에 올라간다. 3. main 함수가 스택에 들어간다. go에 넣는 1이 지역변수로 main 스택에 같이 올라간다. 4. 힙 영역이 왜 위고 스택 영역이 왜 아래인가. 힙 영역은 5. 스택은 높은 주소에서 시작해서 내려온다. 9. 프로세서와 프로그램의 차이 1. 파일 시스템은 .exe 2. 프로세스는 cpu 메모리에 올리고 나서 프로그램이 돌아가고 있는 상태. 3. 운영체제가 프로세스를 만들고 그 안에 스레드가 있다. 프로세스가 어떤 흐름을 가지고 있다. 10. 멀티 프로세싱 vs 멀티 테스킹 vs 멀티 스레딩 1. 단어를 명확하게 아는 게 좋다. 2. 프로세스가 여러 개 인게 멀티 태스킹 그 중에서도 나눠지면 멀티 스레딩 3. Connection pool. JVM에서 스레드로 나눠서 DB에 접근 4. 크롬탭은 하나당 프로세서로 관리한다. 5. 네이버 D2 Hello world에 보면 아주 잘 나와있다. 11. CPU에서 작업 연산은 어떻게 이루어지는가? 1. JOB큐에 할당되는 게 있다. 라운드로빈 방식이 보통적인 CPU 방식 2. 근데 이걸 넓게 보는 게 좋다. 3. 그러면 쿼드 코어에서는 어떻게 이루어지는가? 1. 싱글 CPU의 쿼드코어에서는 바로 4개로 바로 넘어가버린다. 4. 그러면 쿼드 코어의 CPU가 3개가 있으면 어떻게 되는가? 1. 마스터 CPU가 있고 슬레이브 CPU가 있다. 12. GPU와 헥사코어는 어떻게 처리되는가? 1. GPU는 계속 병렬로 더해지기만 한다. 머지 소트 느낌으로 분할해서 들어가고 리턴해서 값이 나온다. GPU 연산이 뭔가. 병렬처리는 어떻게 되는가 13. 커널 레벨 스레드 VS 유저 레벨 스레드 1. 커널이 각 스레드를 알고 있다. 2. 유저 레벨 같은 경우. 커널이 봤을 때는 프로세스 하나다. 프로세스는 알아서 작동. 14. 장기, 중기, 단기 스케줄링 1. **모르면 안 됨.** 2. 프로세스를 스케줄링 하기 위한 queue에는 세 가지 종류가 존재한다. 1. job 큐 : 현재 시스템 내에 있는 모든 프로세스의 집합 2. ready 큐 : 현재 메모리 내에 있으면서 CPU를 잡아서 실행되기를 기다리는 프로세스의 집합 3. device 큐 : Device I/O 작업을 대기하고 있는 프로세스의 집합 3. 장기 스케줄러 1. 메모리는 한정되어 있는데 많은 프로세스들이 한꺼번에 올라올 경우, 디스크에 임시로 저장. ready 큐로 보낼지 판단. 4. 중기 스케줄러 1. 여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아낸다. 대기하는 상황이 오면 block. IO작업이 생각보다 길다. 메모리는 소중하기 때문에 디스크로 옮긴다. 2. 좋은 책들은 suspend가 있다 5. 단기 스케줄러 1. 당장에 running할지 결정. 바로 앞에 있는 프로세서를 어떻게 처리할 것인가. 15. CPU 스케줄링을 선점, 비선점 한 개씩 설명해보라. 1. 비선점 : 프로세스가 끝날 때까지 CPU를 잡고 있다. 선점할 수 없음. FCFS, **SJF** 2. 선점 : CPU를 빼앗아 실행시킨다. **SRT, RR,** Priority S 1. 굵은 글씨는 짧은 job만 해서 나이job하는 게 기아상태로 옴 16. 에이징이란 무엇인가 1. 영원한 기아상태를 없애기 위해서 17. 동기 vs 비동기 1. 카페 유명한 예시 2. 자바는 동기. 동기는 느리다. 일하는 있는 시간동안 대기해야된다. 3. 자바스크립트는 비동기. 비동기는 일하는 시간 동안 다른 일은 수행 가능 4. blocking, non blocking. 18. context switching 1. 인터럽트 2. pc스택과 커널 스택. 근데 이건 투머치. 19. 임계영역 20. 뮤텍스 vs 세마포어 vs 모니터 1. 다 물어본다. ds 사업부에서도 물어봤다. 2. 자바 개발자를 할 거라면 모니터를 알아두는 게 좋다. 3. 세마포어가 2개면 2명이 들어갈 수 있다. 4. 뮤텍스는 Lock. 0아니면 1이다. 화장실로 비유. 5. notify나 wait을 통해서 쉽게 임계영역을 관리할 수 있다. 6. 쉽게 할 수 있는 게 모니터다. 21. 데드락 vs 스핀락 1. 데드락 : 서로가 서로한테 내놓으라고 해서 걸리는 거. 상호배제, 점유대기, 비선점, 순환대기 1. 데드락을 피할 수 있는 것. 예방, 회피, 탐지 - 회복, 무시. 은행원 알고리즘. 윈도우는 무시를 택하고 있다. 그래서 블루스크린이 뜬다. 블루스크린이 한 번 뜨면 계속 뜬다. 2. 스핀락 : 22. 식사하는 철학자 1. 포크를 2개를 들 수 있을 때만 든다고 하면 한 명은 무한한 기아상태에 빠진다. 데드락을 설명하는 좋은 예시다. 23. 은행원 알고리즘 - 면접에서 물어본 사람이 없음 1. 교착 상태를 회피. 2. 미래를 보는 것. 얘한테도 할당해도 교착상태가 안 일어나네? 3. 하지만 미래를 본다는 것에 대한 부하가 크다. 24. IPC가 무엇인가? 1. 프로세서와 프로세서의 통신. InterProccess Communication 2. TCP/IP. 4계층에서 이뤄지는 게 IPC. 3. 커널을 통해서... 25. IPC의 종류와 특징을 말해보시오 1. 파이프 1. 통로를 만들어서 값을 꼽는다. publish subscribe. 백엔드 개발자라면 해야됨 2. 메세지 1. 3. 공유메모리 1. 크롬에 해당하는 부분. 4. 대부분 어려운 기술이라 파이프라인을 쓴다. 26. RPC란? 1. Remote Procedure Call 1. IPC 안에 RPC가 있다. 2. 팀뷰어 같은 얘들. 27. PCB 블록에 대해서 설명해보세요 1. PCB가 스케줄링의 단위다. 2. 명세가 PCB에 해당한다. 3. pointer. process state, process number, register, code area 등등... 28. 메모리의 구조는? 1. 레지스터, 캐시, 메모리, 하드디스크 2. 이 계층 사이에 캐시가 모두 있다. 그래서 하드웨어와 커널 간의 속도 차이를 극복할 수 있다. 3. 프로세스 생성 시 메모리에 어떻게 올라가는가? 1. fork(), exec() 2. exec()는 다 갈아 엎고 다시 시작. 3. fork()는 아예 복사. 4. 운영체제에 들어가면 무조건 만난다. 5. 리눅스의 구조와 똑같다. init -> PID 2, 4... 얘들을 fork함. 4. bash에서 echo같은 얘들이 이런 식으로 되어있다. 29. 고정 메모리 vs 가변 메모리 1. 내부단편화와 외부단편화 2. 가변 메모리일 때 30. 가상메모리(**매우 중요하다**) 1. MMU, TLB, Frame - 물리 메모리를 사용하는 최소 크기 단위, Page - 가상 메모리를 사용하는 최소 크기, Swapper - 프로세스 메모리 관리 2. TLB(Hit / Miss) 3. 물리 메모리에 없으면 물리 메모리로 땡겨옴(이게 trap). 4. 페이지크기가 커지면 어떻게 되고 작으면 어떻게 되고(네이버 면접) 5. 페이지를 희생시킴 - victim page. 페이지의 스케줄링. 6. 쓰레싱 7. 가상메모리를 쓰면 포인터로 관리하게 된다. 31. 페이징 vs 세그먼테이션 1. 페이징은 고정적인 크기만큼 찍어낸다. 2. 세그먼테이션은 내부단편화를 막기 위해서 자주 변경되는 얘들을 위해서...? 32. DMA / spooling / RISC / CISC / RAID 1. 메모리에 바로 access하는 게 DMA 2. raid를 저장할 때 보는 방식. 33. HardLink / SymbolicLink / iNode 1. 심볼릭이 바로가기 2. 데이터를 가지고 있는데 iNode 1. AWS 프로시저를 돌렸을 때 어떻게 되는가