강 연결 성분(Strongly Connected Component)이란? 강 연결 성분이란 방향 그래프에서 연결 성분 내의 임의의 두 정점 u와 v에 대해서 u에서 v로 가는 경로가 있는 동시에, v에서 u로 돌아오는 경로가 있는 연결 성분이다. 강 연결 성분은 그 정의의 특징 상 단절 정점이나, 다리 간선을 포함하지 않는데, 생각해보면 당연하다. 강 연결 성분 내의 특정 정점을 제거함으로써, 두 개 이상의 연결 성분으로 나뉘지도 않고 그러한 간선도 존재하지 않는다. 아래 그림을 살펴보면, 그 의미를 더욱 쉽게 파악할 수 있을 것이다. 색이 같은 정점들을 한번 살펴보면, 임의의 두 정점에 대해서 오고 가는 길이 있다는 것을 확인할 수 있다. 반대로, 색이 다른 정점끼리 오고 가려면, 어느 한 방향은 막히..
* 이 글은 알고리즘에 관해 학습하며 정리한 글입니다. 틀린 점이나, 고쳐야 할 부분이 있으면 알려주세요..! 위상 정렬이란? 위상 정렬이란(Topological Sort) : 사이클이 없는 방향 그래프(Directed Acyclic Graph, DAG)에서 정점을 선형순서로 나열하는 것이다. 이때 DAG, 즉 사이클이 없는 방향 그래프란 주로 노드들 간에 우선순위를 나타내기 위해서 사용한다. 만약 노드들간에 사이클이 존재한다면, DAG라고 볼 수 없다. 즉, 우선 순위가 존재하는 노드들 간에 순서를 나타낸 것인데, 만약 우선순위가 동일하다면 그 중 임의의 하나를 선택한다. 그래서 위상 정렬은 여러 값이 나올 수 있다. 일반적으로 위상 정렬을 사용하는 때는 의존 관계가 존재할 때, 수행 가능한 작업 순서..
파일 시스템에서의 Data Blcok 파일에서는 Block이라고 하는 것을 저장단위로 사용한다.이 Block 하나의 크기는 4096바이트이다. 디스크에서 파일을 저장할 때, Block을 무작위로 저장하지는 않는다. 어떻게 배치하느냐에 따라 그 전략이 달라진다.우선, 지금은 잘 사용하지 않는 _Contiguous Allocation_에 대해 알아보자. Contiguous Allocation 이름을 보고 유추할 수 있듯이, _Contiguous Allocation_방식은 파일을 저장할 때 연속적으로 Block을 배치한다.이 방식을 사용하면 File Allocation Table을 사용하는데, 여기에 파일의 시작 Block과 Block의 길이를 저장한다. 물론 파일의 FCB에서도 파일의 시작 Block..
세마포어(Semaphores)란? 지금까지 Critical Section Ploblem을 소프트웨어/하드웨어적으로 해결하는 방법을 찾아봤다. 소프트웨어적인 방법으로는 세 가지 솔루션이 있었고, 하드웨어적인 방법에는 Testset 인스트럭션을 사용했다. 조금 더 나은 방안은 하드웨어적으로 해결하는 것이라 하였는데, Testset 역시나 Busy Wating을 해야하는 큰 단점이 있다. 세마포어는 Busy Wating을 해결하는 효율적인 방법을 제시한다. 세마포어 자체만으로는 Int 값을 저장할 뿐인 구조체일 뿐이지만, _semWait (s)_와 _semSignal (s)_을 통해서 손쉽게 Critical Section Ploblem을 해결한다. semWait (s) semiphore의 값을 1 감소 시킨다..
Operation System의 발전 이전에는 Operation System이 없었기 때문에 직접 수동으로 하드웨어 장치를 제어하였다. 하지만 이러한 방법은 너무 효율이 떨어졌기에 모니터라는 것을 만들게 되었다. 모니터는 일련의 과정을 제어하는 소프트웨어이다. 따라서 프로그램들이 묶여있으며 그 순서대로 실행될 수 있도록 도와준다. 그리고 이렇게 여러 개의 프로그램들을 묶어놓고 있다가 차례로 하나씩 실행시켜 놓는 방식을 일괄 처리 즉, Batch System이라고 한다. 모니터는 이러한 Simple Batch System 안에서 일련의 과정들이 차례로 수행되었다. Uni-programming 위 그림은 Uniprogramming의 CPU의 동작 방식을 나타낸 것이다. _Run_이라는 상자가 있는 동안에는 ..
