단일-버스 다중프로세서 시스템(1) - 버스 중재 방식과 캐시 일관성 유지 방법

버스의 조직

버스를 이용한 다중프로세서 시스템

1. 데이터 버스(data bus)
• 시스템 요소들 사이에 데이터가 전송될 때 사용되는 선들의 집합
• 양방향 전송
• 선의 수 = 한 번에 전송되는 데이터 비트의 수
2. 주소 버스 (address bus)
• 프로세서가 기억장치와 읽기/쓰기 동작을 할 때, 해당 기억장치를 지정하기 위한 주소를 전송하는 선들의 집합
• 단방향 전송 (프로세서 -> 기억장치)
• 선의 수 = 주소 지정할 수 있는 기억장치의 최대 용량
3. 제어 버스 (control bus)
• 기억 장치, 입출력 장치, 버스 등을 제어하기 위한 선들의 집합

제어 버스의 주요 기능

• 기억장치 및 입출력 장치와의 데이터 교환
  • 기억장치 쓰기 (memory write), 기억장치 읽기(memory read)
  • 입출력 쓰기 (I/O write), 입출력 읽기(I/O read)
  • 전송 확인 (transfer acknowledge)
• 버스 중재 (bus arbitration)
• 버스 요구(bus request), 버스 승인(bus grant), 버스 사용 중(bus busy)
• 인터럽트 동작 지원
• 인터럽트 요구(interrupt request)
• 인터럽트 인식 (interrupt acknowledge)
• 그외 : 버스 클럭 (bus clock), 리셋(reset) 신호 전송

버스의 속도 (대역폭)

• Bus speed = Bus bandwidth
• 버스의 클럭의 주기와 데이터 버스의 폭에 의하여 결정

 

---

버스의 기본 동작

• 쓰기 동작 (write operation)
  1. 버스 마스터가 버스 사용권을 획득한 후,
  2. 버스를 통하여 주소와 데이터를 전송
• 읽기 동작 (read operation)
  1. 버스 마스터가 버스 사용권을 획득한 후,
  2. 버스를 통하여 주소와 제어 신호를 전송하고 데이터가 전송되어 올 때까지 대기
• 동기식 버스 (synchronous bus) : 버스 동작들이 버스 클럭에 기준을 두고 발생 -> 중대형 시스템에서 사용
• 비동기식 버스 (asynchronous bus) : 버스 클럭 없이, 관련된 버스 동작들의 발생 여부에 따라 동작 -> 소형 시스템에서 사용

기억장치 읽기 동작의 시간 흐름도

 

---

버스 중재

• 버스 경합 (bus contention) : 한 개의 버스를 공유하는 다중 프로세서 시스템에서 여러 개의 버스 마스터들이 동시에 버스 사용을 요구하는 경우에 발생
• 버스 중재 (bus arbitration) : 버스 경합이 발생한 경우에 어떤 기준에 따라 버스 마스터들 중에서 한 개 씩만 선택하여 순서대로 버스를 사용할 수 있게 해주는 동작
• 버스 중재기 (bus arbiter) : 버스 중재를 수행하는 하드웨어 모듈
• 기근 (starvation) : 특정 버스 마스터가 오랫동안 버스를 사용하지 못하는 현상

제어 신호들의 연걸 구조에 따른 버스 중재 방식

1. 병렬 중재 방식 (parallel arbitration scheme)

• 버스 마스터와 같은 수의 버스 요구선 및 승인 신호선들이 필요
• 각 버스 마스터가 독립적인 버스 요구 신호선을 가지며, 중재 회로로 입력
• 버스 승인 신호가 각 버스 마스터에 대하여 별도로 발생

2. 직렬 중재 방식 (serial arbitration scheme)

• 버스 요구선 및 승인 신호선이 각각 한 개씩만 필요
• 각 신호선이 버스 마스터들 간에 직렬로 접속
• 접속되는 순서는 마스터들의 우선순위 (priority)에 따라 결정
• 데이지 체인 방식 (daisy chain scheme)

버스 중재기의 위치에 따른 버스 중재 방식

1. 중앙 집중식 중재 방식 (centralized arbitration scheme)

시스템 내에 한 개의 버스 중재기만 존재

2. 분산 중재 방식 (decentralized arbitration scheme)

시스템 내에 여러 개의 버스 중재기가 존재

장점

• 중재 회로가 간단 -> 동작 속도가 빠름
• 어떤 중재기가 고장이 나더라도 해당 마스터에만 영향 -> 신뢰도가 높음

단점

• 고장을 일으킨 중재기를 찾아내는 방법이 복잡
• 한 중재기의 고장이 전체 시스템의 동작에 영향을 줄 수도 있음

조합된 실제 버스 중재 방식 - 아래와 이어짐

1. 병렬 중재 방식 (parallel arbitration scheme)

• 중앙 집중식 고정 우선순위 방식 (centralized fixed priority scheme)
• 분산식 고정 우선순위 방식 (decentralized fixed priority scheme)
• 가변 우선순위 방식 (dynamic priority scheme)

2. 직렬 중재 방식 (serial arbitration scheme)

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

3. 폴링 방식 (polling scheme)

• 하드웨어 폴링 방식
• 소프트웨어 폴링 방식

 

---

병렬 중재 방식

1. 중앙 집중식 고정 우선순위 방식

중재기에 가까이 위치한 순서대로 우선순위가 정해진 방식

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

마스터 1이 버스 사용 중일 때, 마스터 3이 버스 사용을 요구한 경우

1. 마스터 3이 버스 요구 신호(BREQ3 - bus request 3)를 보내면
2. 버스 중재기가 마스터 3에게 버스 승인 신호(BGNT3 - bus grant 3)를 보낸다.
3. 마스터 1이 버스 사용을 끝내고 버스 사용중 신호(BBUSY)를 비활성화하면,
4. 마스터 3이 BBUSY 신호를 다시 활성화하고 버스 사용을 시작.

버스 중재에 대한 부울식과 중재기의 내부 회로

 

2. 분산식 고정 우선순위 방식

모든 버스 마스터들이 별도의 중재기를 가지는 방식

분산식 고정 우선순위 방식

3. 가변 우선순위 방식

회전 우선순위 (Rotating priority)

• 매 중재 동작이 끝난 후에는 모든 마스터들의 우선순위가 한 단계씩 낮아지고 가장 우선순위가 낮았던 마스터가 최상위 우선순위를 가지도록 하는 방법
• 일단 버스 사용 승인을 받은 마스터는 최하위 우선순위를 가지며 바로 다음에 위치한 마스터가 최상위 우선순위를 가지도록 하는 방법. (acceptance - dependent 식 회전 우선순위 방식)

Acceptance-dependent 식 회전 우선순위 방식

임의 우선순위 (Random priority)

동등 우선순위 (Equal Priority)

비동기식 버스 시스템에서만 사용하며, 경합이 발생할 경우 보통 FIFO 사용

최소 최근 사용 (Least recently used)

 

---

직렬 중재 방식

1. 중앙 집중식 직렬 중재 방식

데이지 체인 방식 (daisy-chain) 

데이지 체인 (daisy chain) 방식

BGNT 신호가 데이지 체인된 중앙집중식 직렬 중재 방식. 버스 중재기에 가까운 마스터가 높은 우선순위를 가짐.

2. 분산식 직렬 중재 방식

• 데이지 체인된 버스 승인 신호가 버스 중재기들을 순환형으로 접속
• 가변 우선순위 : 이전 버스 승인을 받은 마스터의 우측이 최상위
• 분산식이지만 단일 결함 (single failure)이 전체 시스템에 영향

분산식 직렬 중재 방식

 

---

폴링 방식

버스 중재기가 각 마스터들이 버스 사용을 원하는 지를 주기적으로 검사하여 버스 승인 여부를 결정

1. 하드웨어 폴링 방식

• 버스 중재기 내의 고정된 하드웨어에 의하여 모든 폴링 동작과 중재 기능이 수행되는 메커니즘
• 버스 중재기와 각 버스 마스터 간에 폴링 동작을 위한 폴링 선이 존재함
• 이진 코드화된 폴링 주소를 사용함. -> 2^n개의 마스터를 가진 시스템에서는 n개의 폴링 선들이 필요
• 중재기가 마스터를 검사하는 순서에 의하여 우선순위 결정

하드웨어 폴링 방식의 구성도

2. 소프트웨어 폴링 방식

• 구성은 하드웨어 폴링 방식과 동일
• 버스 중재기에 프로그램을 실행할 수 있는 프로세서가 포함 -> 지능 부여
  - 폴링 할 마스터의 주소를 기억 가능
  - 폴링 순서 변경 가능
• 속도는 느리지만 융통성(flexibility)이 높음. 결함 마스터를 폴링 순서에서 제외시킴으로써 시스템 결함 허용도를 높임
• 중재에 소요되는 시간이 길기 때문에 분산 시스템의 공유 버스 또는 메시지 전송 시스템(message-passing system)의 중재 방식으로 적절함.

 

---

캐시 일관성 유지 방법

캐쉬 일관성 유지 (cache consistency)

다중 프로세서 시스템에서 공유 데이터가 여러 프로세서들의 캐시에 복사본으로 존재하는 상황에서 캐쉬들과 주기억장치에 저장된 데이터들 간에 일관성을 유지하도록 해주는 기술.

데이터 불일치 (data inconsistency)의 주요 원인들

• 변경 가능한 데이터의 공유 (sharing of writable data)
• 입출력 동작 (I/O activity)
• 프로세스 이주 (process migration)

프로세스 이주 (process migration) : 대칭적 다중 프로세서 시스템에서 프로세스를 처리하던 프로세서가 변경되는 현상.

 

1. 공유 캐시를 사용하지 않는 방법

공유 캐쉬 (shared cache)

• 모든 프로세서들이 하나의 캐시를 공유하도록 하는 방법
• 동시 액세스가 가능하도록 여러 개의 모듈들로 구성
• 프로세서들과 공유 캐시 모듈들은 버스 또는 상호연결망에 의해 연결

장점	항상 캐쉬 일관성이 유지됨
단점	프로세서들 간의 캐쉬 액세스 충돌이 빈번 -> 성능 저하 캐쉬가 프로세서에 근접하게 위치해야 하는 원칙에 위배 모든 I/O 명령들의 공유 캐쉬 경유 필요

[예] Alliant 사의 FX 시스템 : 2~4개의 프로세서들이 하나의 캐쉬 공유

 

2. 공유 변수는 캐시에 저장하지 않는 방법

변경 가능한 공유 데이터는 주 기억장치에만 저장함.

캐쉬 저장 불가능 데이터 (non-cacheable data)

• Lock 변수, 프로세스 큐(process queue)와 같은 공유 데이터 구조
• 임계 영역에 의해 보호되는 데이터들

단점

• 사용자와 컴파일러에게 투명하지 않다. (non-transparent)
  -> 컴파일러가 각 데이터에 tag를 붙여야 하며, run-time 동안 그것을 검색할 수 있는 H/W 필요
• Non-cacheable data와 같은 블록에 포함된 일반 데이터의 캐쉬 저장도 불가능 -> 캐쉬 적중률 저하
• 모든 I/O 데이터들도 캐쉬 저장 불가능 -> 캐쉬 적중률 저하

 

3. 잠금 변수들은 캐쉬에 저장하지 않는 방법

임계 영역을 보호하는 lock 변수들만 'non-cacheable'로 지정

캐쉬 플러쉬(cache flush) 필요

• 임계 영역에서 변경한 공유 데이터를 주기억장치에 갱신했을 때, 다른 캐시들에 있는 모든 복사본들을 무효화시키는 동작
• write-back 경우에는 H/W가 복잡

단점

• 전채 캐시에 플러쉬 필요
• 임계 영역 내에서 액세스 된 데이터의 변경 여부를 표시하는 태그 필요
• I/O 동작의 수행 전에 캐시 플러쉬 필요
  -> 적은 용량의 캐쉬 시스템에서 적합

 

그래서. .주로 버스 감시 매커니즘을 사용하는데 내용이 넘 많아서 다음 포스팅에도 덧붙이겠다!