CS (51) 썸네일형 리스트형 최소 공통 조상 LCA: Lowest Common Ancestor LCA: Lowest Common Ancestor 트리의 노드들 중 공통 조상을 찾는 알고리즘이다. DFS, BFS를 통해 한 노드에서 시작해 모든 간선을 확인해볼수도 있겠지만 이 방법을 사용하면 더 빠르게 찾아낼 수 있다. 위의 상황에서 12번노드와 6번노드의 최소 공통 조상을 찾아보자. 최소 공통 조상은 누가봐도 3이다. 그렇다면 알고리즘으로 어떻게 풀어낼 수 있을까? 레벨을 맞춘다. LCA에서 중요한 것은 레벨을 맞춰야한다. 즉 LCA(6, 12) = LCA(6, 7) 과 같다. 이처럼 레벨(깊이)를 맞춰준 후 동시에 하나씩 조상을 탐색하는 것이 LCA이다. DFS 전처리 LCA를 위해서는 각 노드가 조상의 정보와 레벨의 정보를 가지고 있어야한다. 이를 위해 dfs 전처리가 필요하다. 만들어진 노드.. DeadLock (교착상태) DeadLock이 무엇이고 언제 발생하는지 저번 포스팅에서 이야기 했지만 복습해보면 두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 무한정 대기하는 상태를 교착상태라고 한다. 현실 세계에서 두 차량(프로세스)이 하나의 도로(자원)에 들어가려고 할 때, 둘 중 하나가 양보하지 않는 이상 이 자원에는 누구도 도달할 수 없다. 교착상태의 해결법 예방 교착상태를 예방하려면 어떻게 해야할까? 교착상태는 4가지 필요조건이 있다. 그렇다면 이 조건 중 하나라도 만족하지 않으면 교착상태는 일어나지 않을 것이다. 상호 배제 부정 : 하나의 자원을 여러 프로세스가 접근 가능 → 현실성 X 점유대기 부정 : 프로세스가 실행 전 모든 자원을 할당, 식사하는 철학자의 경우 수저를 한 번에 듦 선점 가능 : 이미 실행.. OS - 식사하는 철학자 문제와 교착상태(DeadLock) 식사하는 철학자 문제 철학자들은 밥먹고 생각하는게 일이다. 참 팔자 좋은 인생들.. 아무튼, 그들은 밥상 머리 앞에서도 생각을 한다. 한 입 먹고 내려놓고 생각하고 한 입 먹고 내려놓고 한다. 그런데 사람이 5명인데 젓가락도 5개다. 쌍이 아니라 5개다. 원형 탁자에 앉아있다고 가정하면 다음과 같은 사진이 될 것이다. 1번 철학자가 양쪽 젓가락을 들었다고 하자. 그렇다면 2번과 5번은 젓가락이 하나밖에 없기 때문에 밥을 먹을 수 없다. 계속 철학자들은 밥을 먹고 내려놓고 생각하고 반복한다. 그런데, 언젠가 이런 일이 생긴다. 3번이 오른쪽 젓가락을 들었을 때 4번이 오른쪽을 들고 … 즉, 모두가 자신의 오른쪽 수저를 들어버리는 것이다. 이렇게 되면 어떻게 될까 . 아무도 밥을 먹을 수 없다! 아무도 젓가.. 전통적인 동기화 문제 은행동기화 문제 같이 우리 실생활에서 사용되는 문제들도 있지만 예전부터 전통적으로 문제가 되는 문제들이 있다. 이를 전통적 동기화 문제라고 한다. Producer and Consumer Problem 생산자 소비자 문제 생산자는 데이터를 생성하고 소비자는 그 데이터를 소비한다. 예를들어 컴파일러가 데이터를 컴파일하면 어샘블리 코드가 되고 어셈블리어를 번역하여 기계어가 된다. 생산자는 데이터를 생성하고서 바로 소비자에게 넘기지 않는다. I/O차이, 연산차이 등 속도를 맞추기 위해 먼저 buffer에 데이터를 삽입하고 이후 소비자가 버퍼에 접근해 take 하는 식으로 처리된다. 즉, 버퍼는 생산자와 소비자가 모두 접근하는 Critical Section이 되는 것이다. 이를 해결하기 위해 상호배재를 위한 세마.. OS - 임계구역과 세마포어 Critical Section 공통 자원을 건드릴 수 있는 공간이다. 멀티 프로세싱에 의한 오류는 보통 여기서 발생한다. 해결 방안이 갖춰야하는 것 Mutual exclusion - 오직 한 쓰레드만 진입 Progress - 진입 결정은 유한 시간 내 Bounded waiting - 어느 스레드라도 유한 시간 내에 해결해야함. 프로세스/쓰레드 동기화 임계구역 문제 해결 (틀린 답 X) 프로세스 실행 순서 제어 비효율성 제거 세마포어 유명한 동기화 해결 도구 acquire() release() 세마포어는 상호베타를 위해 사용한다. void acquire(){ value--; if(value < 0){ add this process/thread to list block } } void release(){ v.. OS - 프로세스 동기화 개념 프로세스 동기화 프로세스 병행 (Concurrency) OS는 아주 빠른 시간에 프로세스를 스위칭한다. 때문에 사실은 하나의 프로세스만 화면에서 실행중이지만 마치 함께 실행중인 것 처럼 보인다. 이것을 프로세스 병행, 동시성이라 한다. 독립 프로세스와 협력 프로세스 독립 프로세스 단일 처리 시스템에서 수행하는 병행 프로세스, 다른 프로세스와 영향을 받지 않으며 독립적으로 실행된다. 협력 프로세스 우리가 사용하는 많은 프로그램은 협력 프로세스이다. 두 프로세스가 동일한 파일을 사용할 수도 있고 프로세스 하나가 파일을 읽는 동안 다른 프로세스가 쓰기를 실행하려 할 수도 있다. 프로세스 동기화 위 처럼 프로그램들이 하나의 자원에 접근하려하면 어떤 일이 발생할까. 가장 유명한 예제는 바로 은행 예제이다. A씨의.. OS - CPU 스케줄링(3), 프로세스의 생성과 소멸, 쓰레드 MultiLevel Queue 스케줄링 다단계 큐 스케줄링은 이전에 봤던 것 처럼 하나의 큐를 사용하는 것이 아닌 여러개의 큐를 사용하는 방법이다. 앞어 많은 프로세스들이 있었는데 운영체제 단계에서 인터럽트를 처리하는 프로세스도 있고 사용자와 인터랙티브하는 프로세스, 배치 프로세스, 컴파일러 등 많은 프로세스가 있는데 이들을 같은 큐로 관리하기 어렵기 때문에 나온 개념이다.' 위의 순서대로 우선순위가 매겨져 각 큐는 절대적인 우선순위를 가진다. 아래의 프로세스 큐가 실행되려면 위의 프로세스 큐가 모두 비어있어야한다. 만약 Interactive Processes가 실행되고 있던 중 System Processes작업이 큐에 들어오면 바로 프로세서를 반납해야한다. 각각의 큐는 독립된 스케줄링 기법을 사용한다... OS - CPU 스케줄링(2) CPU 스케줄링은 Ready Queue의 프로세스들 중 무엇을 우선으로 cpu에 할당할지 정하는 스케줄링 기법이다. Shortest-Job-First First Come First Service (FCFS)는 들어온 순서부터 서비스하는 기법이었다. SJF는 가장 작업시간이 빠른 작업부터 서비스하는 것이다. 선점 vs 비선점 SJF는 선점과 비선점 방법 둘 다 구현할 수 있다. 선점: cpu가 일단 작업을 시작하면 프로세스가 종료되기 전 까지는 서비스 하는 프로세스를 변경하지 않는 방법이다. 비선점: cpu가 작업을 하고 있어도 작업을 빨리 끝낼 수 있는 프로세스가 들어온다면 그것 부터 처리한다. 이 방법은 최소 잔여 시간 방법으로도 불린다. 단, 이 방법은 우리의 컴퓨터에 실제로 적용하기는 힘들다. Pr.. 이전 1 2 3 4 5 6 7 다음
