시냅스

교착상태, Deadlock 어떤 집합 내 모든 프로세스들이 모두 Wait Queue에서 빠져나가지 못하는 상태 다시 말해, 모두 대기하고 CPU를 할당받지 않음 시스템 모델 System Model 시스템은 경쟁하는 스레드들 사이에 분배돼야 할 유한한 수의 자원으로 구성 e.g. CPU가 4개면, 4개의 인스턴스를 가진다. Mutex, semaphore 또한 시스템 자원 프로세스의 자원 사용 순서 요청 : 스레드 -> 자원 요청 (자원을 받을 때까지 대기) 사용 : 자원에 대해 작업 수행 방출 : 스레드가 자원 방출 라이브락 Livelock 또 다른 형태의 라이브니스 장애 교착상태가 같은 스레드 집합 내부에서 같은 집합에 속한 다른 스레드에서만 발생하는 이벤트를 기다리며 봉쇄되는 반면, 라이브락은 스레드가..

트리 Tree 트리 구조(tree 構造, 문화어: 나무구조)란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다. 트리에서 최상위 노드를 루트 노드(root node 뿌리 노드)라고 한다. 또한 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한다. 자식 노드가 없는 노드를 잎 노드(leaf node 리프 노드)라고 한다. 잎 노드가 아닌 노드를 내부 노드(internal node)라고 한다. 용어 정리 node(노드) 트리를 구성하고 있는 기본 요소 노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있다. Ed..

큐 Queue, 덱 Deque https://liltdevs.tistory.com/85 [자료구조] 큐, Queue - 배열리스트로 구현 큐, Queue 큐(queue)는 컴퓨터 과학 분야에서 쓰이는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 q liltdevs.tistory.com 덱(deque, "deck"과 발음이 같음 ← double-ended queue)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태이다. 두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생시킬 수 있다. 큐와 스택을 합친 형태로 생각할 수 있다. 큐 구현 Queue using linekd..

큐, Queue 큐(queue)는 컴퓨터 과학 분야에서 쓰이는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다. 프린터의 출력 처리(I/O)나 윈도 시스템의 메시지 처리기, 프로세스 관리 (CPU Schduling) 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다. 배열리스트로 구현하는 queue는 선형 큐와, 환형(원형) 큐로 나눌 수 있다. 선형 큐는 막대..

뮤텍스 락 Mutex Locks 고급 언어에서 개발한 도구 동기화를 위한 가장 간단한 도구 2개만 가능하다. acquire()을 통해 ciritical section에 진입 허가를 받는다. (원자적 연산) release()를 통해 허가를 반납한다. (원자적 연산) busy waiting -> 무한 루프를 돌면서 프로세스는 낭비된다. spin lock (= busy waiting) core가 여러개 일 때는 busy waiting(= spin lock)은 유용할 수 있다. core 위에서 돌아가고 있어 context switch를 줄여준다. 세마포어 Semaphores 정수 variable binary semaphore -> mutex lock 과 비슷하다. counting semaphore -> 제한 없..

프로세스 동기화 Process Synchronization Cooperation process 서로 영향을 주는 process thread를 공유하거나, shared memory massage passing 위의 경우 데이터 일관성에 유의해야 한다 => 실행 순서를 보장해야 한다. (Integrity of Data) producer - consumer problem while(true) { /* produce an item in next_produced */ while (count == BUFFER_SIZE) ; /* do nothing */ buffer[in] = next_produced; in = (in + 1) % BUFFER_SIZE; count++; } while(true) { while (co..

스택 Stack 스택(stack)의 접근은 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 한다. 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다. 자료를 넣는 것을 '밀어넣는다' 하여 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸쉬한 자료부터 나오게 된다. 이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다. 연결리스트를 활용한 스택과 배열리스트를 활용한 스택의 차이점을 아래에서 알아본다. 구현 스택 생성 Push Pop Peek 제거 배열리스트를 활용한 Stack, ArrayStack 스택 생성 ..

다항식 이중 연결리스트 다항식의 항은 계수 + 차수로 이뤄진다. 단 각 항은 내림차순 정렬로 가장 큰 차수가 header node가 된다. 정렬은 node를 생성하면서 조건문을 통해 앞이나 뒤에 넣을 수 있게 하였다. 단, 이 때 차수가 같은 노드가 추가되면 새로 node를 생성하지 않고 기존 Node에 연산만을 할 수 있게 하였다. 계산의 경우에는 덧셈 뺄셈과 곱셈 나눗셈을 따로 분리하여 생각하여야 한다. 덧셈, 뺄셈의 경우 같은 차수에서만 연산이 이뤄지면 되는데, 곱셈, 나눗셈의 경우에는 매 항마다 연산이 이뤄져야 한다. 또한 계수가 0일 경우에는 해당 항이 지워질 수 있게 하였다. 구현 리스트 생성 원소 추가 원소 반환 제거 연산 생성 typedef struct ListNodeType { int c..

실시간 CPU 스케줄링 Real-Time CPU Scheduling real time : 주어진 시간 내에 task 완료 연성(soft) 실시간 vs 경성(hard) 실시간 연성 실시간 soft real time 크리티컬한 process를 실시간 처리 완료를 보장하지 않는다. 하지만 처리시간은 nonciritical process 보단 짧다. 경성 실시간 hard real time deadline 시간을 꼭 지킨다. -> priority-base 지연시간 최소화 Minimizing Latency 이벤트 지연시간 : 이벤트가 발생해서 그에 맞는 서비스가 수행될 때까지의 시간 인터럽트 지연시간 인터럽트가 발생한 시점부터 해당 인터럽트 처리 루틴이 시작하기까지의 시간 현재 수행중인 PCB를 저장하기 까지의 시..

다중 처리기 스케줄링 Muliple-Processor Scheduling 여러 스레드가 병렬로 실행되어 부하 공유(load sharing)이 가능하다. 그러나, 스케줄링 문제는 그에 상응하여 더욱 복잡해진다. 다중 처리기 스케줄링에 대한 접근 방법 Approach to Multiple-Processor Scheduling 비대칭 다중 처리 : 하나의 처리기가 마스터 서버로 모든 스케줄링 결정과 I/O 처리, 다른 시스템의 활동을 취급하게 하는 것 단점은 마스터 서버가 전체 시스템 성능을 저하할 수 있는 병목이 된다는 점이다. 대칭 다중 처리 (SMP) : 표준 방법으로, 각 프로세스가 스스로 스케줄링을 할 수 있다. 모든 스레드가 공통 준비 큐에 있을 수 있다. 경쟁 조건으로부터 공통 Ready Queu..