컴퓨터 구조론 7장 [시스템 버스, I/O 및 인터럽트 / 버스 중재]

• 한 개의 시스템 버스에 접속된 여러 개의 버스 마스터들이 동시에 버스 사용을 요구하는 경우에는 경쟁이 발생하게 된다. 
• 이러한 현상을 버스 경합(bus contention)이라고 한다.
• 이 문제를 적절히 해결하지 못하면 시스템이 정상으로 동작하지 못할 수도 있고, 동작을 하더라도 성능이 떨어지게 된다.
• 버스 경합이 발생한 경우에 버스 마스터들 중에서 한 개씩 선택하여 순서대로 버스를 사용할 수 있게 해주는 동작을 버스 중재(bus arbitration)라 하며, 이러한 기능을 수행하는 하드웨어 모듈을 버스 중재기(bus arbiter)라 한다.
• 버스 중재 방식은 시스템 성능에 많은 영향을 주기 때문에 시스템의 특성에 따라 적절히 설계되어야 한다. 특히 기능상 중요도가 높은 버스 마스터가 버스를 우선적으로 사용할 수 있도록 해주어야 한다. 그러한 만약 모든 버스 마스터들이 동등한 우선순위(priority)를 가진 시스템이라면, 그들이 공정하게 버스를 사용할 수 있도록 해주어야 한다. 

어떤 시스템에서든, 특정 버스 마스터가 매우 오랫동안 버스를 사용하지 못하게 되는 기근(starvation) 현상은 일어나지 않도록 해야 한다.버스 중재 방식은 제어 신호들(버스 요구 신호 및 버스 승인 신호)의 연결 구조에 따라 다음과 같이 두가지로 분류될 수 있다. [WIL92]

• 병렬 중재 방식(parallel arbitration scheme)
• 직렬 중재 방식(serial arbitration scheme)

병렬 중재 방식

• 병렬 중재 방식에서는 각 버스 마스터가 독립적인 버스 요구 신호 선을 가지고 있으며, 이들이 모두 중재 회로로 입력된다. 또한 버스 승인 신호도 각 버스 마스터에 대하여 별도로 발생된다. 따라서 버스 마스터들의 수와 같은 수의 버스 요구 선 및 승인 신호 선들이 각가 필요하며, 이들이 모두 버스 중재기로 연결된다.

직렬 중재 방식

버스요구 신호와 버스승인 신호가 하나씩 있으며, 각 신호 선이 모든 버스 마스터들 간에 직렬로 접속되는 방식

접속되는 순서는 마스터들의 우선순위에 따라 결정된다.

버스 중재 방식은 버스 중재기의 위치에 따라 다음과 같이 분류될 수도 있다.

• 중앙집중식 중재 방식(centralized arbitration scheme)
• 분산식 중재 방식(decentralized arbitration scheme)

중앙 집중식 중재 방식

• 한 개의 버스 중재기가 모든 버스 중재 기능을 수행하는 방식
• 즉, 버스 마스터들이 발생하는 버스 요구 신호들은 하나의 중재기로 보내지고, 중재기는 정해진 중재 원칙에 따라 하나의 버스 마스터만 승인하여 승인 신호를 보내게 된다.

분산식 중재 방식

• 버스 중재 동작이 각 버스 마스터가 별도로 가지고 있는 버스 중재기들에 의해 이루어지는 방식
• 즉, 여러 개의 버스 중재기들이 존재하는데, 일반적으로 각 버스 마스터가 중재기를 한 개씩 가지며, 버스 동작들은 각 마스터의 중재기에 의해 이루어진다.

병렬 중재 방식

중앙집중식 고정-우선순위 방식

• 우선순위에 의한 버스 중재 방식에는 각 버스 마스터에 지정된 우선 순위가 변하지 않는 고정-우선순위 방식(fixed-priority scheme)과 우선순위가 계속 변하는 가변-우선순위 방식(dynamic-priority scheme)이 있다.

중앙집중식 고정 우선순위 중재 방식의 구성도

• 위 그림은 버스 마스터가 네 개인 경우에 중앙집중식 고정-우선순위 중재 방식(centralized fixed-priority arbitration scheme)의 회로 구성도를 보여준다.
• 이 구성에서 중재기에 가까이 위치한 순서대로 우선순위가 정해졌다고 가정하면, 버스 마스터 1이 가장 높은 우선순위를 가지며, 버스 마스터 4가 가장 낮은 우선순위를 가지게 된다.
• 이 방식에서 각 버스 마스터가 자신의 버스 요구(BREQ) 선을 가지고 있으며, 이들은 모두 하나의 버스 중재기로 접속된다. 
• 버스 중재기는 한 개 또는 그 이상의 버스 요구 신호를 받아서ㅡ, 그 중에서 우선순위가 가장 높은 마스터의 버스 승인(BGNT) 신호만 세트한다.
• BBUSY 신호는 어떤 버스 마스터가 버스를 사용하고 있는 중이라는 것을 가리킨다. 따라서 버스 승인을 받은 마스터는 그 신호가 세트되어 있는 동안에는 기다렸다가, 해제되는 순간부터 버스 사용을 시작하게 된다.
• 그 마스터는 버스 사용을 시작하는 순간에 BBUSY. 신호를 세트함으로써, 다른 마스터가 버스를 사용하지 못하도록 막아야 한다.

버스 중재 신호의 시간 흐름도

시간 흐름도는 버스가 사용되고 있는 중의 어느 한 순간에 대한 제어 신호들의 관계를 보여주고 있다.

ex) 버스마스터1이 현재 버스를 사용하고 있는 중일 때 버스 마스터 3이 버스 사용을 요구한 경우의 중재 과정

1. 마스터 3이 BREQ3 신호를 세트한다.
2. 버스 중재기가 마스터 3에게 BGNT3 신호를
3. 마스터 1이 버스 사용을 끝내고 BBUSY 신호를 해제한다.
4. 마스터 3이 BBUSY 신호를 다시 세트하고 버스 사용을 시작한다. 이때 BREQ3와 BGNT3는 제거된다.

이 예에서 만약 버스마스터 3이 버스 요구를 보내기 전에 우선순위가 더 낮은 버스 마스터 4가 버스를 사용하고 있었더라도, 마스터 4에 의한 버스의 사용은 도웆에 중단되지 않고 계속된다. 또한 이 예에서 버스 마스터 2와 3이 동시에 버스 요구를 보냈다면, 우선순위가 더 높은 버스 마스터 2가 선택되어 BGNT2가 세트된다.

1과 2사이의 시간 간격은 버스 중재기의 내부 회로에서 지연 시간을 나타낸다.

각 마스터에 대한 BGNT 신호는 더 높은 우선순위를 가진 마스터가 버스 요구를 발생하지 않은 상태에서 BREQ를 1로 세트했을 때만 활성화 할 수 있다.

부울 중재기의 내부 회로도

분산식 고정-우선순위 방식

• 이 방식에서는 모든 버스 마스터들이 중재기를 한 개씩 가지고 있다.
• 각 버스 마스터의 중재기는 자신보다 더 높은 우선순위를 가진 버스 마스터들의 버스 요구 신호들을 입력으로 받아서 검사하고, 그들 중의 어느 것도 버스 사용 요구를 하지 않은 경우에만 자신의 버스 승인 신호를 세트한다.

분산식 고정 우선순위 중재 방식의 구성도

네 개의 버스 마스터들이 있는 시스템에서 이 방식을 위한 구성도와 버스 중재기들의 내부 회로를 보여주는데, 이 구성에서는 버스 마스터 1이 가장 높은 우선순위를 가지며, 마스터 4가 가장 낮은 우선순위를 가진다.

중재기 내부 회로에서 보는 바와 같이 각 마스터의 버스 요구 신호는 그보다 우선순위가 더 낮은 다른 마스터들의 중재기로만 입력된다.

따라서 더 높은 우선순위를 가진 마스터가 버스 요구를 할 경우에는 하위 마스터들은 버스 사용 승인을 받을 수가 없게 된다. 

ex) 마스터 1의 중재기는 자신의 버스 요구 신호만 입력으로 받기 때문에 자신이 원할 때는 언제나 버스 사용 승인을 받을 수 있다.

그러나 마스터 4의 중재기는 다른 모든 버스 요구 신호들을 입력으로 받기 때문에, 다른 마스터들이 버스 요구를 발생하지 않은 경우에만 버스 사용 승인을 받을 수 있다.

승인을 받은 버스 마스터는 BBUSY 신호를 검사하여서, 비활성화 상태(다른 마스터가 버스를 사용하지 않는 상태)이면 즉시 버스 사용을 시작한다.

분산식 중재 방식은 중앙 집중식에 비하여 중재 회로가 간단하기 때문에 동작 속도가 더 빠르다는 장점이 있다. 그러나 고장을 일으킨 중재기를 찾아내는 방법이 복잡하다는 점과, 한 중재기의 고장이 전체 시스템의 동작에 영향을 줄 수도 있다는 단점을 가지고 있다.

ex) 고장난 중재기가 버스 승인 신호를 잘못 발생시키는 경우에는 두 개의 마스터들이 동시에 버스를 사용하게 될 수도 있다.

가변 우선순위 방식(dynamic-priority scheme)

• 버스 사용 우선순위를 계속 변경시키는 중재 방식으로서, 버스 사용 기회의 불균등이나 기근 현상을 방지해주지만 회로 구현이 더 어렵다.
• 이 방식은 우선순위가 고정되어 있는 방식에서 최상위 우선순위를 가진 마스터가 버스를 독점하거나, 최하위 우선순위를 가진 마스터가 오랫동안 버스를 사용하지 못하는 기근 현상이 발생하는 것을 방지하기 위한 것이다.

사용되는 알고리즘

• 회전 우선순위(Rotating priority)
• 임의 우선순위(Random priority)
• 동등 우선순위(Equal priority)
• 최소-최근 사용(Least-recently used)

회전 우선 방식에는 두 가지 구현 방법이 있다.

• 중재 동작이 끝날 때마다 모든 마스터들의 우선순위가 한 단계씩 낮아지고 가장 우선순위가 낮았던 마스터가 최상위 우선순위를 가지도록 하는 방법
• 일단 버스 사용 승인을 받은 마스터는 최하위 우선순위를 가지며 바로 다음에 위치한 마스터가 최상위 우선순위를 가지도록 하는 방법

특히 두번째 방법을 acceptance-dependent식 회전 우선 순위 방식이라 한다.

회전 우선순위 방식

여기서는 어떤 마스터가 버스 중재깅에 의하여 버스 승인을 받게 되며, 포인터(pointer)는 그 마스터의 번호를 가리키게 되며, 그 다음 번호를 가진 마스터에게 다음 중재 사이클에서 최상위 우선순위가 주어진다. 

ex) a에서 마스터 3이 버스 승인을 받은 후에는 마스터 4의 우선순위가 가장 높아지고, 마스터 5가 그 다음이 되며, ..., 마스터 3은 최하위 우선순위를 가지게 된다는 것응ㄹ 보여준다.

b에서는 마스터 6이 버스 승인을 받은 후에 우선순위가 같은 방법으로 바뀐 모습을 보여준다.

임의 우선순위 방식

• 임의 우선순위 방식에서는 각 중재 동작이 끝날 때마다 마스터들의 우선순위가 임의로 정해진다. 이때 각 버스 마스터의 우선순위를 나타내는 순서는 난수 발생기(random number generator)에 의하여 생성된다.

동등 우선순위 방식

• 비동기식 버스시스템에서만 사용될 수 있는 방식으로서, 모든 마스터들이 동등한 우선순위를 가진다. 
• 이 방식에서 만약 두 개 혹은 그 이상의 마스터들이 동시에 버스 요구를 보낸다면 중재기는 정해진 기준에 의하여 그 충돌을 해결하는데, 일반적으로 조금이라도 먼저 도착한 요구를 먼저 승인해주는 FIFO(First-In First-Out) 알고리즘이 사용된다.

최소-최근 사용 방식(Least-Recently Used)

• 최근 가장 오랫동안 버스를 사용하지 않은 버스 마스터에게 최상위 우선순위를 할당하는 방식이다. 이 방식은 하드웨어로 구현할 때 회로가 복잡해지는 단점이 있다.
• 직렬 중재 방식

BGNT 신호가 데이지 체인으로 연결된 중앙집중식 직렬 중재 방식

중앙 집중식 직렬 중재 방식

• 직렬 중재 방식의 주요 특징은 하나의 중재 신호선에 의해 모든 버스 마스터들이 직렬로 연결되어 데이지 체인(daisy chain) 형태를 이룬다는 것이다.
• 마스터들의 우선순위는 버스 중재기를 시작점으로 하여 승인 신호 선이 연결된 순서대로 정해진다. 결과적으로 버스 중재기에 가장 가까이 위치한 마스터가 가장 높은 우선순위를 가지며, 멀어질수록 우선 순위는 더 낮아진다.
• 버스마스터들로부터 발생되는 모든 버스 요구들은 하나의 공통 신호 선을 통하여 버스 중재기로 들어온다. 또한 하나의 공통 신호 선을 사용하여 구현되는 BBUSY 신호는 어떤 마스터가 버스를 사용하고 있을 때는 세트되고, 그렇지 않을 경우에는 리셋된다.
• 이 방식도 한 개의 버스 중재기가 모든 중재 기능을 통제하므로 중앙집중식으로 분류된다.
• 버스 중재기의 내부 회로는 여러 가지 기능들이 추가된 중재 회로로 구성되지만, 여기서는 BREQ 신호 선을 직접 BGNT 신호 선으로 연결한 간단한 구조이다.

한 개 또는 그 이상의 버스 마스터가 버스 사용을 요구하면(BREQ 신호를 활성화 하면), 버스 중재기는 데이지 체인의 첫 번째에 접속된 마스터로 승인 신호(BGNT)를 보낸다. 버스 중재기에 가장 가까이 위치한 첫 번째 마스터는 가장 먼저 버스 승인 신호를 받기 때문에, 버스 사용에 있어서 최상위 우선순위를 가지게 된다. 만약 그 마스터가 버스 요구를 발생하지 않은 상태에서 승인 신호를 받았다면, 승인 신호를 가 다음에 연결된 마스터로 넘겨준다.

이와 같이 승인 신호는 버스를 요구한 마스터에게 도달할 때까지 계속 통과하게 되며, 버스 요구를 보낸 마스터들 중에서 중재기에 가장 가까이 위치한(우선순위가 가장 높은) 마스터에게 승인 신호가 전달되면, 그 마스터가 버스 사용권을 가지게 된다.

 

이 방식에서도 이미 버스를 사용하고 있는 마스터가 버스 사용을 끝낼 때까지는 새로이 버스 승인 신호를 받은 마스터가 버스 사용을 시작하지 않도록 해야 한다.

이를 보장하기 위해서는 어떤 마스터도 버스를 사용하지 않을 때만 버스 중재기가 승인 신호를 발생하도록 설계되어야 한다.

버스 중재기에 그러한 기능이 없다면, 각 마스터의 버스 인터페이스 회로가 다음과 같은 두 가지 중의 한 기능을 가져야 한다.

• BBUSY 신호가 해제될 때까지는 버스 마스터들이 요구 신호를 보내지 않도록 한다.
• 버스 요구 신호는 항상 발생시킬 수 있지만, 승인 신호를 받은 후에도 BBUSY 신호가 해제될 때까지는 버스를 사용할 수 없도록 한다.

위의 첫 번째 경우에는 버스 마스터가 승인 신호를 받는 즉시 버스 사용을 시작할 수 있다. 그러나 두 번째 경우에는 승인 신호를 받은 후에도 먼저 버스를 사용하고 있던 다른 마스터가 사용을 완료할 때까지는 기다려야 한다.

분산식 직렬 중재 방식

• 각 버스 마스터가 자신의 중재기를 가진 분산식 직렬 중재 방식은 데이지-체인 버스 승인 신호(daisy-chained bus grant signal : DBGNT) 선이 버스 중재기들을 순환형으로 접속한 형태로 구성된다.

분산식 직렬 중재 방식의 구성도

• 이 방식에서는 버스 사용권을 부여받은 마스터가 버스 사용을 시작하는 순간에 (그 마스터의 중재기가) DBGNT 신호를 세트하여 자신의 바로 우측에 연결된 마스터의 중재기로 보내준다. 만약 그 신호를 받은 중재기의 마스터가 버스 사용을 신청하고 기다리던 중이었다면, 그 중재기는 즉시 자신의 BGNT 신호를 발생시켜 마스터로 보낸다.
• DBGNT 신호를 받은 중재기의 마스터가 버스 요구를 하지 않은 상태라면, 그 신호를 우측에 접속된 다음 중재기로 넘겨주는데, 그러한 과정은 버스를 요구한 마스터에 도달할 때까지 계속된다.

이 방식의 특징

• 각 마스터의 우선 순위가 계속 변한다.
• 어떤 마스터가 버스 사용 승인을 받으면 그 마스터는 다음 중재 동작에서는 최하위 우선 순위를 가지게 되고, 그 마스터의 바로 우측에 위치한 마스터가 최상위 우선순위를 가지게 된다.
• 그 다음부터는 순환형 구조에서 DBGNT 신호가 연결된 순서대로(시계 방향으로) 우선순위가 하나씩 낮아진다. 따라서 여러 개의 마스터들이 동시에 버스 사용을 신청한 경우에는 현재 버스를 사용하고 있는 마스터로부터 우측으로 가장 가까이 위치한 마스터가 버스 승인 신호를 받게 되고, 다른 마스터들은 기다려야 한다.

유의사항

• 버스 승인 신호를 받은 마스터는 먼저 버스를 사용하고 있던 마스터가 버스 사용을 끝내고 BBUSY 신호를 리셋 시킬 때까지 기다렸다가 버스를 사용해아 한다는 것이다.
• 이 방식은 분산식이지만, 어느 한 지점에만 결함이 발생해도 전체 시스템이 영향을 받는다. 
• 그 이유는 어떤 중재기에 결함이 발생하면 DBGNT 신호가 통과하지 못하여 전체 동작이 중단되기 때문이다.

폴링 방식

• 폴링 방식(주기적 검사 방식 이라고도 함)에서는 버스 중재기가 각 마스터들이 버스 사용을 원하는지를 주기적으로 검사하여 버스 승인 여부를 결정한다. 
• 이 방식에는 폴링 순서와 중재 동작이 모두 중재기의 내부에 하드웨어로 구현되어 있는 하드웨어 폴링 방식과 프로그램을 이용한 소프트웨어 폴링 방식이 있다.

하드웨어 폴링 방식(hardware polling scneme)

• 중재기 내의 고정된 하드웨어를 이용한 주기적 검사를 통해 중재 기능을 수행하는 방식
• 이 방식에서는 버스 중재기와 버스 마스터 사이에 폴링 동작을 위한 별도의 폴링 선이 존재한다. 따라서 N개의 마스터를 가진 시스템에는 N개의 폴링 선들이 필요하다.
• 각 선은 중재기가 버스 마스터의 버스 요구 여부를 검사하고자 할 때만 사용하기 때문에 한 번에 한 개씩만 세트된다.
• 그러나 2진 코드화된 폴링 주소를 사용하면 폴링 선을 log2N개로 줄일 수 있다.
• 이 경우에는 중재기가 검사할 마스터의 주소 코드를 순서대로 발생시키면서 폴링 동작을 수행하면 된다.
• 폴링 선 외에도 공통의 BREQ 선과 BBUSY 선이 각각 한 개씩 필요하다.
• 이와 같은 신호선들이 포함된 폴링 방식의 구성도는 다음과 같다.

분산식 직렬 중재 방식의 구성도

여기서는 2진 코드화된 폴링 주소가 사용되었으며 동작 순서는 다음과 같다.

1. 중재기는 폴링 주소를 발생하여 검사할 마스터를 지정한 다음에, 그 마스터가 버스 사용을 원하는지 묻는다.
2. 지정된 마스터가 버스 사용을 원하는 경우에는 BREQ 신호를 세트한다.
3. BREQ 신호가 세트되면, 중재기는 현재 검사 중인 마스터에게 버스 사용을 허가한다. 그렇지 않으면 다음 마스터들에 대한 검사를 순서대로 진행한다.

• 이 방식에서 각 마스터들의 우선순위는 중재기가 마스터를 검사하는 순서에 의하여 결정된다. 즉, 중재기가 가장 먼저 검사하는 마스터가 최상위 우선순위를 가지며, 그 다음부터 순서대로 더 낮은 우선 순위를 가지게 된다. 이 순서는 마스터의 번호에 따라 정해질 수도 있고, 가변 우선순위 알고리즘이 적용될 수도 있다.
• 검사할 마스터의 번호를 지정하는 매커니즘은 2진 카운터를 이용하여 쉽게 구현할 수 있다. 즉, 2진 카운터의 출력을 폴링 주소로 사용하여 차례대로 마스터를 지정하면서 검사하는 것이다.
• 일반 어떤 마스터가 버스 사용을 시작하면 BBUSY 신호가 세트되고, 그에 따라 2진 카운터의 동작도 중단된다. 일정 시간 후에 그 마스터가 버스 사용을 완료하고 BBUSY 신호를 해제하면, 중재기는 다시 중재 동작을 시작한다. 이때 2진 카운터가 지난 번 중단된 순간의 다음 값부터 출력하도록 구현하면 회전 우선순위 방식이 되며, 첫 번째 마스터의 번호부터 다시 시작하도록 구현하면 고정 우선순위 방식이 된다.

소프트웨어 폴링 방식

• 중재기 내의 프로세서가 중재 프로그램을 수행하면서 다양한 중재 기능을 수행하는 방식
• 하드웨어 폴링 방식과 동일하게 구성되지만, 버스 중재기에 프로그램을 실행할 수 있는 간단한 프로세서가 포함되어 있어서 '지능'을 가지고 있다는 점이 다르다.
• 즉, 중재 동작이 중재기의 고정된 하드웨어에 의하여 일률적으로 이루어지는 것이 아니라, 프로세서에 의해 조정되는 방식이다.  따라서 소프트웨어 폴링 방식은 하드웨어 방식에 비하여 속도가 더 느리지만, 융통성이 높다는 장점이 있다.
• 중재 프로세서는 다음에 폴링할 마스터의 주소를 기억할 수 있고, 필요에 따라 폴링 순서를 변경할 수도 있다. 또한 어떤 머스 마스터에 결함이 발생한다면, 그 마스터를 폴링 순서에서 제외시킴으로써 시스템 결함 허용도를 높일 수도 있다. 
• 어느 순간에 더 중요한 작업을 실행하거나 큰 작업부하가 걸리는 마스터의 폴링 우선순위를 일시적으로 높여줄 수도 있다. 그러나 이 방식은 중재에 소요되는 시간이 비교적 길다는 단점이 있다.

---

Reference

컴퓨터 구조론 개정 5판

https://velog.io/@chocaprio/07%EC%9E%A5-%EC%8B%9C%EC%8A%A4%ED%85%9C-%EB%B2%84%EC%8A%A4-IO-%EB%B0%8F-%EC%9D%B8%ED%84%B0%EB%9F%BD%ED%8A%B8

07장 시스템 버스, I/O 및 인터럽트