개발공부 블로그

http://www.kocw.net/home/m/search/kemView.do?kemId=1046323 운영체제 강의를 듣고 정리한 내용입니다 *문제점 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다 해결을 위한 알고리즘 두 개의 프로세스 P0, P1가 있다고 가정한다 프로세스들의 일반적인 구조 do { entry section critical section exit section remainder section } while(1); 프로세스들은 수행의 동기화(synchronize)를 위해 몇몇 변수를 공유할 수 있다 -> synchronization variable 프로그램적 해결법의 충족 조건 가정 모든 프로세스..

http://www.kocw.net/home/m/search/kemView.do?kemId=1046323 운영체제 강의를 듣고 정리한 내용입니다 Process Synchronization 프로세스 동기화 데이터의 접근패턴 어떤 위치에 있던 간에 저장되어 있는 위치를 읽어와서 연산 후 다시 저장하는 방식으로 데이터를 접근한다 S-box -> Memory Address Space -> 디스크, 프로세스의 메모리 주소 공간 E-box -> CPU Process -> CPU, 컴퓨터 내부, CPU 프로세스 s-box를 공유하는 e-box가 여러 개 존재하는 경우 Race Condition의 가능성이 있다 -> 경쟁상태 race condition이 발생하는 경우 kernel 수행 중 인터럽트 발생 시 프로세스가 ..

http://www.kocw.net/home/m/search/kemView.do?kemId=1046323 운영체제 강의를 듣고 정리한 내용입니다 CPU가 여러개 있는 경우의 스케줄링 CPU가 여러 개인 경우 스케줄링은 더욱 복잡해진다 Multiple-Processor Scheduling Homogeneous processor Queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우 문제가 더 복잡해진다 Load sharing 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘이 필요하다 별개의 큐를 두는 방법과 공동 큐를 사용하는 방법이 있다 Symmetric Multiprocessing(SMP) 각 프로세서..

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 둘 다..