재민

재귀함수(Recursion)은 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법을 의미한다. Ex) 팩토리얼 재귀함수는 스택에 저장하고(push) 빼내는(pop) 형식을 생각하면 이해하기 편한데, 이를 c 코드로 정리하면 다으모가 같다. void Rec(0){ if (n

[알고리즘 소개] 1) 이진탐색 알고리즘에서는 배열 인덱스의 시작과 끝을 각각 0과 마지막 값으로 둔다. 그리고 0과 마지막 값을 더한 값을 2로 나눈 결과값을 인덱스값으로 하여, 인덱스 값이 target값보다 큰지 작은지를 판단한다. 2) 1의 결과를 토대로 target값보다 크다면 오른쪽을, target값보다 작다면 왼쪽 절반을 취한다. 이를 반복한다. 3) 순차 탐색하는 것 보다 좋은 성능임을 확인한다.(순차 탐색보다 탐색량이 줄음) [구현] int Bsearch(int arr[],int len, int target) { int first = 0; int last = len - 1; int mid; while(first

우선순위 스케줄링이란 : 프로세스에 우선순위를 부여하는 스케줄링으로서, 프로세스는 대개 우선순위가 높을 수록 작은 우선순위 번호를 가진다. 그러면 CPU는 가장 높은 우선순위를 가진 프로세스에 CPU를 할당하는 구조이다. 우선순위의 정의는 내/외부적 요인이 작용한다. 내부적 요인으로는 시간 제한, 메모리 요구, open file 수, I/O와 CPU의 비율 등이 작용할 것이고, 외부족 요소로는 프로세스의 중요성, 비용의 유형과 액수, 그리고 정치적 요인이 작용할 것이다.

운영체제 상에서 가상메모리는 물리적 메모리에 backing store가 합쳐진 공간을 의미한다. 가상 메모리에서는 프로그램의 논리 메모리와 물리적 메모리를 분리하는데, 프로세스가 완전히 메모리에 적재되지 않아도 프로세스 실행을 허용한다. 가상 메모리에서는 물리적 메모리보다 크기가 큰 가상 메모리를 제공할 수 있는데, 프로그램의 크기가 물리적 메모리보다 클 수 있다. 또한 가상 메모리는 페이지 단위의 swap in/out을 진행하는데, 이를 통해 입출력 크기를 감소시킬 수 있다. 가상 메모리의 구현에는 요구 페이징과 요구 세그먼테이션을 이용한다. 가상메모리는 프로세스들이 메모리와 파일 공유를 가능하게 하는데, 이 과정은 공유 라이브러리와 공유 메모리를 통해 이루어진다.

파일에 대한 디스크 공간 할당 방법의 고려 사항으로는, 디스크 공간의 효율적인 이용 및 파일의 빠른 접근을 위해야 한다는 것이다. 이를 위해 3가지 주요 할당 방법을 사용한다 1) 연속 할당(contiguous allocation) 각 파일은 디스크의 연속된 블록들의 집합을 점유하는 방법이다. 최소 탐색시간과 간단하다는 점, 파일 접근이 쉽다는 점은 장점으로 작용하지만, 외부 단편화로 인한 저장공간이 낭비된다는 점, 그리고 파일 크기를 증가시킬 수 없다는 점은 분명한 단점이다. 2) 연결 할당(linked allocation) 각 파일은 디스크 블록들의 linked list로 구성되어, 블록 들이 디스크의 임의의 위치에 분산 가능하도록 하는 방법이다. 공간 낭비가 없다는 점은 장점이지만, 랜덤 접근이 불..

디스크 스케줄링은 디스크의 I/O 요청 처리 순서를 적절한 순서로 스케줄링하여 접근시간 및 대역폭을 향상시키는 방법이다. 디스크 스케줄링의 방법으로는 FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK 스케줄링이 있ㄸ. 1) FCFS : 선입선처리 스케줄링 FIFO 큐를 사용하여 요청한 순서대로 처리하는 방법이다. 빠른 서비스를 제공하지 못하며, 부하가 많은 경우 특히 비효율적이다. 2) SSTF: 최소 탐색 우선 스케줄링이다. (Shortest-Seek-Time-First Scheduling) 현재 헤드 위치에서 탐색시간이 최소인 위치의 요청을 먼저 선택하는 방법이다. FCFS방법보다 효율적이지만, 일부 요청의 기아 상태가 발생할 수 있다. 3) SCAN : 엘레베이터 알고리즘 디스크..

Page fault(페이지 부재)가 발생할 경우 처리 과정은 다음과 같다. 1. page table의 해당 entry를 조사하여 invalid 원인을 알아낸다. 2. free frame을 찾는다. 3. 디스크에 있는 page를 page frame으로 swap in 한다 4. disk read가 완료되면 page table을 갱신한다. 5. page fault trap에 의해 중단되었던 instruction을 재시작한다.

메모리 할당으로는 고정 분할 방식(메모리를 몇 개의 고정 크기 영역으로 분할하는 방법)과 가변분할방식(가변 길이 및 개수를 가지는 분할)이 있다. 가변 메모리 할당 (Dynamic Memory Allocation): 이는 프로그램 실행 중에 필요한 메모리 양을 동적으로 할당하고 해제하는 방식이다. C/C++에서 malloc, free, new, delete와 같은 함수 또는 연산자를 사용하여 동적으로 메모리를 할당하고 해제할 수 있다. int *dynamicArray = (int *)malloc(5 * sizeof(int)); // 동적으로 배열 할당 // ... free(dynamicArray); // 할당된 메모리 해제 정적 메모리 할당 (Static Memory Allocation): 이는 컴파일 ..

이진트리의 표현으로는, 배열과 연결리스트를 들 수 있다. 1) 배열 우선 1차원 배열에 노드를 저장한다. 자신의 번호를 가진 인덱스 위치에 저장해둔다. 이 때 인덱스 0번은 사용하지 않고 비워두고, 인덱스 1번부터 루트 노드를 저장한다. n개의 노드를 가진 트리는 부모와 자식 노드의 인덱스 관계임을 볼 수 있다. 따라서 parent(i) : [i/2] if i != 1이 되고, leftChild(i) : 2i if 2i

스와핑(Swapping)이란 실행을 계속할 수 없는 프로세스를 메모리에서 일시적으로 예비 저장장치로 내보내고, 실행을 계속할 수 있는 프로세스를 예비 저장장치에서 메모리로 불러오기 하여 실행을 재개할 수 있게 하는 것을 의미한다. 예비 저장장치로는 모든 프로세스의 메모리의 복제본을 저장할 수 있을 정도의 저장 용량을 가진 빠른 디스크를 사용한다. 이 때 빠른 접근을 위해 저장된 메모리 이미지에 대해 직접 접근이 가능해야 한다. 스와핑이 존재하지 않는다면, 물리적 메모리의 크기보다 모든 프로세스의 물리적 주소 공간의 합이 반드시 작아야만 한다. 그러나 스와핑을 통해 이러한 경우가 아니더라도 모든 프로세스가 동시에 실행될 수 있게 할 수 있다. 스와핑 동작은 다음과 같은 프로세스로 진행된다. 1. CPU s..