본문 바로가기

CS Study

 (20)
메모리 관리 - 메모리 단편화, 페이징, 세그멘테이션 메모리 단편화 RAM 에서 메모리의 공간이 작은 조각으로 나뉘어져 사용 가능한 메모리가 공간이 실제로는 충분히 존재하지만 사용이 불가능한 상태. 내부 단편화 : 메모리를 할당할 때 프로세스가 필요한 메모리보다 더 큰 메모리가 할당되어 프로세스에서 사용하는 메모리 공간이 낭비되는 현상. 예를 들어, 메모리를 할당하는 최소 블록 크기가 10K인데 프로세스는 5K만 필요한 상태면 5K가 낭비된다 외부 단편화 : 메모리가 할당 및 해제 작업을 반복하여 작은 메모리가 띄엄띄엄 존재할때 사용하지 않는 메모리가 존재하는 경우로총 메모리 공간은 충분하지만 실제로 사용이 불가능한 상태. 메모리 단편화 해결 방법 1. Paging 기법 메모리 공간이 연속적으로 할당되어야 한다는 제약조건을 없애는 메모리 관리 전략. 프로세..
병행 프로세스와 동기화 - 병행성 vs 병렬성, 상호 배제, 세마포어, 뮤텍스 프로세스 동기화의 필요성 어떤 프로세스가 먼저 공유 자원에 접근하느냐에 따라 실행 결과가 달라질 수 있기 때문에 공유 자원의 일관성을 유지하기가 어렵습니다. 이를 해결하기 위해 프로세스 동기화가 필요합니다. 1. 병행성(Concurreny) vs 병렬성(Parallelism) 1.1 병행이란? 동시에 실행되는 것처럼 보이는 것입니다. 자세하게는 메모리에 다수의 프로세스가 같이 존재한다는 의미입니다. 실제 실행 과정에서 자원을 공유하고 있을 경우 공유된 자원을 서로 언제 사용할것이지와 같은 복잡한 관리가 필요합니다. 병행 처리는 다음과 같은 문제점이 있습니다. 전역 자원의 공유가 어렵다. OS가 자원을 최적으로 할당하기 어렵다 프로그래밍 오류를 찾아내는 것이 어렵다. 1.2. 병렬이란? 실제로 동시에 작업..
Thread란? Multi-Thread, Multi-Tasking, Multi-Processing 1. Thread란? 프로세스 내에서 실행되는 여러 흐름의 단위를 뜻합니다. 즉, 프로세스가 할당받은 자원을 이용하는 실행의 단위입니다. 이 각각의 스레드는 서로 하는 일은 서로 다르지만 스레드가 모여 하나의 프로세스를 구성합니다. 프로세스와 비교했을때 프로세스는 CPU자원이 부여된 자원의 소유자이고, 스레드는 스케줄링의 단위로서 존재합니다. 하나의 프로세스에 속한 각각의 스레드들은 프로세스가 가지는 자원을 공유하면서 자신의 실행환경에서 현재의 실행위치와 스택, 레지스터 값들을 따로 가지게 됩니다. 스레드는 프로세스내에서 각각 Stack만 할당받고 Code, Data, Heap 영역은 공유합니다. 한 프로세스내부에서 프로세스들은 주소공간이나 자원(Heap)과 같은 영역을 공유하면서 실행됩니다. Code,..
프로세스란? PCB, Process State, Process Life Cycle 1. Process OS입장에서 보면 실행되어야 하는 프로그램들에게 시스템자원을 적절히 분배해줘야 하는 책임이 있습니다. 이때 task 단위로 서로 명확하게 구분이 되어야 하는데 이것을 프로세스라고 지칭합니다. 실행중인 프로그램을 의미합니다. 즉 메모리위에 올라와 실행되고 있는 프로그램의 인스턴스로 OS로부터 정상적인 실행을 위해 필요한 환경을 부여받은 능동적인 존재입니다. OS로부터 시스템 자원을 할당받는 작업의 단위이기도 합니다. 예를 들어, 크롬 브라우저가 두 개가 실행되면 두 개의 크롬 프로세스가 실행되는 것입니다. 1.1 Process Control Block (PCB) 프로세스 하나가 만들어진다는 것은 곧, 그 프로세스에 대한 모든 정보를 나타내는 PCB 하나가 만들어진다는 말과 같습니다. O..
Interrupt 란? 인터럽트 프로세스, 인터럽트 우선순위 1. 인터럽트 CPU당 하나의 Task(Process/Thread)만 실행할 수 있기 때문에, 사용자에게 멀티 태스킹을 지원하기 위해서는 Task를 Switching하며 구동되어야 합니다. 이때 Task간 Switching하는 과정에서 발생하는 요청을 인터럽트라고 합니다. 또는 CPU가 프로그램을 실행하고 있을 때, 입출력 장치나 예외상황이 발생하여 처리가 필요할때 프로세서에게 알려 처리할 수 있도록 하는 것을 의미합니다. I/O Device와 커뮤니케이션 저장매체에서 데이터 처리를 완료한뒤 프로세스를 깨워야할때 인터럽트가 필요합니다. (block -> ready) 예외 상황 핸들링 0으로 나누려는 연산의 경우 알 수 없기 때문에 인터럽트가 필요합니다. 이때는 Process를 Kill 해줍니다. 타이머 ..
[그래프 이론] - Minimum Spanning Tree (최소 신장 트리) Spanning Tree는 그래프를 최소로 연결한 그래프입니다. 그렇기 때문에 N개 노드들이 있을때 모든 정점들이 연결 되어 있고 간선은 N-1개로 연결되어있습니다. 이때 사이클은 포함해서는 안됩니다. 최소 신장 트리는 Spanning Tree에서 사용된 간선들의 총 비용이 최소값을 가진 특수한 트리입니다. 최소 신장 트리가 최단 경로를 나타내지 않습니다. 최단 경로와 헷갈리면 안됩니다!! 예를 들어, N개의 정점에서 각 정점별 비용이 주어지고, 최소의 비용으로 모든 노드들간 서로 이동이 가능하도록 만드는 필요한 최소 비용을 구하라는 문제가 있을때 최소 신장 트리를 떠올려야 합니다. 최소 신장 트리를 만드는 방법은 두 가지 방법이 있습니다. 가장 많이 사용하는 방법으로 프림 알고리즘과 그 다음으로 크루스..
탐색 알고리즘 정리 #3 - 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) Shortest path between all pairs of vertices, negative edges allowed. 모든 노드 간 최단 거리를 구하는 알고리즘입니다. 플로이드-워셜 알고리즘은 다익스트라 알고리즘과는 다르게 음의 간선도 사용할 수 있습니다. Floyd-Warshall 로직 다익스트라 알고리즘과는 다르게 플로이드-워셜 알고리즘은 모든 정점을 경유지로 만든다는데에 있습니다. 우선, 모든 노드 간의 최단경로를 저장해야 하기 때문에 2차원 인접 행렬을 만듭니다. 거리값은 모두 무한대로 초기화 시켜줍니다. 하나의 정점에서 다른 정점으로 바로 갈 수 있으면 비용을 업데이트 시켜줍니다. 이때 갈수있는 경로가 여러개라면 최소값을 저장합니다. 경유지를 기준으로, 어떤 두 노드가 해당 경유지를 거처갈..
탐색 알고리즘 정리 #2 - 다익스트라 알고리즘(Dijkstra algorithm) 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘입니다. (shortest path from one node to every other node) 다익스트라의 개념은 출발점에서 이동 가능한 노드들을 찾고, 그 거리를 모두 기록합니다. 그리고 이 거리들 중 가장 짧은 것을 선택하고 이동하는것을 반복합니다. 마지막으로 한 노드까지의 경로를 리턴해주면 가장 짧은 경로를 알 수 있습니다. 이때 간선들은 모두 양의 간선들을 가져야 합니다. 하나의 정점에서 다른 모든 정점까지 각 정점별 최단 거리를 기록하는 배열이 있어야 합니다. 다익스트라 알고리즘은 첫 정점을 기준으로 연결되어있는 정점들을 추가해가며, 이전보다 최단 경로값이라면 최소값을 계속 업데이트 합니다. (각 정점간의 거리들은 모두 무..

티스토리툴바