데굴데굴

min-heap data structure 이진 트리를 기반으로 한 자료구조 부모 노드가 자식들보다 작거나 같은 구조 가장 작은 값이 부모 노드에 위치하는 자료구조 우선순위 큐 구현, Heap Sort에도 활용된다. 가장 작은 값을 `O(1)`의 시간으로 빠르게 찾을 수 있다는 장점이 있다. 다음은 자바스크립트로 최소 힙을 구현하는 코드이다. class MinHeap { constructor() { this.heap = []; } push(value) { this.heap.push(value); this.heapifyUp(); } pop() { if (this.isEmpty()) return null; const root = this.heap[0]; const lastNode = this.heap.pop..

일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태 자원은 하드웨어와 소프트웨어를 포함하는 개념이다. 프로세스가 자원을 사용하는 절차는 네 단계가 있다. request -> allocate -> use -> release Deadlock의 발생 조건 아래 조건을 모두 만족해야 Deadlock이 발생한다. Mutual exclusion - 매 순간 하나의 프로세스만 자원을 사용할 수 있다. No preemption - 프로세스는 자원을 빼앗길 수가 없다. 오로지 스스로 내놓아야만 한다. Hold and wait - 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있다. Circular wait - 자원을 기다리는 프로세스 간에 사이클이 형성된다. Deadlock이 발생했는지 알아보..

process synchronization은 concurrency control이라고도 한다. Critical-Section Problem 해결책의 세 가지 전제조건 상호 배제 Mutual Exclusion: 한 프로세스가 critical section을 수행 중이면 다른 프로세스는 critical section에 들어가면 안 된다. 진행 Progress: critical section에 아무도 들어가있지 않으면 들어갈 수 있게 해야 한다. 한정 대기 Bounded Waiting: 특정 프로세스가 영원히 임계 영역에 들어가지 못하면 안 된다. (starvation 발생 X) entry section에서 lock을 걸고 critical section에서 빠져나왔을 떄 exit sectoin에서 lock을 ..

데이터가 저장되는 곳이 있고 데이터를 이용해 연산을 수행하는 곳이 존재 한 storage box를 여러 execution box가 사용하고 있다면 Race condition의 가능성이 있다. 이 상태를 조율해줄 수 있는 방법이 필요 Race condition이 발생하는 경우 1. 커널의 코드를 실행 중일 때 인터럽트가 발생할 경우 커널에서 데이터의 값을 1 증가시키는 작업을 하고 있음 도중에 인터럽트가 발생하여 인터럽트 핸들러를 실행함 인터럽트 핸들러에서 데이터의 값을 1 감소시키는 작업을 함 -> 예상: 값이 원래 상태로 돌아와야 한다 (1 증가 -> 1 감소) 커널에서 인터럽트 핸들러로 넘어갈 때 작업하던 상태를 저장해두고 넘어감 인터럽트가 끝나고 다시 돌아왔을 때 이전 작업 상태를 다시 불러오기 때..

CPU만 쓰는 단계 - CPU burst I/O만 하는 단계 - I/O burst I/O-bound process (many short CPU bursts) - 계산 시간보다 I/O에 많은 시간이 필요한 job CPU-bound process (few very long CPU bursts) - 계산 위주의 job CPU-burst time의 분포를 확인하니 CPU만 오랫동안 쓰는 빈도보다 짧은 간격으로 I/O 작업을 수행하는 빈도가 높았다. I/O는 유저와 직접적인 상호작용을 하는 작업. 더 좋은 사용자 경험을 제공하기 위해 interactive job에게 더 우선적으로 CPU를 제공해야 한다 스케줄러 & 디스패처 둘은 전부 운영체제 안의 코드이다. CPU Scheduler - Ready 상태의 프로세스..

프로세스는 저절로 생기지 않음 시스템 부팅 후 최초의 프로세스는 운영체제가 생성하지만 그 이후부터는 다른 프로세스를 복제 생성함으로써 생겨난다. 부모 프로세스가 자식 프로세스를 생성하여 부모 프로세스를 기준으로 하나의 트리 구조가 형성된다 부모 프로세스와 자식 프로세스가 자원을 공유하는 모델도 있고, 일부를 공유하거나 전혀 공유하지 않는 모델도 있다. (공유하지 않는 모델이 일반적) 프로세스와 관련된 시스템 콜 명령어 fork() - 복제 생성 (자식 프로세스는 부모의 공간과 문맥을 그대로 복사하여 생성됨) exec() - 한 프로세스에서 시스템 콜을 통해 다른 프로그램을 실행시키는 명령어 exit() - 프로세스가 마지막 명령을 수행한 후 운영체제에게 알려줌 wait() - 자식 프로세스가 부모 프로세..

스레드 (thread, lightweight process) CPU를 수행하는 단위, 프로세스의 특정한 수행 경로 같은 프로그램을 여러 개 띄워서 실행할 때 프로세스를 하나 더 생성하지 않고 한 PCB 내에서 stack만 따로 할당받는 것이다. 스레드별로 program counter, register set, stack space는 개별적으로 가진다. code section, data section, OS resources는 한 프로세스 내에서 공유해 사용한다. 장점 - 한 프로세스 아래에 스레드를 여러 개 두게 되면 한 스레드가 blocked 상태일 때 같은 태스크 내의 다른 스레드가 실행되어 처리를 빠르게 할 수 있다. - 동일한 일을 수행하는 다중 스레드가 협력하여 처리율을 높이고 성능을 향상시킬 ..

프로세스 실행 중인 프로그램 (program in execution) 프로세스 문맥 (process context) 프로세스가 어떤 상태에서 수행되고 있는지 정확하게 규명하기 위해 필요한 정보 하드웨어 문맥 CPU의 수행 상태를 나타내는 것 프로그램 카운터 값, 각종 레지스터에 저장하고 있는 값 프로세스의 주소 공간 커널상의 문맥 - PCB, 커널 스택 프로세스의 상태 Running - instruction 수행 중 Ready - CPU 사용을 위해 대기 중인 상태 (메모리에 올라와 있음, cpu만 얻으면 바로 작업을 수행할 수 있는 상태) Blocked (wait, sleep) - cpu를 줘도 당장 instruction을 실행할 수 없는 상태, ex) i/o 작업을 완료해야 할 수 있는 작업 susp..