Computer Science
-
[OS] Memory ManagementComputer Science/Operation System 2020. 4. 28. 13:59
✔️ 논리적 주소와 물리적 주소 ◾️ 메모리는 주소를 통해서 접근하는 매체이다. ◾️ 메모리 주소는 논리적 주소와 물리적 주소가 있다. ◾️ 논리적 주소 : 프로그램마다 가지고 있는 독자적인 주소이다. ◾️ 물리적 주소 : 실제 메모리의 주소이다. ◾️ 물리적 메모리 아래부분은 OS 커널이 위치한다. 상위 부분은 여러 프로그램이 섞여서 올라간다. ◾️ 프로그램이 실행이 되려면 물리적인 메모리에 올라 가야한다. 이때 프로세스의 논리적 주소가 물리적 주소로 바뀌어야한다. 이를 주소 바인딩이라고 한다. ◾️ Symbolic Address : 변수 등의 심볼로된 주소를 말한다. Symbolic Address는 컴파일 되어 숫자로된 논리적 주소로 바뀐다. ◾️ Complie time binding : 컴파일 시점..
-
Minimum Spanning Tree (Kruskal, Prim)Computer Science/Data Structure and Algorithm 2020. 4. 26. 22:04
✔️ Spanning Tree ◾️ 스패닝 트리는 원본 그래프의 정점 전부와 간선의 부분 집합으로 이루어진 부분 그래프이다. ◾️ 스패닝 트리에 포함된 간선들은 정점들을 트리 형태로 전부 연결해야한다. ◾️ 트리 형태란 간선들이 사이클을 이루지 않는다는 것을 의미한다. ✔️ Minimum Spanning Tree Problem ◾️ 최소 스패닝 트리 문제란, 가중치 그래프의 스패닝 트리 중 가중치의 합이 가장 작은 트리를 찾는 문제를 말한다. ◾️ 즉, 그래프의 연결성을 그대로 유지하는 가장 '저렴한' 그래프를 찾는 문제이다. ✔️ Kruskal's Algorithm ◾️ 크루스칼의 최소 스패닝 트리 알고리즘은 그래프의 모든 간선을 가중치의 오름차순으로 정렬한 뒤, 스패닝 트리에 하나씩 추가해 나간다. ..
-
Union Find, Disjoint SetComputer Science/Data Structure and Algorithm 2020. 4. 24. 17:02
✔️ Union Find ◾️ Union Find는 Disjoint Set(상호 배타적 집합)을 표현할 때 쓰는 트리 자료 구조이다. ◾️ 상호 배타적 집합이란 공통 원소가 없는 배타적 집합을 뜻한다. ◾️ Union 연산 : 두 원소 A, B가 주어질 때, 이들이 속한 두 집합을 하나로 합친다. ◾️ Find 연산 : 어떤 원소 A가 주어질 때 이 원소가 속한 집합을 반환한다. 트리를 이용한 상호 배타적 집합의 표현 ◾️ 두 원소가 같은 집합(트리)에 포함되어 있는지 확인하는 방법은 각 원소가 포함된 트리의 루트가 같은지 확인하는 것이다. 이렇게 하기 위해서는 모든 자식 노드가 부모에 대한 포인터를 가지고 있어야한다. 루트는 부모가 없으므로, 대개 자기 자신을 가리키도록 구현한다. ◾️ 두 트리를 합칠..
-
[OS] DeadLockComputer Science/Operation System 2020. 4. 23. 15:04
✔️ DeadLock ( 교착 상태 ) ◾️ 'DeadLock Example 2'를 살펴보자. ◾️ P0은 A 자원을 가지고 있으면서, B자원을 요구한다. ◾️ P1은 B 자원을 가지고 있으면서, A자원을 요구한다. ◾️ P0과 P1은 DeadLock 상태이다. ✔️ DeadLock 발생의 4가지 조건 ◾️ 상호배제, 비선점, 점유대기, 환형대기 4가지 조건을 모두 만족해야 DeadLock이 발생한다. ✔️ Resource-Allocation Graph ( 자원 할당 그래프 ) ◾️ 자원 할당 그래프는 프로세스의 자원 할당 상태를 표현해주는 그래프이다. ◾️ 동그라미는 프로세스, 네모는 자원을 나타낸다. 네모속의 점은 자원의 인스턴스를 의미한다. ◾️ 프로세스 -> 자원 : 프로세스가 해당 자원을 요청하..
-
[OS] Process SynchronizationComputer Science/Operation System 2020. 4. 14. 13:12
✔️ Process Synchronization (프로세스 동기화) ◾️ Concurrency Control(병행 제어)라고 부르기도 한다. ◾️ 공유 데이터의 동시 접근은 데이터의 불일치 문제를 발생시킬 수 있다. ◾️ 일관성 유지를 위해서는 협력 프로세스간의 실행 순서를 정해주는 매커니즘이 필요하다. ✔️ Race Condition ◾️ 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황 ◾️ 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라진다. ◾️ Race Condition을 막기위해서는 동시 접근을 동기화(synchronize) 해야한다. 1️⃣ Race Condition이 발생하는 예 📌 Multi-processor system에서 메모리를 공유하고 있을 때 📌 공..
-
[OS] CPU SchedulingComputer Science/Operation System 2020. 4. 10. 14:37
✔️ CPU Scheduling (CPU가 1개 있는 시스템) ◾️ CPU를 사용하려는 프로세스 사이에서 우선순위를 관리하는 작업 ◾️ CPU스케줄링을 통해 CPU 이용률, 처리량을 향상시킬 수 있다. ◾️ CPU 스케줄링을 통해 프로세스의 소요시간, 대기시간, 응답 시간을 줄일 수 있다. ◾️ I/O 작업이 빈번하게 이루어지는 프로그램이 있다. (사람하고 인터렉션을 자주하는 프로그램) ◾️ 반면, I/O 작업이 빈번하게 이루어지지 않는 프로그램이 있다. (공학 계산기 프로그램) ◾️ 위 두 프로그램에 대해 CPU를 적절히 할당 해줘야한다. (I/O 작업이 빈번하게 이루어지는 프로그램에 대해 적절히 CPU를 할당해줘야 사람 입장에서 답답하지 않다.) 컴퓨터시스템 안에 있는 I/O bound job(사람이..
-
[OS] Process ManagementComputer Science/Operation System 2020. 4. 9. 12:49
✔️ 프로세스의 생성 1️⃣ 부모 프로세스가 자식 프로세스를 생성한다. 2️⃣ 프로세스는 트리구조를(계층 구조) 형성한다. 3️⃣ 프로세스는 자원을 필요로 한다. ◾ OS로부터 자원을 할당 받는다. ◾ 부모 프로세스의 자원을 공유한다. 4️⃣ 자원의 공유 ◾ 부모와 자식이 모든 자원을 공유하는 모델 ◾ 일부를 공유하는 모델 ◾ 전혀 공유하지 않는 모델 (일반적임) 5️⃣ 프로세스 수행(Excution) ◾ 부모와 자식이 공존하며 수행되는 모델 ◾ 자식이 종료될 때까지 부모가 기다리는(wait, blocked)모델 6️⃣ 프로세스 주소 공간 ◾ 자신은 부모의 공간을 복사한다. (Context까지 다 복사) ◾ 자식은 그 공간에 새로운 프로그램을 올린다. ◾ 유닉스에서는 fork() 시스템 콜로 부모를 복사..