API Interface는 상호 간의 연결을 위한 접점이다. API는 프로그램 간의 접점이다. API를 통해 프로그램에서 다른 프로그램의 기능을 사용할 수 있다. 만약 OS의 기능이 필요하면 OS가 제공하는 API로 OS의 기능을 사용할 수 있다. HTTP로 API를 제공하는 것을 HTTP API라 한다.
스레드 예전의 프로세스는 단일 실행 스레드(single thread of execution)을 가졌다면 지금의 프로세스는 여러 개의 스레드를 가져 여러 개의 실행 흐름을 가지게 되었다. 예전에는 프로세스가 여러 개의 실행 흐름을 가지기 위해 새 프로세스를 생성했다. 하지만 프로세스를 생성하는 건 많은 시간과 자원이 요구되는 작업이며 같은 일을 하는 프로세스를 여러 개 두는건 매우 비효율적이다. 때문에 경량화된(light-weight) 프로세스인 스레드가 등장했다. 스레드는 원래 실타래, 프로그램 실행 흐름을 의미하는 용어였다. 멀티스레딩 시스템에서 CPU를 점유하는 단위는 프로세스가 아닌 스레드이다. 스레드는 경량화된 프로세스(Light-Weight Process, LWP)이다. 스레드는 스레드 ID, ..
IPC 프로세스는 독립적인 프로세스이거나 협력적인 프로세스이다. 독립적인 프로세스 : 다른 프로세스와 아무런 데이터도 공유하지 않는 프로세스 협력적인 프로세스 : 다른 프로세스에 영향을 주거나 받는 프로세스 또는 다른 프로세스와 데이터를 공유하는 프로세스 협력적인 프로세스들은 서로 간 데이터를 주고 받을 수 있는 프로세스 간 통신(interprocess communication, IPC) 기법이 필요하다. IPC에는 공유 메모리(shared-memory)와 메시지 전달(message-passing) 모델이 있다. 어떻게 하면 프로세스 간 데이터를 주고 받을 수 있을까? 프로세스가 다른 프로세스 메모리에 접근하는 것은 매우 위험하므로 OS에 의해 금지된다. 쉬운 방법은 프로세스들이 서로 접근할 수 있는 공..
프로세스 비공식적으로, 프로세스는 실행 중인 프로그램이다. 프로그램이 명령어 리스트를 저장한 파일(실행 파일)과 같은 수동적인 존재(passive entity)라면 프로세스는 프로그램 카운터 및 관련 자원을 가진 능동적인 존재(active entity)이다. 프로세스는 아래의 자원들을 가진다. 레지스터 (PC, IR 등) cpu time 메모리 파일 I/O 디바이스 메모리 배치 프로세스의 메모리 배치는 일반적으로 여러 섹션으로 구분되며 아래의 섹션을 포함한다. 텍스트 섹션 - 실행 코드 데이터 섹션 - 전역 변수 힙 섹션 - 프로그램 실행 중 동적으로 할당되는 메모리 스택 섹션 - 함수를 호출 시 임시 데이터 저장 장소(함수 매개변수, 복귀 주소, 지역 변수) 텍스트와 데이터 섹션은 크기가 고정되어 있으..
알고리즘 증명 알고리즘을 설계했다면 알고리즘이 제대로 동작하는지 증명할 필요가 있다. 단위 테스트를 이용해 여러 개의 입력에 대해 프로그램을 실행해 보고 그 답을 점검할 수도 있지만, 이런 식으로는 이 알고리즘이 가능한 모든 입력에 대해 정확하게 동작한다는 사실을 증명할 수 없다. 이번 글에서는 알고리즘 증명을 위해 흔히 사용하는 기법들을 소개한다. 수학적 귀납법과 반복문 불변식 수학적 귀납법은 자연수 n과 관련된 명제 P(n)이 모든 자연수에 대해 성립한다는 것을 증명하는 방법이다. 증명은 아래의 두 단계로 구성된다. P(1)이 성립함을 보인다. P(n)이 성립한다 가정하에 P(n+1) 또한 성립함을 보인다. 수학적 귀납법의 원리는 도미노와 같다. 다음 2가지 사실을 보이면 모든 도미노가 쓰러진다는 걸..
BFS BFS는 시작 정점에서 가까운 정점부터 순서대로 방문하는 그래프 탐색 알고리즘이다. 이러한 탐색 방식으로 시작 정점에서 각 정점들을 최단 경로로 방문한다. 아래는 인접 행렬을 탐색하는 BFS 코드이다. static void BFS(int start, int[][] graph, boolean[] discovered) { Queue queue = new LinkedList(); discovered[start] = true; queue.add(start); while(!queue.isEmpty()) { int v = queue.remove(); for(int i=0; i
문제를 방향 그래프로 만들어 오일러 경로 또는 오일러 트레일을 구하는 문제로 변환할 수 있다. a부터 z를 정점으로 두고 단어의 시작 알파벳에서 단어의 마지막 알파벳으로 가는 간선을 추가한다. 예를 들어 dog 단어가 나온다면 d에서 g로 가는 간선을 추가한다. 그런 다음 방향 그래프에 오일러 경로 혹은 트레일이 존재할 수 있는지 확인 후 오일러 경로 또는 오일러 트레일을 구해 단어를 출력한다. (모든 정점) 진입 차수 = 진출 차수 → 오일러 경로 존재 (시작점) 진출 차수 = 진입 차수 + 1, (끝점) 진출 차수 = 진입 차수 - 1, (나머지 정점) 진입 차수 = 진출 차수 → 오일러 트레일 존재 import java.util.*; import java.io.*; public class Main ..
운영체제 컴퓨터 하드웨어를 관리하는 소프트웨어이며 유저, 응용 프로그램과 하드웨어간의 연결점(Intertace) 역할을 수행한다. 컴퓨터 시스템 구성 전통적인(classical) 컴퓨터 시스템은 하나 이상의 CPU와 다수의 디바이스 컨트롤러가 버스를 통해 연결되어 있다. 디바이스 컨트롤러는 특정 유형의 장치를 담당하며 로컬 버퍼 저장소와 특수 목적 레지스터 집합을 유지 관리한다. 장치 컨트롤러마다 장치 드라이버(device driver)가 있다. 이 장치 드라이버는 운영체제에게 장치에 대한 인터페이스를 제공한다. 인터럽트 CPU와 I/O 디바이스 간의 통신 방법 중 한가지로 하드웨어는 버스를 통해 CPU에 신호를 보내 인터럽트를 발생시킬 수 있다. CPU가 인터럽트되면 CPU는 하던 일을 중단하고 인터럽..
