Q. Array와 LinkedList의 장점과 단점에 대해 시간 복잡도를 가지고 설명해주세요. 더보기 Array의 장점은 순차적으로 데이터를 저장할 수 있다는 것입니다. 데이터에 순서가 있으므로 index를 갖게 되며, index를 이용하여 자료의 탐색을 O(1)의 시간복잡도로 할 수 있습니다. 반면 데이터가 순차적으로 존재하기 때문에 새로운 데이터를 삽입하거나 삭제하는 경우 그 뒤의 모든 데이터들을 한칸씩 움직여주어야 한다는 단점이 있습니다. 이 경우 O(N) 의 시간 복잡도를 가집니다. LinkedList의 경우 삽입과 삭제 연산에 O(1)의 시간복잡도를 가집니다. 반면, 탐색을 하는 경우 array 처럼 index를 이용하여 바로 접근할 수 없으며 선형 탐색을 해야 하므로 O(N)의 시간복잡도를 가..
Computer Science
CPU 스케줄링 데드락(DeadLock) Race Condition 세마포어(Semaphore) & 뮤텍스(Mutex) 페이징 & 세그먼테이션 페이지 교체 알고리즘 메모리(Memory) 파일 시스템 Q. CPU 스케줄링 알고리즘 중에서 비선점형 스케줄링에 대해 설명해주세요 더보기 CPU 의 이용률을 극대화하기 위해서 멀티 프로그래밍을 해야 한다. 언제 어떤 프로세스에 CPU 자원을 할당할지 결정하는 것이 CPU 스케줄링이다. 비선점형 스케줄링이란 한 프로세스가 CPU 를 점유하고 있다면 다른 프로세스가 CPU 자원을 빼앗을 수 없는 방식이다. 따라서 필요한 문맥 교환만 발생하여 오버헤드가 상대적으로 적지만 프로세스가 어떻게 배치되는 지에 따라서 효율성이 많이 차이날 수 있다. 비선점형 스케줄링의 종류 F..
이번 포스팅에서 정리할 운영체제 핵심 키워드 프로세스 스레드 인터럽트 시스템 콜 Process Context Switching IPC (Inter Process Communication) Q. 프로세스와 스레드에 대해 설명해주세요. 더보기 프로세스 : 프로그램이 정적 코드의 집합이라면, 프로세스는 프로그램이 실행되어 메모리에 적재 된 이후, CPU 자원을 할당 받아서 실행되고 있는 동적인 상태인 것을 의미한다. 스레드 : 하나의 프로세스 안에서 동시에 실행중인 작업 흐름의 단위를 의미한다. 인터넷 브라우저에서 동영상 재생을 하며, 쇼핑을 할 수 있는데 이는 하나의 프로세스 안에서 동시에 여러 스레드들이 진행되기 때문에 가능하다. Q. 프로세스의 내부 구조에 대해 설명해주세요. 더보기 코드영역 프로그래머가..
선택 정렬 (Selection Sort) 현재 위치에 들어갈 값을 선택해서 정렬하는 배열이다. 일상에서 크기 순으로 나열할때 하나씩 끄집어내서 정렬하는 걸 생각하면 쉽다. 예를 들어서 오름차순으로 정렬하는 경우에, index 0번에 오는 원소는 모든 값중에서 가장 작은 값을 선택해서 정렬한다. 그후 index 1 번에 오게 될 원소를 찾아서 선택하여 정렬하게 되는데, 0 번에 정렬한 값을 제외하고 나머지 값들 중에서 가장 작은 값을 선택해서 정렬하게 되면 된다. 시간 복잡도 : O(N**2) 시간 복잡도는 루프문을 통해 모든 인덱스에 접근해야 하므로, 기본적으로 O(N)이 걸리고, 하나의 루프에서 현재 인덱스 값과 다른 인덱스의 값들과 비교를 각각 한번씩 수행하여 최소값을 찾은 후 현재 인덱스에 있는 값..
Segmentation 프로그램을 의미 단위인 여러개의 segment로 구성 작게는 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의 크게는 프로그램 전체를 하나의 세그먼트로 정의 가능 일반적으로는 code, data, stack 부분이 하나씩의 세그먼트로 정의됨 Segment 는 다음과 같은 logical unit 들이다. main(), function, global variables, stack, symbol table, arrays Segmentation Architecture locigal address는 다음의 두가지로 구성 segment table : 각각의 테이블 엔트리는 base 와 limit 을 가지고 있음 base : starting physical address of the segm..
Paging 기법과 주소 변환 Paging 기법에서는 프로그램을 구성하는 주소 공간이 동일한 크기의 Page 라는 단위로 잘려서, 각각의 Page가 물리적 메모리의 어디에나 올라갈 수 있다. 각각의 Page들이 어느 위치에 올라가 있는지 알기 위해서는 Page별로 주소 변환이 필요하다. Paging 기법 물리 메모리는 Frame 이라 불리는 같은 크기의 블록으로 나누어진다. 논리메모리는 Page라 불리는 같은 크기의 블록으로 나누어진다. Page Table에서 논리적인 주소에서 물리적인 주소로 주소 변환을 한다. 따라서 Page Table에서는 logical memory 의 개수만큼 entry 가 존재하게 된다. Index를 이용해서 곧바로 접근할 수 있는 자료 구조 형태이다. 각각의 Page는 Code..
Logical vs Physical Address 1. Logical Address (= Virtual Address) 프로세스마다 독립적으로 가지는 주소 공간 각 프로세스마다 0번지부터 시작 CPU가 보는 주소는 logical address 이다. 2. Physical Address 메모리에 실제 올라가는 위치 3. 주소 바인딩 : 주소를 결정하는 과정 어떤 프로그램이 물리적 메모리 어느 곳에 올라갈지를 결정한다. Symbolic Address -> Logical Address -> Physical Address *Symbolic Address : 프로그래머들이 특정 이름을 통해 변수를 지정하고 값을 저장할 때, 변수의 이름을 통해 값에 접근하게 된다. 즉 우리가 흔히 사용하는 포인터이다. 주소 바인딩..
Deadlock : 일련의 프로세스들이 서로가 가진 자원을 기다리며 block 이 된 상태 Resource 자원으로, software 자원일 수도 있고 hardware 자원이 될 수도 있다. ex. I/O device, CPU cycle, memory space, semaphore 프로세스가 자원을 사용하는 절차 ex. Request, Allocate, Use, Release https://core.ewha.ac.kr/publicview/C0101020170412134857472082
