개발공부 블로그

http://www.kocw.net/home/m/search/kemView.do?kemId=1046323 운영체제 강의를 듣고 정리한 내용입니다 Priority Scheduling 우선순위 스케줄링 우선순위가 높은 프로세스에게 CPU를 할당한다 우선순위는 정수값으로 표현된다 (작은숫자가 높다) - preemptive - nonpreemptive SJF 스케줄링도 일종의 우선순위 스케줄링이다 문제점 : 경우에따라 영원히 할당받을 수 없을정도로 우선순위가 밀릴 수 있다 해결 : Aging을 사용한다 Aging(에이징) 아무리 우선순위가 낮은 프로세스여도 기다리는 시간이 길어질수록 우선순위를 앞당겨준다 Round Robin 스케줄링 각 프로세스는 동일한 크기의 할당시간을 가진다 (time quantum) 할당..

힙, 트리 트리 노드의 제일 위를 트리의 root라고 한다 자식이 딸려 있지 않은 부분은 leaves이다 탐색할때는 뿌리를 통해서 접근한다 간선 edge 두 노드를 연결하는 선 간선의 수에 따라 level을 나눈다 트리의 각각의 요소 : 노드 트리의 자료구조 Heap 규칙 1 부모 노드가 자식 노드보다 크다 -> 최대 힙 MAX HEAP 2 부모 노드가 자식 노드보다 작다 -> 최소 힙 Min HEAP 둘 중 어느 방법을 사용해도 무관하다 가장 큰 숫자가 뿌리에 있게 하려면 최대 힙, 가장 작은 숫자로부터 시작하려면 최소 힙을 사용하면 된다 트리에서의 높이 루트에서 가장 먼 잎까지 가는데 거치게 되는 간선의 개수이다 최대 힙에서 노드의 개수 n, level, height, log_2(n+1) -1log ..

add와 remove 메서드 해시를 추가하는 add 메서드 (boolean 반환) public boolean add(K key, V value) { //제네릭 타입 지정 x if(loadFactor() > maxLoadFactor) resize(tableSize * 2); //새로운 테이블의 크기를 계산 HashElement he = new HashElement(key, value); //새로 추가할 요소 생성 int hashval = key.hashCode(); //추가할 인덱스 탐색 hashval = hashval & 0x7FFFFFFF; hashval = hashval % tableSize; harray[hashval].add(he); //요소추가, 추가하는 방식은 상관 없다 numElements+..

재해싱 충돌을 피하기 위한 대표적인 방법으로는 해시 체인이 있다 -> 배열의 칸마다 리스트를 배정하는 방식 자료구조가 할당될수록 크기를 조정해야 한다 체인해시에서 해시가 너무 많이 할당되면 마찬가지로 크기 조정을 해야 한다 -> 새로운 해시로 모든 요소를 옮겨야 한다 객체를 해시에 추가하려면 우선적으로 hashCode 메서드를 호출해야 한다 int hv = x.hashCode(); hv = hv & 0x7FFFFFFF; hv = hv % tableSize; 다시 찾거나 제거하고자 할 때 위치 0의 연결리스트를 위치 0으로 옮기면 안된다 배열을 크기를 조정하면서 테이블의 크기가 바뀌었기 때문이다 ->각 요소의 위치를 초기화 한 후, 처음부터 다시 위치를 지정해야 한다 새로운 테이블에 빈 연결리스트를 만든 ..

해시충돌을 방지하기 위한 방법 1. 선형 조사법 2. 2차식 조사법 3. 이중 해싱 선형 조사법 찾고자 하는 값을 찾을 때까지 뒤로 간다 빈 공간을 찾을 때까지 자료구조를 살펴본다 자료구조가 차면서 추가된 객체를 찾기 위해 더 많은 칸을 살펴봐야 한다 요소를 제거 할 때 가운데에 있는 요소를 지우고자 할 때 이 요소를 제거하고 이 칸을 null로 설정하는 방식은 사용할 수 없다 -> 나중에 찾고자 하는 요소가 있을 때 중간에 null이 있을 때 null 뒤의 값을 찾을 수 없기 때문이다 어떤 요소가 존재했지만 비었다는 표시를 해야한다 해시값에서 시작해서 null에 도착할 때까지 1씩 더하고 그 위치에 저장한다 -> 추가보다는 제거가 까다롭다 관계가 있든 없든 데이터가 뭉치게 된다 -> 선형 조사법의 비효..

http://www.kocw.net/home/m/search/kemView.do?kemId=1046323 운영체제 강의를 듣고 정리한 내용입니다 CPU scheduling Scheduling Criteria CPU utilization (이용률) CPU를 가능한 바쁘게 일을 시켜야 한다 -> 사용률을 의미 Throughput(처리량) 주어진 시간내에 CPU가 일을 많이 처리해야한다 -> 처리량을 의미 Waiting time(대기 시간) CPU를 기다리는 시간을 말한다 Response time(응답 시간) 처음으로 CPU를 얻기까지 걸린 시간을 말한다 -> 총 수행시간 FCFS(First-Come-First-Served) 프로세스의 도착 순서가 순차적이다 SJF(Shortest-Job-First) CPU를..

http://www.kocw.net/home/m/search/kemView.do?kemId=1046323 운영체제 강의를 듣고 정리한 내용입니다 Message Passing Message system 프로세스 사이에 공유 변수(shared variable)를 일체 사용하지 않고 통신하는 시스템을 말한다 Direct Communication 통신하려는 프로세스의 이름을 명시적으로 표시한다 Process P ---> Process Q Indirect Communication mailbox(혹은 port)를 통해 메시지를 간접적으로 전달한다 Process P -----> Mailbox M ------>Process Q -> Direct Communication, Indirect Communication 둘 다..

http://www.kocw.net/home/m/search/kemView.do?kemId=1046323 운영체제 강의를 듣고 정리한 내용입니다 프로세스 간 협력 독립적 프로세스 프로세스는 각자의 주소 공간을 가지고 수행되므로 원칙적으로 하나의 프로세스는 다른 프로세스의 수행에 영향을 끼지치 못한다 협력 프로세스 프로세스 협력 메커니즘을 통해 하나의 프로세스가 다른 프로세스의 수행에 영향을 미칠 수 있다 프로세스 간 협력 메커니즘 (IPC :Interprocess Communication) 메시지를 전달하는 방법 message passing : 커널을 통해 메시지 전달 주소 공간을 공유하는 방법 shared memory : 서로 다른 프로세스 간에도 일부 주소 공간을 공유하게 하는 shared memor..

http://www.kocw.net/home/m/search/kemView.do?kemId=1046323 운영체제 강의를 듣고 정리한 내용입니다 프로세스의 생성(Process Management) 부모 프로세스가 자식 프로세스를 생성한다 -> 프로세스의 문맥을 복제 생성 프로세스의 트리(계층 구조) 형성 Copy-on-write(COW) 운영체제 메모리관리 파일 시스템에 자주 쓰이는 용어로 write가 발생했을 때 복사를 한다는 의미이다 그 이전까지는 부모의 문맥을 공유한다 -> 효율적인 운영체제에서는 주소 공간만을 공유하여 사용한다 프로세스는 자원을 필요로 한다 자원을 받는 방식 운영체제로부터 받는다 부모와 공유한다 자원의 공유 부모와 자식이 모든 자원을 공유하는 모델 일부를 공유하는 모델 전혀 공유하..

Thread 프로세스 내부에 CPU 수행 단위가 여러 개 존재하는 것을 말한다 주소공간의 구조 (Thread 추가) Thread1의 Stack/ Thread2의 Stack / Thread3의 Stack data code Thread의 구성 program counter register set stack space -> program counter가 코드의 어느 부분을 가리키는지, register의 값이 어떻게 되는지를 stack에 쌓는다 Thread가 동료 쓰레드와 공유하는 부분(task) code section data section OS resources 정통적인 개념의 heavyweight proces는 하나의 Thread를 가지고 있는 task라고 볼 수 있다 프로세스 안에 쓰레드를 여러 개 두는 ..