CS

sync, async, blocking, non-blocking

서론 얼마 전에 면접에서 이 개념들을 섞어서 대답하는 바람에... ㅠㅠ 이번에 확실히 정리하고자 글을 쓴다. blocking, non-blocking 이 두 개의 개념은 어떤 한 함수가 어떻게 동작하는지에 관한 이야기다. 함수 A와 B가 존재한다고 하자. 그리고 함수 A가 코드 안에서 함수 B를 호출한다. 이 때 함수 A가 어떻게 행동할지에 따라서 blocking과 non-blocking이 결정된다. 함수 B에는 관심이 없다. 여기서 함수 A의 동작에만 초점을 맞춰보자. blocking에서 함수 A는 다른 행동을 하지 않고 함수 B의 결과를 기다린다. 그러면 함수 A와 함수 B는 싱글 프로세스, 싱글 쓰레드, 멀티 프로세스, 멀티 쓰레드 중에 무엇일까? 모른다. 이것은 구현에 관한 이야기다. 어떤 것으로..

퀵 정렬 (Quick Sort)

기준이 되는 요소(pivot)을 하나 정해서 그 요소를 기준으로 작은 것은 왼쪽으로, 큰 것은 오른쪽으로 몰아넣고 그것들을 다시 반복해서 정렬하여 합치는 알고리즘이다.(divide and conquer) 시간 복잡도 Best - O(NlogN) Average - O(NlogN) Worst - O(N^2) 설명 pivot을 하나 정한다. 그 후에 시작과 끝의 인덱스를 각각 left와 right로 정한다. left는 pivot보다 큰 요소를 찾을 때까지 증가시킨다. right는 pivot보다 작은 요소를 찾을 때까지 감소시킨다. 만약 left가 pivot보다 큰 요소를 찾았고 right가 pivot보다 작은 요소를 찾았다면 서로 자리를 바꿔준다. 그런데 만약 이 때 left와 right가 서로 교차하여 le..

삽입 정렬 (Insertion Sort)

배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 방법이다. 시간 복잡도 Best - O(N) Average - O(N^2) Worst - O(N^2) 설명 삽입 정렬은 길이가 n인 배열에서 인덱스가 1번인 요소(두 번째 요소)부터 시작한다. 배열에서 요소를 선택해서 이전 인덱스의 요소들과 비교하여 적절한 위치에 삽입한다. 이를 n - 1번 반복하면 오름차순 또는 내림차순으로 정렬을 완성할 수 있다. 구현(파이썬) arr = [6, 5, 3, 1, 8, 7, 2, 4] for i in range(1, len(arr)): for j in range(i, 0, -1): # 오름차순 기준, 내림차순은 부호를 반대로 if arr[j - 1..

선택 정렬 (Selection Sort)

선택된 값과 나머지 데이터들을 전부 비교하여 알맞은 자리를 찾는 방법이다. 시간 복잡도 Best - O(N^2) Average - O(N^2) Worst - O(N^2) 설명 길이가 n인 배열에서 인덱스가 0번인 자리를 선택하고, 해당 인덱스를 최솟값을 가지는 인덱스로 둔다. 그 후에 배열의 끝까지 탐색하며 최솟값을 가지는 인덱스를 찾는다. 탐색이 완료되면, 선택한 인덱스 0번의 요소와 최솟값을 맞바꾼다. 이후 인덱스가 1번인 자리를 선택하고 그 이후의 요소들을 가지고(이전 인덱스는 이미 정렬했기 때문에 탐색하지 않는다.) 최솟값을 탐색한 다음 다시 최솟값을 맞바꾼다. 이를 n - 1번 반복하면 오름차순 정렬이 완료된다. 구현(파이썬) arr = [29, 10, 14, 37, 20, 25, 44, 15]..

10. 파일 시스템

파일 파일은 관련된 정보들을 이름을 통해서 묶어 놓은 것이다. 파일은 이름을 통해서 구분되고 접근한다. 일반적으로 비휘발성 보조기억장치에 저장한다. 파일은 생성, 삭제, 읽기, 쓰기 등의 작업을 할 수 있다. 운영체제에서는 저장 장치도 파일로 인식하여 볼 수 있게 해준다. 파일에는 파일 metadata(혹은 file attribute)가 존재한다. 메타데이터는 파일 자체의 내용이 아니라 파일을 관리하기 위한 각종 정보들이 포함된 데이터로 파일 이름, 유형, 저장된 위치, 파일 사이즈, 접근 권한, 시간, 소유자 등이 존재한다. 운영체제에서 이런 파일들을 관리하는 부분을 파일 시스템이라고 하며, 파일 및 파일의 메타데이터와 디렉토리 정보등을 관리한다. 디렉터리 디렉터리는 폴더와 같은 뜻으로, 파일의 메타데..

버블 정렬 (Bubble Sort)

버블 정렬은 아주 기본적인 정렬 알고리즘이지만 시간 복잡도때문에 실제로는 잘 사용하지 않는 알고리즘이다. 시간 복잡도 Best - O(N^2) Average - O(N^2) Worst - O(N^2) 설명 버블정렬은 인접한 두 요소를 비교하여 큰 요소를 오른쪽으로 보내는 정렬 방법이다. 이렇게 배열을 한 바퀴 돌면 맨 끝에 제일 큰 요소가 하나 고정된다. 이를 길이가 n인 배열에서 고정된 요소들을 제외하고 n - 1 번 반복하면 최종적으로 모든 요소가 오름차순으로 정렬된다. 구현(파이썬) arr = [5, 1, 4, 2, 8] for i in range(len(arr) - 1, 0, -1): for j in range(i): # 오름차순 기준, 내림차순은 부호를 반대로 if arr[j] > arr[j +..

9. 가상 메모리

Demand paging 프로세스가 실제로 페이지를 필요로 할 때 메모리에 올리는 것을 demand paging이라고 한다. 이런 행위의 장점은 다음과 같다. - I/O 양의감소 - 메모리 사용량 감소 - 빠른 응답시간 - 더 많은 수용자 수용 page fault 페이지 테이블에는 vaild-invalid bit가 존재한다. invalid는 프로세스에서 사용되지 않는 주소 영역인 경우&페이지가 물리적 메모리에 없는 경우(디스크에 스왑된 경우) 세팅된다. 만약 주소 변환시에 엔트리에 invalid bit가 세팅되어있다면, 이것을 page fault라고 부른다. invalid bit가 세팅된 페이지를 접근하면 먼저 mmu가 trap을 발생시킨다. 그 뒤에 OS가 cpu를 잡고 커널 모드로 전환해서 다음과 같..

8. 메모리 관리

메모리의 주소 메모리 주소는 논리적 주소(가상 주소)와 물리적 주소로 구분된다. 논리적 주소 - 프로세스마다 독립적으로 가지는 주소 공간 - 각 프로세스마다 0번지부터 시작한다. - cpu가 실제로 보고 있는 주소다. 물리적 주소 - 메모리에 실제 올라가는 위치를 말한다. 어떤 코드를 컴파일하여 프로그램을 만들면 그 때 명령어들과 변수들의 논리적 주소가 결정된다. 이것이 실제로 동작하려면 메모리에 프로세스를 올려야한다. 이 때 논리적 주소가 실제 물리적 주소로 변환되어야 한다. 주소 바인딩 논리적 주소를 물리적 주소로 변환하는 과정을 주소 바인딩이라고 하는데, 물리적 주소가 언제 결정되느냐에 따라 3가지로 구분된다. compile time binding - 컴파일시에 물리적 메모리 주소가 결정된다. - ..

7. 교착상태(Deadlock)

교착상태(Deadlock) 교착상태(Deadlock)은 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태를 말한다. 여기서 자원은 하드웨어(cpu, memory..)가 될 수도 있고, 소프트웨어가 될 수도 있다. 교착상태 발생에는 4가지 조건이 존재한다. 이것들이 전부 동시 만족해야 교착상태가 발생한다. Mutual exclusin(상호배제) 매 순간 하나의 프로세스만이 자원을 사용할 수 있다. No preemption(비선점) 프로세스는 자원을 스스로 내려놓을 수 있지만 강제로 빼앗기지 않는다. Hold and wait(점유 대기) 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있는다. Circular wait(순환 대기) 자원을 기다리는 프로세스간에..

6. 프로세스 동기화

데이터의 접근 데이터의 접근은 다음과 같은 순서로 일어난다. 1. 데이터가 저장되어 있는 공간에 접근한다. 2. 연산할 데이터를 가져온다. 3. 연산을 실행한다. 4. 연산 결과를 다시 저장한다. ex) cpu-memory, 컴퓨터 내부-디스크, 프로세스-프로세스의 주소 공간 이 때 여러 프로그램이 하나의 저장 공간을 공유하는 경우 경쟁 상태(race condition)의 가능성이 존재한다. 경쟁 상태란 둘 이상의 입력 또는 조작의 타이밍이나 순서 등이 결과값에 영향을 줄 수 있는 상태를 말한다. 예시로는 멀티프로세서 시스템, 공유 메모리를 사용하는 프로세스들, 커널 내부 데이터를 접근하는 루틴들이 있다. OS에서 경쟁 상태는 여러 프로세들이 동시에 공유데이터를 접근하는 상황을 의미하며 또 데이터의 최종..