오래 못 할 짓 하지 않기

BI - Connected Component : Undirected + Maximal biconnected subgraph  ● Articulation Point: Vertex V가 사라졌을 때 하나의 Component가 2개로 나눠질 때!  해부학적으로는 '관절'이라 생각하면 될 것 같다.  = 다리에서 무릎 관절 역할!   ▶ BI-Connected 라는 것은  하나의 Vertex가 사라져도 하나의 Component가 분해되지 않는 것!! 위 그래프는 Bi-Connected가 아니다. 이걸 쪼개면 오른쪽같은 단위로 쪼갤 수 있고, 그만큼이 Articulation Point라는 뜻이므로Articulation Point가 존재한다는 건 Bi-Connected가 아니라는 것!     이렇게 생긴 Tree에..

DeadLock System Model 우리가 사용하는 Thread / CPU의 System Model을 먼저 보자. 우리는 정해진 수의 Resource와 Thread가 있다.이 Thread가 Resource를 사용하기 위해서는 다음 3단계를 거친다.               1. Request            > 사용 중이라면 기다려야한다.        2. Use        3. Release    ● Deadlock State 란: 해당 Thread가 다른 Thread에 의해서만 일어날 수 있는 Event 를 기다리는 상태! 우리는 이번에 Resource에 대한 Acquisiton 과 Release에 관련된 Event만 고려할 것이다.   - do work one에서는 first mutex를 ..

Posix SynchronizationPosix에서는 Synchronization을 위한 API를 제공한다.Mutex LockSemaphoreCondition Variable이는 리눅스, 맥OS 등 여러 곳에 쓰인다. 딱히 자세히 볼 건 없는 것 같으니 PPT 에서 슥 보자.    Synchronization in Java JAVA에서도 Synchronization을 위한 API를 제공한다.Java monitorReentrant lockSemaphoreCondition Variable● JAVA Monitor 특징: 자바에서 Method 를  Synchronized로 선언하면,그 Method를 부르는 Thread는 해당 Object에 대한 Lock을 가지고 있어야 한다. 만약 다른 Thread가 사용하고..

Liveness: Process가 자신의 Execution life cycle내에 일을 진행할 수 있게 보장해주는 Properties 이게 깨지는 이유는 다음 3가지가 있다. DeadlockPrioirity Inversion기타 등등... ● Deadlock: 두 개 이상의 프로세스가 무한정으로 특정 프로세스에 이벤트가 생기길 기다리는 것  P0과 P1가 있다고 해보자. P0 먼저 실행시키자.▶S,Q가 반납될 때까지 아무것도 안 하고 기다릴게 P1 실행▶ Q,S가 반납될 때까지 아무것도 안 하고 기다릴게 근데 둘 다 기다리는 게 끝나야 S와 Q를 반납함.서로가 서로를 기다리는 상황 세마포어 키를 1로 설정해둔다.(1개만 Critical 가능)P0가 실행하면 S를 기다림P1은 Q를 기다린다. 그렇다면, P..

Sychronization 의 개념이나 필요한 기술들을 알아봤다. 이젠 어떤 Tool들이 있는지 알아보자.크게 나누면 4가지가 있다. ● Mutex Locks ● Semaphores ● Monitors ● Liveness  ● Mutex LocksMutex = Mutual Exclusive ▶ 특징 : 가장 간단한 방법이다. ▶ 모든 프로세스가 공유하는 하나의 열쇠의 역할을 하는 변수를 만들고    Critical section에 진입할 때 열쇠를 받고, 나올 때 열쇠를 반납하는 개념이다.  열쇠를 받을 땐 acquire 함수를 사용한다.Critical section에 들어갈 때는 열쇠를 false로 바꿔서다른 프로세스들이 사용하지 못하게 한다. 반대로 열쇠를 반납할 땐 release 함수를 사용하여 ..

DAG에서 Dependency가 있는 그래프에서각각의 Task의 Duration이 정해져있다.  외출하는 데 필요한 작업들은 다음과 같다.하지만 이 중에서도 순서가 중요함.   Time Complexity는 세타 ( Vertex + Edge ) 우리가 각 노드에 대해서 알아야 하는 건- Earliest start time ( EST )         =  앞에 완료되어야 하는 애가 끝난 시간 - Earliest finish time ( EFT ) 이다.    = EST + Duration    EST 를 계산하는 건Dependency가 있는 노드의 앞에 완료되어야 하는 작업이 있다면그 작업 중에 가장 Max로 끝나는 시간으로 한다.  Vertex가 Weight에 영향을 받는다는 개념으로 풀어야 한다.방향..

https://witch.work/posts/os-5https://velog.io/@chy0428/OS-HW-support-for-Synchronization 위 두 블로그에 정리 잘 되어 있음.   우선 동기화와 관련하여 생기는 문제를 해결하는 방법은 여러 가지가 있다.하지만 어떠한 방법이든 다음 3가지 조건을 충족해야한다. 1. 상호 배제 ( Mutual exclusion )   : Critical section에는 1개의 프로세스만 접근할 수 있다. 2. 진행 ( Progress )   : 자신의 Critical section에 실행되고 있는 프로세스 X     and Critical section에 들어오려고 하는 프로세스가 있을 때     → 무기한 연기되지 않고 Critical section에..

Topological sort위상 정렬 DAG 에서 이루어진다.= Directed Acyclic Graph ( 비순환 방향 그래프 ) 위상 정렬이란 DAG에서 정점을 선형으로 정렬하는 것을 말한다.   (u,v) 이렇게 있는 Edge는 u먼저 오고 그 뒤에 v가 오는 Edge를 말한다.    우선 DFS로 한 번 돌리고Finished Time가 큰 순서대로 정렬을 한다.  주로 예시로는 옷을 입는 걸로 예시를 들 수 있다.  우선 (자신을 가리키는 게 없는 vertex에 한해서) 어디서 먼저 시작하든제대로 된 결과가 나올 것이다. Pants 를 먼저 입으면 안 되고, 그 전에 Underwear를 항상 먼저 입어야 하며,Watch같은 경우는 무엇을 하든지 중간에 끼어들어서 할 수 있다. Finish Tim..

Depth First Traversal 들어갈 수 있는만큼 최대한 들어갔다가 나오는 것 ● BFS = Level order   →  같은 레벨들 차례차례 보고 내려감 ● DFS = Pre in Post order로 할 수 있음→ 인접해있는 아래 노드로 쭉 내려감→ 다 Explore 했으면, Backtrack 하여 돌아온다.    = 어디서 왔는지 알아야 함     = Stack 형식으로 구현한다.     특징) 1. 인접한 Vertex가 이미 Discover되었다면,     그 사이에 있는 Edge는 Explore는 되지 않지만, Check는 되었다고 할 수 있다. 2. 색깔별 의미    ● White  : Discover되지 않음    ● Gray    : Discover 되었지만 작업하지는 않음  (..

Graph Traversal: Graph G에 있는 모든 Vertex를 방문하는 것이다.  ● 모든 Vertex를  ● 한 번만 방문하는 알고리즘 2가지1) BFS ( Breadth First Search ) - QUEUE 로 구현2) DFS  ( Depth First Search )   - STACK으로 구현   BFS ( Breadth First Search )(Tree 형태 기준) Level Order 방식 Root 로 설정한 노드에서 연결되어있는 노드들을 Discover 하고 , 그 사이에 있는 Edge를 Explore 했다고 할 수 있다.+ Discover and Explore의 기준은 목적지에 있는 노드가 Discover 되지 않았을 때  1. Root 노드인 A → 연결되어있는 B,C 를 (..