justgo_developer

교착상태(Deadlock): 멀티프로세싱 환경에서 여러 프로세스가 간섭하여 생기는 문제-> 다수의 프로세스가 특정자원의 할당을 무한정 기다리고 있는 상태 Deadlock의 조건1. Mutual exclusion: 한번에 오직 하나의 프로세스만 자원을 사용가능2. Hold-and-wait: 프로세스가 할당된 자원을 점유하고 다른 프로세스가 반납하는걸 기다리는 상태3. No preemption: 프로세스의 할당된 자원은 강제로 빼앗을수 없다.4. Circular wait: 프로세스 자원요구가 순환적 Deadlock Prevention(데드락 예방): deadlock이 발생할 4가지 조건중 하나라도 제거하자1. Mutual Exclusion - 사용하지 않음/동시접근 허락되지 않음2. Hold and Wait..

prim의 알고리즘- 임의의 노드를 출발노드로 선택- 출발 노드를 포함하는 트리를 점점 키워 감- 매 단계에서 이미 트리에 포함된 노드와 포함되지 않은 노드를 연결하는 에지들 중 가장 가중치가 작은 에지를 선택 가중치가 최소인 에지 찾기- VA: 이미 트리에 포함된 노드들- VA에 아직 속하지 않은 각 노드 v에 대해서 다음과 같은 값을 유지- key(v) : 이미 VA에 속한 노드와 자신을 연결하는 에지들 중 가중치가 최소인 에지(u,v)의 가중치- ㅠ(v) : 그 에지 (u,v)의 끝점 u r:출발점 key값이 최소인 노드 찾기- 최소 우선순위 큐를 사용: V-VA에 속한 노드들을 저장: Extract-Min : key값이 최소인 노드를 삭제하고 반환

서로소인 집합들의 표현- 각 집합을 하나의 트리로 표현배열 parent를 만들어 모든 트리를 하나의 배열로 표현 -자신이 속한 트리의 루트를 찾음FIND-SET(x)if x≠p[x]then p[x]