CS (46) 썸네일형 리스트형 [ 운영체제 ] 쓰레드(Thread) Thread 등장 배경 쓰레드는 프로세스의 단점을 보완한 새로운 실행 단위다. 사실 이전에 프로세스가 CPU의 실행 단위라고 했는데 사실은 쓰레드가 맞다. 이전까지는 엄밀히 말해서 '단일 쓰레드'라고 할 수 있다. 프로세스의 치명적인 단점은 fork()를 할 때 자식 프로세스에게 code~stack까지의 모든 메모리 공간을 새롭게 할당한다는 점이다. 이는 심각한 메모리 낭비다. 이해하기 쉽게 그림으로 알아보자. 위 그림과 같이 fork()에 의해 생성된 프로세스는 모두 새로운 메모리 공간을 할당받았다. 그런데 크롬창 네 개를 실행시키는 경우를 생각해보자. 같은 프로그램이기 때문에 비슷한 부분이 상당히 많을 것이다. 어떤 부분이 같고, 어떤 부분이 다를까? 그렇다.. 사실 stack 부분만 달라도 상관 없.. [ 운영체제 ] 프로세스간 통신, IPC (Interprocess Communication) 프로세스는 서로 데이터를 주고 받을 일이 많다. 대표적으로 PPT 파일을 인쇄하는 과정을 생각해 보자. PPT 프로세스는 인쇄할 데이터를 프린터 프로세스에게 전송해주고, 프린터 프로세스는 전송 받은 데이터를 가지고 출력을 하면 된다. 물론 자세하게 들어가면 훨씬 복잡한 과정이지만 일단 이렇게 알아두자. '데이터를 전송한다'의 의미를 메모리 관점에서 다시 생각해보자. 메모리의 크기는 한정적이기 때문에 프로세스가 차지하는 공간도 한정적이다. 프로세스 A가 프로세스 B에게 데이터를 전송한다는 것은 프로세스 A가 프로세스 B의 메모리 공간에 접근한다는 뜻이다. 그런데 이는 굉장히 위험한 행동(?)이다. 만약에 전송하는 데이터의 크기가 프로세스 B의 데이터 공간을 넘어선다면? 프로세스 B에 오류가 발생할 것이다... [ 운영체제 ] 프로세스는 누가 생성하고, 어떻게 생성될까? 프로세스는 누가, 어떻게 만드는 걸까? 우리는 프로세스에 대해 공부하면서 위와 같은 질문을 아직 하지 않았다. 딱히 의심도 하지 않았던 것 같다. 교수님께서 위와 같은 질문을 했을 때 '헐..그러네' 라는 생각을 했었던 기억이 난다. 그러면 바로 본론으로 들어가자. 프로세스는 과연 누가 만드는 것일까? 1. Who? 정답부터 말하자면 프로세스는 부모 프로세스로부터 생성된다. 따라서 모든 프로세스는 부모 프로세스를 가진다. 부모와 자식 관계이기 때문에 OS는 프로세스를 트리 자료구조로 관리한다. 모든 프로세스는 PID라는 고유 식별자를 가진다. PID는 PCB에 저장되어 있다. 그렇다면 태초의 프로세스, 그러니깐 모든 프로세스의 조상 프로세스는 어떻게 생성될까? 태초의 프로세스는 OS 입장에서 매우 중요하.. [ 운영체제 ] 프로세스의 상태, Context Switch 프로세스는 커널의 PCB에 의해 관리된다. PCB 안에는 프로세스에 관한 정보들이 저장되어 있는데, '상태' 정보가 그 중 하나다. 상태의 종류를 알아보기 전에 상태 정보를 저장하는 이유를 한번 생각해보자. 우리는 운영체제를 배우면서 늘 두 가지 사실을 기억하고 있어야 한다. 1. CPU는 한 가지 일(프로세스)만 처리할 수 있다! 2. 컴퓨터는 고철 덩어리에 불과하다(근데 반도체를 곁들인). 마법처럼 짠! 하는 일은 없다. 물론 요즘에는 성능이 좋은 CPU가 많이 나와서 여러 개의 프로세스를 동시에 처리할 수 있지만 사실 그것도 여러개의 CPU를 하나의 CPU처럼 보이게 만들어 놓은 것에 불과하다. 하나의 칩에는 한 가지 일만 수행할 수 있다. 이러한 문제 때문에 '상태' 정보가 필요하다. CPU를 최.. [C++] 투 포인터로 연속 부분합 구하기 어떤 수열의 연속 부분합을 구해보자!! 어떻게 해결할 것인가? 직관적으로 떠오르는 아이디어는 단순하게 이중 for문을 돌리는 것이다. 그러나 이 방법은 O(N^2)의 시간복잡도를 가지기 때문에 효율적이지 못하다. 투 포인터를 사용하면 시간 복잡도를 O(N)까지 단축시킬 수 있다. 위 문제의 핵심은 '연속'에 있다. 연속합을 구하는 것이기 때문에 중복되는 부분이 존재한다. 말로 하면 헷갈리니깐 그림으로 보자. 위 그림에서 빨간색과 파란색의 연속된 부분합에서 형광색 부분이 중복됨을 알 수 있다. 이 사실을 잘 기억하자. 이제 투 포인터의 알고리즘을 살펴보고, 손으로 예제 한 문제를 직접 풀어보자. [ 투 포인터 알고리즘 ] 1. 시작점(start), 끝점(end)을 -1로 초기화한다 2. 현재 부분합(sum.. [C++] 위상 정렬(Topology Sort) 위상 정렬은 비순환 단방향 그래프에서 순서가 정해져 있는 작업을 차례대로 수행해야 할 때 그 순서를 결정해주는 알고리즘이다. 순서만 맞으면 되기 때문에 정답이 두 개 이상일 수 있다. 단, 사이클이 발생하는 경우 위상 정렬을 수행할 수 없다. 이렇게 사이클이 발생하지 않는 그래프를 DAG(Directed Acyclic Graph)라고 한다. 즉, 위상정렬은 DAG에서만 정의될 수 있다. 위상 정렬을 구현하기 위해서 '진입 차수'라는 개념을 알아야 한다. '진입 차수'란 노드로 들어오는 간선의 개수다. 말로 하면 헷갈리니깐 바로 그림으로 알아보자. 위 그림의 경우 진입 차수는 3이다. 노드0으로 들어오는 화살표의 개수가 3이기 때문이다. 위 그림의 경우 진입 차수는 0이다. 노드 0으로 들어오는 화살표.. [C++] 다익스트라(Dijkstra) 1. 다익스트라의 구성 최소 거리를 구할때 사용하는 대표적인 알고리즘 '다익스트라'에 대해 알아보자. 다익스트라 알고리즘은 시작점으로부터 모든 노드까지의 최소거리를 구해준다. 다익스트라를 구현하기 위해서는 비용 배열, 방문 노드 배열, 시작점~각 노드까지의 비용 배열이 필요하다. [ 다익스트라 구현시 필요 요소 ] 1. 비용 배열 weight(이중배열) 출발지에서 목적지로 갈 때 드는 비용을 나타내는 배열이다. weight[3][5] = 5 // 노드3 -> 노드5 갈 때 비용이 5만큼 든다는 뜻이다. weight[2][4] = INF // 노드2 -> 노드4 갈 때 비용이 무한만큼 든다는 뜻이다. 2. 방문 노드 배열 visit 방문한 노드를 확인하는 배열이다. visit[3] = true // 노드3.. [C++] 중위 표기식을 후위 표기식으로 변환 후 계산 중위 표기식은 연산자가 중간에 위치하는 표기식으로 우리가 늘 쓰는 표기식이다. 후위 표기식은 연산자가 뒤에 있는 표기식으로 컴퓨터의 연산 방식이다. 컴퓨터는 사람이 입력한 중위 표기식을 후위 표기식으로 변환해서 연산을 진행한다고 한다. 중위 표기식 : A * (B + C) 후위 표기식: ABC+* 이번 글에서는 중위 표기식을 후위 표기식으로 변환하는 알고리즘과 후위 표기식을 계산하는 알고리즘을 다룬다. 두 가지 경우 모두 stack 자료구조가 필요하다. 1. 중위 표기식을 후위 표기식으로 변환 알고리즘은 아래와 같다. 1) 피연산자는 무조건 출력 2) 연산자인 경우 ---- top보다 우선순위 크면 push ---- top보다 우선순위 작거나 같으면 pop 후 2) 반복 3) '('는 push 4) ').. 이전 1 2 3 4 5 6 다음
