4Legs_Archives

스레드 라이브러리 (Thread Libraries) 스레드 라이브러리는 프로그래머에게 스레드를 생성하고 관리하는 API를 제공한다. 스레드 라이브러리의 구현은 2가지로 나뉘는데, 1. 모든 라이브러리를 커널의 지원 없이 사용자 공간에 제공한다. 이는 라이브러리의 함수를 호출하는 것이 곧 시스템 콜이 아닌 사용자 공간의 지역 함수를 호출한다는 것이라는 의미이다. 2. 운영체제에 의해 직접 지원되는 커널 수준의 라이브러리를 구현한다. 이는 라이브러리의 함수 호출이 곧 시스템 콜임을 의미한다. Pthreads (POSIX Standard) 스레드의 생성과 동기화에 대한 API를 정의한 것이다. (Specification, not an Implementation) C언어에서 pthread.h 헤더 파일을 inc..

스레드 (Thread) 웹 서버가 페이지, 이미지, 사운드 등의 클라이언트 요청을 처리하는 상황을 생각해 보자. 사용량이 많은 웹 서버는 수천, 수만 명의 사용자들의 수많은 요청을 연속적으로 받게 될 것이다. 하지만 만약 웹 서버가 한 번에 단 하나의 요청만 처리할 수 있다면, 사용자들은 간단한 요청 하나에도 많은 시간을 기다리며 불편을 토로할 것이다. 이러한 상황을 해결하는 방법으로는 각 요청마다 요청을 처리하는 프로세스를 두는 것을 들 수 있다. 서버가 요청을 받으면, 서버는 요청을 처리하는 프로세스를 생성하여 받은 요청에 대한 적절한 서비스를 제공한다. 하지만 수천, 수만 개의 요청에 대해 각각 프로세스를 생성하는 데에는 시간 자원의 낭비가 심해질 것이다. 그렇다면 프로세스 하나가 마치 여러 개의 ..

프로세스의 생성 한 프로세스는 실행되는 도중 프로세스 생성 시스템 콜을 통해 새로운 프로세스들을 생성할 수 있다. 다른 프로세스를 생성하는 프로세스를 부모 프로세스(Parent Process)라 하고, 다른 프로세스에 의해 생성된 프로세스를 자식 프로세스(Child Process)라 한다. 프로세스의 부모-자식 관계들은 트리의 형태로 나타나게 된다. 대부분의 운영체제에서는 프로세스들을 구별하기 위해 각 프로세스들에게 유일성을 가진 정수 PID(Process Identifier)를 부여한다. 일반적으로, 프로세스는 CPU time, 메모리, 파일, 입출력 장치 등의 자원이 필요하다. 따라서 어떤 프로세스가 다른 프로세스를 하나 생성하면, 생성된 프로세스는 운영체제로부터 직접 자원을 제공받거나 부모 프로세스..

PCB (Process Control Block) 각 프로세스는 운영체제에서 PCB의 형태로 표현된다. (Task Control Block이라고도 한다) PCB는 다음 그림과 같이 프로세스와 관련된 다양한 정보들을 담고 있다. - Process State : New, Ready, Running, Waiting 등의 상태를 담는다. - Program Counter : 이 프로세스에서 다음으로 실행될 Instruction의 주소를 담는다. - CPU Register : Program Counter와 더불어 프로세스가 진행된 상태를 저장해 interrupt가 발생한 이후에도 프로세스가 잘 동작하도록 한다. - Memory-management Information : 페이지 테이블, 세그먼트 테이블 등의 메모리..

[최단거리 알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) 벨만-포드 알고리즘 (Bellman-Ford Algorithm) [서론] 최단거리 알고리즘의 마지막, 플로이드-와샬 알고리즘(이하 플로이드 알고리즘)이다. 플로이드 알고리즘은 그래프에서 모든 정점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘이다. 그래서 이전까지의 최단거리 알고리즘과는 다르게 dist배열이 처음부터 2차원 배열 형태이다. 벨만-포드 알고리즘과 마찬가지로 음의 가중치가 존재하는 그래프에서도 사용 가능하며, 음의 사이클이 존재하는 경우 최단거리를 구할 수 없다. [동작 원리] 플로이드 알고리즘은 출발 노드, 도착 노드 그리고 중간 노드를 통해 DP와 유사하게 동작한다. 편의상 이들을 From, To, Mid..

프로세스(Process)란? 일반적으로 실행 중인 프로그램을 지칭한다. 그렇다면 왜 프로세스라는, 실행 중인 프로그램에 대한 개념이 별도로 필요할까? 우리는 대개 컴퓨터를 사용할 때 단 하나의 프로그램만 사용하지 않는다. 크롬과 같은 웹 브라우저, 음악을 재생하는 프로그램, 메신저 프로그램 등 여러 개의 프로그램을 동시에 켜놓고 사용하기 마련이다. 하지만 실행 중인 프로그램들 중 우리가 실제로 조작하고 사용하는 프로그램은 한 순간에 단 하나뿐이다. 따라서 OS는 프로그램 고유의 내부 기능이 잘 동작하도록, 실제로 사용하는 프로그램에게 메모리 관리와 같은 지원을 해 주어야 한다. 메모리에서의 프로세스 (Process Memory Layout) 각 프로세스마다 다음과 같은 메모리 영역을 가진다. - 스택 영..

Monolithic Structure (단일 구조) 복잡하고 모듈화된 OS구조의 반대 개념이다. 어플리케이션 및 모든 커널 서비스들이 같은 주소 공간에 위치하기 때문에, 각 컴포넌트 간의 커뮤니케이션이 비교적 효율적이다. 하지만 어느 한 부분이 수정되면 전체를 다시 컴파일 해야하고, 한 컴포넌트에서 발생한 문제가 전제 시스템의 문제가 될 가능성이 크다. Layered Approach (계층 구조) Monolithic의 단점을 보완할 수 있는 계층 구조이다. 상위 계층은 하위 계층을 호출되고, 하위 계층은 상위 계층에게 호출되어 정보를 제공한다. 각 계층별로 구분되어 있기 때문에 Monolithic 구조에 비해 어느 한 부분에 발생한 문제를 해결하기 비교적 쉽다. (그 계층에 대해서만 수정 및 재컴파일 하..

인터럽트(Interrupt) 와 트랩(Trap) 인터럽트(Interrupt)는 하드웨어가 시스템의 수행 흐름을 바꾸기 위해 CPU를 일시적으로 멈추는 것이다. 인터럽트는 하드웨어 인터럽트와 소프트웨어 인터럽트로 나뉜다. · 하드웨어는 CPU에 특정한 신호를 보내 인터럽트를 발생시킨다. · 소프트웨어는 시스템 콜(System Call) 이라는 연산을 실행하여 발생시킨다. 이를 트랩이라고도 한다. I/O 인터럽트 (Input/Output Interrupt) 입출력 하드웨어로부터 발생되는 인터럽트이다. 입출력의 수행이 끝나면 이 인터럽트를 통해 CPU에게 입출력이 끝났음을 알린다. 입출력은 동기식 입출력과 비동기식 입출력으로 나뉜다. 동기식 입출력(Synchronous I/O) 은 입출력이 끝날 때까지 해당 ..

문제 링크 : www.acmicpc.net/problem/2593 2593번: 엘리베이터 첫째 줄에는 N과 M이 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 M줄에 걸쳐 엘리베이터 번호 순서대로 Xi와 Yi가 빈 칸을 사이에 두고 주어지며, 마지막 줄에는 A와 B가 주어진다. N은 100,000이하, M www.acmicpc.net 문제를 그래프의 관점에서 이해하는 것이 중요한 문제이다. 문제에서 층은 최대 10만개, 엘리베이터의 갯수는 최대 100개이므로 BFS를 적용할 때 층이 아닌 엘리베이터를 기준으로 해야 함을 캐치할 수 있다. (BFS의 시간복잡도는 일반적으로 O(V^2)이다.) 문제에서 제시된 예제를 통해 설명하자면, 아래와 같은 엘리베이터 상황을 4층에서 7층으로 이동 가능, 7층에서 12층..

문제 링크 : www.acmicpc.net/problem/3860 3860번: 할로윈 묘지 오늘은 할로윈이다. 상근이와 친구들은 할로윈을 기념하기 위해 묘지를 방문했다. 상근이와 친구들은 한 명씩 묘지로 들어가고, 혼자서 묘지의 출구를 찾아야 한다. 이제, 상근이의 차례가 돌아 www.acmicpc.net 2차원 배열 형태의 그래프에 대한 벨만-포드 알고리즘 적용 문제이다. 문제에서 제시된 예제는 다음과 같다. 이러한 2차원 배열 형태의 예제를 우리에게 익숙한 일반 그래프 형태로 나타내면 아래와 같다. 따라서, 주어진 2차원 배열 Board를 그래프의 형태로 바꾸고, 변환한 그래프에 대해 벨만-포드 알고리즘을 적용하면 된다. 다만 BOJ1219_오민식의 고민 문제와는 달리, 이 문제는 음의 사이클이 발생..