강 연결 성분(Strongly Connected Component)이란? 강 연결 성분이란 방향 그래프에서 연결 성분 내의 임의의 두 정점 u와 v에 대해서 u에서 v로 가는 경로가 있는 동시에, v에서 u로 돌아오는 경로가 있는 연결 성분이다. 강 연결 성분은 그 정의의 특징 상 단절 정점이나, 다리 간선을 포함하지 않는데, 생각해보면 당연하다. 강 연결 성분 내의 특정 정점을 제거함으로써, 두 개 이상의 연결 성분으로 나뉘지도 않고 그러한 간선도 존재하지 않는다. 아래 그림을 살펴보면, 그 의미를 더욱 쉽게 파악할 수 있을 것이다. 색이 같은 정점들을 한번 살펴보면, 임의의 두 정점에 대해서 오고 가는 길이 있다는 것을 확인할 수 있다. 반대로, 색이 다른 정점끼리 오고 가려면, 어느 한 방향은 막히..
세마포어(Semaphores)란? 지금까지 Critical Section Ploblem을 소프트웨어/하드웨어적으로 해결하는 방법을 찾아봤다. 소프트웨어적인 방법으로는 세 가지 솔루션이 있었고, 하드웨어적인 방법에는 Testset 인스트럭션을 사용했다. 조금 더 나은 방안은 하드웨어적으로 해결하는 것이라 하였는데, Testset 역시나 Busy Wating을 해야하는 큰 단점이 있다. 세마포어는 Busy Wating을 해결하는 효율적인 방법을 제시한다. 세마포어 자체만으로는 Int 값을 저장할 뿐인 구조체일 뿐이지만, _semWait (s)_와 _semSignal (s)_을 통해서 손쉽게 Critical Section Ploblem을 해결한다. semWait (s) semiphore의 값을 1 감소 시킨다..
Process Control 실행 모드 User Mode 낮은 권한을 가진다. System Mode(=Kernel Mode, supervisor mode) 높은 권한을 가진다. 이전에 Virtual Memory Space에 대해서 배울 때 해당 공간에도 커널이 있었음을 기억해 보자. 여기에 있는 커널은 메인 메모리로부터 복사된 것일까? 그렇지 않다. 실제로는 Main Memory 상의 커널이 매핑되어 그렇게 보이는 것 뿐이다. 프로세스는 user mode와 kernel mode를 번갈아 가면서 Mode change를 진행한다. 즉, CPU가 끊임없이 하나의 프로세스만을 차지하는 것처럼 보이지만 실제로는 그렇지 않다는 것이다. 실제로는 굉장히 빠른 속도로 Mode를 바꾸어간다. 다시 말해 A라는 task가..
데이터의 종류는 아날로그 데이터일 수도 있고, 디지털 데이터일 수도 있다. 이번 포스팅에서는 디지털 신호를 디지털 신호로 변환하는 방법을 알아볼 것이다. 그러한 방법에는 라인 코딩과 블록 코딩 두 가지 방식이 있는데 라인 코딩에 대해 먼저 배워보자. Line Coding 라인 코딩은 디지털 데이터를 디지털 신호로 변환하는 과정이다. 인코더는 디지털 데이터를 디지털 신호로 인코딩하고, 디코더는 디지털 신호를 디지털 데이터로 디코딩하는 역할을 맡는다. 이때, 인코딩과 디코딩에 대한 규칙을 정해놓은 것이 라인 코딩의 정확한 의미이다. 뭐 사실 규칙이라고 해봤자, 결국 짧은 시간 안에 많은 데이터를 송신하는 것을 데이터 통신의 목적으로 둔다. 조금 더 전문적인 용어로는 Signal rate를 낮추고, Data ..
커널로의 진입이 필요한 시점은 3가지 존재한다. InterruptTrap (software interrupt)System Call 이 중에서 인터럽트가 어떻게 커널 코드로 들어가고 어떤 처리가 일어나는지 알아보자. 인터럽트란? 인터럽트란 비동기적 이벤트가 발생했다는 사실을 주변장치로 알리는 방법을 뜻한다. 여기서 비동기란 이벤트가 언제 일어날 지 알 수 없다는 뜻인데, 이는 우리가 키보드를 언제 두드릴지 모르는 것과 같다고 생각하자. 반대로 동기란 이벤트가 일어날 시간이 정해져 있다는 뜻이다. 인터럽트가 발생하면 가장 먼저 PIC(Programmable Interrupt Controller)에 신호가 도착한다. PIC 칩은 곧장 CPU로 신호를 전달하는 프로세스를 거친다. 이때 Clock 인터럽..
