공부 정리

* Merge Sort? 합병 정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 방식이다. 합병 정렬은 분할 정복(divide and conquer) 기반이라고 볼 수 있다. 합병 정렬은 다음의 단계들로 이루어진다. 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법을 적용한다. 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 통합한다. * Pseudocode 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(m..

* Shell Sort? 쉘 정렬은 전체의 리스트를 한 번에 정렬하지 않는다. 1. 정렬해야할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다. 2. 모든 부분 리스트가 정렬되면 쉘 정렬은 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 알고리즘을 되풀이한다. 3. 부분 리스트의 개수가 1이 될 때까지 이 과정을 반복한다. 부분 리스트를 만들 때에는 주어진 리스트의 k번째 요소를 추출하여 만든다. 이 k번째 요소를 간격(gap)이라고 한다. 이 간격은 처음에는 자료의 개수가 n개 있다면 n / 2 정도로 정하고 각 패스마다 간격을 절반으로 줄이는 방식을 많이 사용한다. * Pseudocode * 분석 삽입..

* Insertion sort? 삽입 정렬은 손 안의 카드를 정렬하는 방법과 유사하다. 새로운 카드가 들어오면 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입함으로써 정렬이 유지되게 한다. 이와 같은 작업을 카드의 수만큼 반복하게 되면 전체 카드가 정렬된다. 이와 같이 정렬되어 있는 리스트에 새로운 레코드를 적절한 위치에 삽입하는 과정을 반복한다. * Pseudocode * 분석 복잡도는 자료 구성에 따라서 달라진다. 입력 자료가 정렬되어 있다면 가장 빠르다. 삽입 정렬의 외부 루프는 n-1번 실행되며 각 단계에서 1번의 비교와 2번의 이동만 이루어지므로 총 비교 횟수는 n-1번, 총 이동 횟수는 2(n-1)번이 되어 알고리즘의 시간 복잡도는 O(n)이다. 최악의 복잡도는 입력 자료가 ..

* Bubble Sort? 버블 정렬은 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다. 버블 정렬을 오름차순으로 한 번 실행하였다면, 리스트의 가장 오른쪽 끝에는 제일 큰 수가 들어가게 된다. 오른쪽부터 정렬이 완료되며 정렬이 되지 않은 왼쪽을 반복하여 정렬하면 정렬이 완료된다. * Pseudocode 하나의 스캔은 index = 0 부터 index = i - 1 까지 반복하는 루프로 구성된다. index 번째 요소와 index + 1 번째 요소를 비교하여 둘이 크다면 swap 한다. 이러한 스캔 과정이 n - 1번 반복되면 정렬은 완료된다. * 분석 버블 정렬의 비교 횟수는 항상 최선, 평균, 최악..

* Selection Sort? 선택 정렬은 입력 배열에서 최소값을 발견한 다음, 이 최소값을 배열의 첫번째 요소와 교환한다. 다음에는 첫번째 요소를 제외한 나머지 요소들 중에서 가장 작은 값을 선택하고 이를 두번째 요소와 교환한다. 이 절차를 (숫자 개수 - 1)만큼 되풀이하면 전체 숫자들이 정렬된다. * Pseudocode * 분석 선택 정렬은 2중 for문을 돌게 된다. 외부 for문은 n-1번 시행되며, 내부 for문은 0부터 n-2까지 변하는 i에 대하여 (n-1-i)번 반복 수행될 것이다. 실제 비교는 내부 for문에서 수행되는데 i가 0일 떄 n-1번, i가 1일 떄 n-2번 이런 식으로 비교하니까 총 비교 횟수는 (n -1) + (n - 2) + ... + 1 = n ( n + 1) / 2..

A thread (or lightweight process) is a basic unit of CPU utilization. 하나의 프로세스 내부에 CPU 수행 단위가 여러개 인 것이 스레드이다. 쓰레드라는 것은 현재 CPU가 현재 어디를 수행하는가(Program Counter)만 여러개 두는 것이다. 프로세스 하나에 CPU 수행 단위만 여러 개임. instruction을 위해서는 현재 어느 부분 수행중인지 알려주는 PC가 있어야 하는데 현재 어느 부분을 수행 중인지 알려주는 Program Counter가 있어야 하는데 이것을 별도로 유지한다. PC, register stack 같은 것만 별도로 가지고 나머지는 공유한다.(죄다 별도로 가지면 낭비임) * Thread의 구성 - program counter..

Contiguous Allocation Linked Allocation Indexed Allocation 하나의 파일이 디스크에 연속해서 저장되는 것을 말한다. directory는 파일의 메타데이터를 가지고 있다. * 단점 - external fragmentation - file grow가 어렵다. -> 파일 생성 시 얼마나 큰 hole을 배당할 것인가? -> grow 가능 (파일이 커질 걸 생각해서 미리 자리 배당하기) vs 낭비 (internal fragmentation) * 장점 - fast i/o -> 한번의 seek/rotation으로 많은 바이트 transfer -> realtime file 용으로, 또는 이미 run 중이던 process의 swapping 용 swap area -> 어차피 프..

* File - A named collection of related information - 일반적으로 비휘발성 보조기억장치에 저장한다. - 운영체제는 다양한 저장장치를 file이라는 동일한 논리적 단위로 볼 수 있게 해준다. - operation: create, read, write, reposition(/seek), delete, open, close * File attribute (혹은 파일의 metadata) - 파일 자체의 내용이 아니라 파일을 관리하기 위한 각종 정보들 파일 이름, 유형, 저장된 위치, 파일 사이즈 접근 권한 (read/write/execution) 시간 (생성, 변경, 사용), 소유자 등 * File System - 운영체제에서 파일을 관리하는 부분 - 파일 및 파일의 메타..

자원을 획득하고 반환하는 걸 처리하는 것을 추상화한 것이다. Semaphores S - integer variable (변수 값 = 정수, 변수가 1이라면 lock, unlock에 활용하고 자원의 개수가 5개라면 5개가 사용 가능) - 아래의 두 가지 atomic 연산에 의해서만 접근 가능하다. P(S)는 공유데이터(자원)을 얻는 연산이다. 그러니까 lock을 거는 과정이라고 생각해도 된다. 세마포어 객체 mutex는 1로 초기화되어 있다. (1개가 크리티컬 섹션에 들어갈 수 있다는 뜻임) busy - wait는 효율적이지 못함 ( = spin lock) block & wake up 방식의 구현 (= sleep lock) 락을 못 얻으면 blocked (잠들어버리기) -> 쓸데없이 cpu 낭비하는거 막음..

Concurrency: 병행 제어 A가 ++하는 동안 B가 count 가져가서 -1 한다면 -1뺀 결과만 저장된다. 원랜 0 저장되어야 하는데... S-Box(Memory Address Space)를 공유하는 E-Box(CPU Process)가 여럿 있는 경우 Race condition(경쟁상태)의 가능성이 있다. 즉 여러 주체가 하나의 데이터에 동시 접근 하려고 할 때 경쟁 상태의 가능성이 있는 것이다. * E - box? CPU Process: MultiProcessor System, 공유 메모리를 사용하는 프로세스들. 커널 내부 데이터를 접근하는 루틴들 간 예) 커널모드 수행 중 커널모드로 다른 루틴 수행할 때) 1. 커널 수행 중 인터럽트 발생 시 2. 프로세스가 시스템 콜을 하여 커널 모드로 수..