이진 탐색 트리 (Binary Search Tree) 아래의 규칙으로 구성된 이진 트리이다. 왼쪽 자식 노드의 키는 부모 노드의 키보다 작다. 오른쪽 자식 노드의 키는 부모 노드의 키보다 크다. 각각의 서브 트리도 이진 탐색 트리이다. 중복된 키를 허용하지 않는다. 이진 탐색 트리의 특징 이진 탐색 트리 규칙에 의해 데이터가 정렬되어 있다. 이진 트리에 비해 탐색이 빠르다. 균형 상태 일때 : O(log n) 불균형 상태 일때 : O(n) 이진 탐색 트리 - 탐색 찾고자 하는 데이터를 루트 노드부터 비교하여 탐색한다. 대소 비교를 하여 찾는 데이터가 현재 노드보다 작으면 왼쪽, 크면 오른쪽 노드로 이동한다. 찾는 데이터가 없으면 null을 반환한다. 어떤 데이터를 찾더라도 최대 트리 높이 만큼의 탐색이 ..
CPU 스케줄링 운영 체제에서 다중 프로세스를 관리하고 CPU의 사용을 최적화하기 위한 방법 여러 프로세스가 CPU를 공유하는 다중 프로그래밍 환경에서 CPU 스케줄러는 어떤 프로세스가 CPU를 사용할 수 있는지 결정하고, 프로세스들 사이의 우선순위를 관리한다. 선점 스케줄링 vs 비선점 스케줄링 선점 스케줄링 (Preemptive Scheduling) 현재 실행 중인 프로세스가 다른 프로세스에 의해 강제로 중단되고, 다른 프로세스가 CPU를 차지할 수 있는 방식 우선순위가 높은 프로세스가 CPU 시간을 뺏어갈 수 있다. 실시간 시스템에서 중요하다. 프로세스의 응답 시간을 보장하고 우선순위가 높은 작업을 즉시 처리할 수 있다. 컨텍스트 스위칭에 따른 오버헤드가 발생할 수 있다. 종류 : SRTF, 우선순..
IPC (Inter Process Communication) 프로세스는 독립적으로 실행되는 단위이므로 기본적으로 다른 프로세스와의 통신이 어렵다. 이를 해결하기 위해 운영체제의 커널 영역에서 IPC 기능을 제공한다. IPC 종류 1. PIPE(Anonymous PIPE) 파이프는 두 개의 프로세스를 연결 하나의 프로세스는 데이터를 쓰기만, 다른 하나는 데이터를 읽기만 할 수 있다. 한쪽 방향으로만 통신이 가능하기 때문에 단방향 통신 또는 Half-Duplex(반이중) 통신이라고 부른다. 파이프는 하나의 통신 선로로 읽기 또는 쓰기 중 하나만 가능하므로, 송수신을 동시에 수행해야 하는 경우 두 개의 파이프를 사용해야 한다. 같은 부모 프로세스를 가지는 프로세스들 사이에서만 통신이 가능하다. 읽기/쓰기 중 ..
PCB (Process Control Block) PCB는 운영체제가 각 프로세스를 관리하기 위해 유지하는 자료구조이다. 각 프로세스마다 하나의 PCB가 할당되며, PCB에는 해당 프로세스에 대한 정보가 저장된다. PCB에 저장되는 정보 프로세스 식별자(Process Id) 각 프로세스에는 고유한 식별자가 할당된다. 프로세스를 식별하고 구분하기 위해 사용 프로세스 상태(Process State) 프로세스의 현재 상태를 나타낸다. new, ready, running, waiting, terminated가 있다. 스케줄링 및 운영체제의 상태 관리에 사용 프로그램 카운터(Program Counter) 현재 프로세스가 다음에 실행할 명령어의 주소를 가리키는 레지스터 값 프로세스가 중단되었다가 다시 실행될 때, ..
시스템 콜 (System Call) 시스템 콜 : 운영체제 커널의 기능을 사용하기 위해 사용자 프로그램이나 응용 프로그램이 호출하는 인터페이스 시스템 콜은 프로세스가 운영체제의 커널 모드로 전환되어 특정 기능을 수행하고, 이후 다시 사용자 모드로 돌아가 프로그램이 실행되는 원리로 동작한다. 시스템 콜 사용 운영체제가 제공하는 다양한 서비스와 리소스에 접근하기 위해 사용 ex) 파일 시스템 접근, 네트워크 통신, 메모리 관리, 프로세스 관리 등 시스템 콜은 운영체제의 기능을 사용하기 위해 특정 함수를 호출하는 형태로 제공된다. 시스템 콜 호출 방식 프로그래밍 언어의 라이브러리 함수나 시스템 인터페이스를 통해 간접적으로 호출 시스템 콜의 종류 1. 파일 관련 시스템 콜 open() : 파일을 열고 사용하기 ..
힙(Heap) 완전 이진 트리 형태 중복 값 허용 반 정렬 상태 최솟값 또는 최댓값을 빠르게 찾아내는데 유용한 자료구조 최소 힙, 최대 힙 우선순위 큐(Priority Queue)를 구현하는데 사용 최소 힙(Min Heap) 부모 노드의 키가 자식 노드의 키보다 작거나 같은 형태 (루트 노드가 최소값을 가지는 힙) 최대 힙(Max Heap) 부모 노드의 키가 자식 노드의 키보다 크거나 같은 형태 (루트 코드가 최대값을 가지는 힙) 힙 구현 배열을 사용하여 구현 완전 이진트리의 특성에 따라 배열에서 각 노드는 인덱스로 표현 루트 노드는 인덱스 0에 위치하며, 자식 노드들은 특정한 방식으로 인덱스를 계산하여 배열에 저장 # 부모 노드와 자식 노드의 관계 왼쪽 자식 index = 부모 index * 2 오른쪽..
트리(Tree) 노드와 링크로 구성된 자료구조 계층적 구조를 나타낼 때 사용 ex) 폴더 구조, 조직도, 가계도, etc. 트리의 특징 하나의 노드에서 다른 노드로 이동하는 경로는 유일하다. 노드가 N개인 트리의 Edge의 수는 N-1개 이다. Cycle이 존재하지 않는다. (Acyclic) 모든 노드는 서로 연결되어 있다. 하나의 Edge를 끊으면 2개의 Sub-Tree로 분리된다. 이진 트리 종류 1. 이진 트리(Binary Tree) 각 노드는 최대 2개의 자식을 가질 수 있다. 자식 노드는 좌우를 구분한다. 2. 포화 이진 트리(Perfect Binary Tree) : 모든 레벨에서 노드들이 꽉 채워져 있는 트리 3. 완전 이진 트리(Complete Binary Tree) : 마지막 레벨을 제외하..
스택(Stack) 후입선출(Last In First Out; LIFO) 자료구조 : 마지막에 들어온 데이터가 먼저 나가는 구조 스택 구현 일반적으로 배열 또는 연결 리스트로 구현 배열 기반 스택 : 고정된 크기를 가짐 연결 리스트 기반 스택 : 동적으로 크기가 조정됨 스택 기본 연산 push: 스택의 맨 위에 요소 추가 pop : 스택의 맨 위에 있는 요소를 제거하고 반환 peek 또는 top : 스택의 맨 위에 있는 요소를 반환하지만 제거하지는 않음 스택 사용 데이터의 순서와 관련된 정보를 유지하면서 데이터를 저장하고 검색하는 경우 유용하게 사용된다. 함수 호출과 재귀 알고리즘 함수가 호출되면 해당 함수의 호출 정보(매개 변수, 반환 주소 등)가 스택의 맨 위에 저장된다. 함수의 실행이 완료되면 스택에..
인터럽트 정해진 흐름 대로 CPU가 실행되고 있는데 이것을 끊는 것을 인터럽트라고 한다. 인터럽트의 종류 동기 인터럽트(예외) : CPU에 의해 발생하는 인터럽트이다. CPU가 명령어들을 수행하다가 예상치 못한 상황이 발생하면 동기 인터럽트가 발생한다. 비동기 인터럽트(하드웨어 인터럽트) : 특정한 동기화 신호 없이 다른 프로세스, 장치, 또는 외부 이벤트에 의해 발생 (ex. 전화/문자 메시지, 웹 브라우저의 팝업 창, 입출력장치 등) 하드웨어 인터럽트를 사용하는 이유는 입출력 작업 도중에도 효율적으로 명령어를 처리하기 위해서이다. 예를 들어 프린트를 하는 상황에서 만약 인터럽트가 없다면, CPU는 프린트 완료 여부를 확인하기 위해 주기적으로 확인해야 한다. 그러나 인터럽트가 있다면 입출력 작업 동안 ..
프로세스 (Process) 메모리에 올려져서 실행 중인 프로그램 각각의 프로세스는 독립된 메모리 공간, 자원, 상태 등을 갖는다. 독립된 메모리 공간에는 Text(Code), Data, Stack, Heap을 할당 받는다. 프로세스는 실행 중인 프로그램의 인스턴스로, 별도의 메모리 영역을 할당받고, 자체적으로 제어 블록인 PCB(Process Control Block)을 갖는다. PCB에는 id, register, PC 등이 있다. 응용 프로그램 ≠ 프로세스 응용 프로그램은 여러 프로세스로 구성 가능 프로세스 스테이트(Process State) 프로세스가 운영체제에 의해 관리되는 동안 어떤 상태에 있는지를 나타낸다. 프로세스의 상태는 다양한 상태 전이(Transition)에 따라 변경될 수 있다. new..
