본문 바로가기

CS23

[자료구조] 2. Tree : Binary Tree, Heap, BST 1. Terminology 1) Degree : # of child the node has 2) Size : total # of node in tree 3) Depth : # of edge that need to pass from root node(>=0) 4) Height : maximum value of depth 5) Level : set of node at same level 2. Binary Tree Tree의 각 Node가 최대 2개의 Children Node를 가지는 Tree 자료구조 * number of node in tree = n, height of tree = h 일때 → 2h + 1 ≤ n ≤ 2^(h+1)-1 1) Compelete Binary Tree : 완전이진트리 마지막 le.. 2020. 12. 1.
[자료구조] 1. Array, Pointer, Stack, Queue, LinkedList 1. Array 연속적인 memory에 저장된 같은 type의 data집합 2. Pointer // 일반 포인터 type* var_name; cout data = (element); // == *(*ptr).data = (element); 3. Stack 한쪽 끝에서만 자료를 추가하고 삭제할 수 있는 FILO형태의 자료구조 4. Queue 한쪽 끝에서만 자료를 추가하고 삭제할 수 있는 FIFO형태의 자료구조 5. Linkedlist 기준에 따라 순서대로 배치할 때 새로운 element 삽입/삭제를 단순 Array보다 빠르게 할 수 있는 자료구조 typedef struct listNode *listPtr; typedef struct listNode{ int data; listPtr link; } listP.. 2020. 12. 1.
[OS] 9. Deadlock 1. 조건 1) Mutual exclusion 2) Hold & Wait 3) No Preemption 4) Circular Wait : 모두를 만족해야 deadlock 생성 가능, 즉 하나만 방지하면 deadlock 불가능 2. Prevention 1) Mutual exclusion - Mutual exclusion 속성을 가지지 않은 resource에 대해서만 가능 2) Hold & Wait - 프로세스가 Task를 위한 모든 Resource를 점유해야 시작 가능하도록 설계, 하나라도 불가능하면 다시 release. - Low resource utilization, possibility of Starvation 3) No preemption - Preemption 속성을 가지지 않은 resource에.. 2020. 11. 29.
[OS] 8. Synchronization 1. 개요 - 하나의 프로세스에서 2개 이상의 Thread가 Concurrent하게 작업할 때 같은 Address space를 공유하기 때문에 같은 Data를 사용할 수 있다. - 이 상황을 Race Condition이라고 하고 이는 Non-deterministic한 결과를 낳는다. - Race Condition 때 발생하는 문제를 해결하기 위해 Synchronization을 수행한다. cf) Scheduling은 OS 권한으로 프로그래머가 통제할 대상이 아님. 2. Critical section : 임계영역 - 공유되는 자원(resource)를 사용하는 Code 부분 3. Lock 프로세스의 shared resource에 대한 점유 상태를 나타내는 것으로써 상호배제(Mutual Exclusion : M.. 2020. 11. 29.
[OS] 7. Process Scheduling(2) 1. Advanced Scheduling 1) Proportional share scheduling - 프로세스 별로 비율을 정해서 CPU를 사용하는 것 2) Real time system - deadline이 있는 system Soft real time system deadline에 맞추려고 하지만 보장은 없는 system hard real time system deadline에 맞춰지지 않으면 치명적인 system 따라서 preemptive priority-based scheduling이 되어야 한다. 2. Way to guarentee deadline Interval > Deadline > Processing time이면 deadline은 보장된다. * reate of periodic process.. 2020. 11. 18.
[OS] CPU, Processor, Core, Process, Thread 그리고 관계 정리 1. HW 1) CPU : Central Processing Unit, 중앙처리장치 간단하게 컴퓨터의 뇌로써 '사고'를 담당 기억, 연산, 제어를 담당 cf) MPU, MCU - MPU : Micro Processing Unit CPU의 한 종류로써, 전자부품과 반도체칩을 하나의 작은 칩에 내장한 형태의 CPU - MCU : Micro Controller Unit CPU(또는 MPU) 및 RAM, ROM, I/O 제어회로를 단일 칩에 모두 내장한 것을 의미 한 개의 소자로 하나의 컴퓨터 기능을 수행한다 2) Processor 컴퓨터 운영을 위해 기본적인 명령어에 반응하고 처리하는 논리회로 디바이스가 해야할 일을 총 지휘하는 프로세서를 CPU라고 함(보통 프로세서와 CPU를 같은 의미로 사용) 이외의 프로.. 2020. 11. 4.
[OS] 5. Thread 1. Thread - Sequence of instruction of program : 실행의 흐름 - 프로세스로부터 execution state를 분리한 것 상태 원소 비고 Static state code, global variable, heap, opened files... Thread간 공유 Execution state PC, SP, stack Thread간 공유X - 사용하는 이유 1) multi core의 충분한 활용 : 하나의 프로세스는 하나의 프로세서로 mapping되기 때문 * 프로세서와 CPU는 비슷한 의미, core는 이들에 속해있는 원소라고 보면됨 2) 여러 process를 IPC하는 것은 overhead 발생 및 잦은 context-switch로 비용, 시간 관점에서 비효율적 3) .. 2020. 11. 3.
[OS] 4. 프로세스(2) 1. PCB(Process Control Block) 프로세스는 각각 자신의 PCB를 갖고 있으며 PCB는 프로세스에 대한 모든 정보를 포함한다. 2. IPC(Inter-Process Communication) 프로세스는 기본적으로 서로에게 간섭할 수 없고 독립적이지만 필요에 따라 협력할 수 있고, 이유는 다음과 같다. 1) 정보교환 2) 계산 가속화 : 특정 Task를 sub task들로 나누어 가속화하기 위해 병렬로 처리 3) 모듈성 : 기능에 따라 별도의 프로레스 또는 스레드로 나누어 모듈식 형태로 시스템을 구성하기를 바랄 때 4) 편의성 : 개별 사용자들이 동시에 작업할 많은 Task를 병렬로 처리하기 위해 3. IPC Model 1) Shared memory - 프로세스가 OS에게 명확하게 공유.. 2020. 11. 2.
[JAVA] 변수와 메서드 1. 선언 위치에 따른 변수의 종류 종류 선언위치 생성시기 비고 저장위치 멤버변수 클래스변수 클래스영역 클래스가 메모리에 올라갈 때 - 키워드 static를 붙여 표시 - 모든 인스턴스가 하나의 클래스 변수 저장공간을 공유 Method area 인스턴스변수 인스턴스가 생성되었을 때 - 독립적인 저장공간을 가짐 Heap 지역변수(로컬변수) Method 영역 변수 선언문이 수행되었을 때 (메서드 종료 시 소멸) Stack 2. 메서드 - 클래스 메서드는 같은 클래스 내의 인스턴스 메서드, 변수를 호출할 수 없다. : 클래스 메서드가 실행될 때 인스턴스 메서드, 변수가 아직 생성되지 않았을 수도 있기 때문이다. 즉, 클래스 메서드는 인스턴스 메서드, 변수를 쓰는 메서드가 아니다. 따라서 인스턴스를 사용하는 클.. 2020. 10. 30.

티스토리툴바