으랏차

RISC의 기본 설계 개념 주에서 가장 중요한 사항은 명령어들이 한 클럭 사이클(clock cycle)에 한 개씩 실행되도록 하는 것이다. 그러나 명령어 실행은 오퍼랜드 인출, 연산, 및 결과의 저장을 모두 포함하기 때문에 사실상 한 클럭 사이클내에 실행한다는 것은 불가능하다. 따라서 이것이 가능하도록 하기 위하여 명령어 실행 과정을 파이프라이닝(pipelining)하고, 특정 명령어들 외에는 실행 과정에서 주기억장치를 액세스하지 않도록 하며, 필요한 데이터를 가능한한 프로세서 내부에서 액세스할수 있도록 레지스터의 수를 증가시키는 것과 같은 특별한 고려가 필요하다. RISC 설계에서 공통적으로 사용되고 있는 이와 같은 몇 가지 기본 원리들을 좀더 자세히 살펴보면 다음과 같다.

1) 복잡한 명령어의 제거

한 사이클 내에 명령어가 실행되도록 하기 위하여 실행 과정을 파이프라이닝 하였을 때, 파이프라인의 어느 한 단계가 특별히 긴 시간이 걸린다면 전체 클럭 사이클의 주기가 길어질 수 밖에 없을 것이다. 이러한 문제를 피하기 위하여 복잡하고 긴 시간이 걸리는 연산을 포함하는 명령어는 제거하였다. 예를 들면, 대부분의 RISC 프로세서들의 명령어 세트에는 곱셈 명령어와 나눈셈 명령어가 없다. 이들은 쉬프트(shift)와 덧셈 또는 뺄셈 명령어들을 반복 사용함으로써 대체될 수 있다. 또한 부동-소수점 연산으 산술 보조프로세서(arthmetic coprocessor)를 이용하여 처리할 수 있다.

2) 주기억장치 액세스 명령어의 제한

명령어 실행의 속도를 높이기 위하여 파이프라인 구조가 사용되었더라도 연산을 위한 데이터가 필요한 시점에서 사용 가능하지 않다면, 파이프라인의 효율이 급격히 떨어질 것이다. 그러나 기억장치를 액세스하는 동작은 다른 동작들에 비하여 시간이 오래 걸리기 때문에, 명령어 실행 도중에 데이터를 기억장치로부터 액세스하게 되면 파이프라인 동작의 흐름이 깨어질 것이다. 이러한 문제를 방지하기 위하여 RISC 프로세서에서는 데이터에 대한 연산을 수행하는 명령어의 실행에 필요한 데이터는 항상 (외부 기억장치가 아닌) 내부 레지스터에 저장되어 있도록 하고 있다. 즉, 이러한 명령어들에게는 기억 장치 액세스를 허용하지 않는 것이다.

그렇게 되는 경우에는 데이터에 대한 연산을 수행하는 명령어들은 레지스터 주소지정 방식(register addressing mode)만을 가지면 되며, CISC 프로세서의 명령어에서와 같은 여러 가지 복잡한 주소지정 방식들은 사용할 필요가 없어진다. 이에 따른 이점들은 다음과 같다.

 명령어 코드가 기억장치 주소 비트들은 포함하지 않고 레지스터 번호를 나타내는 적은 수의 비트들만 가지면 되므로, 명려어 코드의 비트 수가 줄어든다. 예를 들어, 레지스터의 수가 32개라면 주소필드는 5비트이면 된다.

 유효 주소(effective address)를 계산하는 데 걸리는 시간이 절약된다.

연산에 필요한 데이터가 항상 레지스터 내에 있도록 하기 위해서는 데이터가 사용되기 이전에 미리 다른 명령어에 의하여 기억장치로부터 인출되어 있어야 한다. 또한 연산이 완료된 후에 결과값도 일단 레지스터에 저장되며, 기억장치에 저장되어야 하는 시점에서 다른 명령어에 의하여 저장된다. RISC 프로세서에서는 이와 같은 기억장치 액세스 동작은 LOAD와 STORE 명령어에 의해서만 이루어지도록 하고 있다. 또한 이 명령어들은 사용되는 주소지정 방식도 간단한 것들만 사용된다.

일반적인 RISC 프로세서에서 정의된 LOAD 및 STORE 명령어의 종류를 보면 표 6과 같다. 여기서 LOAD 명령어가 부호화 여부(signed 또는 unsigned)에 따라 두 가지로 구분되어 있는 이유는 다음과 같다: 기억장치로부터 읽어오는 데이터가 프로세서의 한 단어(word) 길이인 32비트보다 짧은 byte 또는 halfword라면, 32비트 레지스터로 적재될 때 부호(+,-)를 가진 수의 경우에는 상위 비트들이 모두 부호 비트(sign bit)와 같은 값을 가지도록 한다. 즉, 부호 비트가 확장된다. 부호가 없는 수(unsigned byte 또는 halfword)의 경우에는 부호 비트의 확장이 필요하지 않다. STORE 명령어의 경우에는 명령어 실행 과정에서 부호 비트 확장 동작이 필요하지 않으므로, 명령어도 구분될 필요가 없다.

이와 같이 기억장치 액세스는 LOAD 및 STORE 명령어만에 의하여 이루어지기 때문에, 다른 명령어들은 기억장치 주소를 포함할 필요가 없다. 예를 들어, ADD, MOVE, AND와 같은 명령어들에는 레지스터 번호를 나타내는 적은 수의 비트들만 포함되어 있다.

3) 주소지정 방식의 단순화

명령어의 종류가 많아지면 연산 코드를 해독하는 회로가 복잡해지는 것과 마찬가지로, 주소지정 방식(addressign mode)의 종류가 많으면 유효 주소(effective address)를 계산하는 시간이 그만큼 더 걸리게 되고 회로도 복잡해진다. 이를 방지하기 위해서는 주소지정 방식의 종류도 최소화시킬 필요가 있다. 실제로 RISC 프로세서들은 매우 적은 수의 간단한 주소지정 방식들만 사용하고 있는데, 그 설명을 위한 예로서 다음과 같은 RISC I의 명령어 형식을 분석해 보자.

이 형식에서 위의 숫자들은 각 필드의 비트 수를 나타내며, OP code 필드는 명령어의 연산코드이고, C 비트는 이 명령어의 실행 결과에 조건 코드(condition code)를 세트 할 것인지의 여부를 나타낸다. 즉, C=1이면, 연산 결과에 따라 조건 코드를 세트하라는 의미이고, C=0이면 명령어 실행 결과가 조건 코드에 영향을 주지 않는다는 것이다. DEST 필드는 이 연산의 결과가 저장될 목적지 레지스터(destination register)를 지정하고, SRC 필드는 연산에 사용될 데이터의 근원지 레지스터(source register)를 지정한다. 이 필드들은 각각 5비트씩이므로, 32개의 레지스터들이 지정될 수 있다.

I 비트는 OFFSET 필드의 내용을 지정해준다. 즉, I=1이면 OFFSET 필드의 내용이 연산에 사용될 실제 데이터라는 것을 가리키고, I=0이면 OFFSET 필드의 하위 5비트가 연산의 두 번째 오퍼랜드를 가지고 있는 레지스터의 번호라는 것을 의미한다. 이에 따라 주소지정 방식은 다음과 같은 종류로 구분될 수 있다.

 I=1의 경우: 즉치 주소지정방식(immediate addressing mode)

R(DEST) = R(SRC) op OFFSET

 I=0의 경우: 레지스터 주소지정방식(register addressing mode)

R(DEST) = R(SRC) op R(lower 5 bit of OFFSET)

단, R(n)은 n값이 지정하는 번호의 레지스터를 나타내고, op는 OP code에 의하여 지정되는 연산(ADD, SUB, AND 등)을 의미한다. I=1일 때, OFFSET 필드가 13비트이므로 데이터가 2의 보수로 표현되는 경우에 -2¹² 과 (2¹²-1) 사이의 정수값을 가질 수 있다.

여기서 흥미로운 것은 레지스터 0의 내용을 하드웨어적으로 0값에 고정시키는 것이다. 따라서, 연산 오퍼랜드의 근원지가 레지스터 0인 경우에는 읽혀오는 값이 항상 0이 된다. 이것을 이용한 연산의 몇 가지 예를 보면 다음과 같다.

I = 1, SRC = 0, op = ADD : R(DEST)OFFSET

I = 0, SRC = 0, op = AND : R(DEST)0

I = 0, OFFSET = 0, op = ADD : R(DEST)R(SRC)

일반적인 명령어들에세는 위에서 설명한 두 가지 주소지정 방식들만 사용되며, 주기억장치를 액세스하는 LOAD 와 STORE 명령어에서는 이들과는 다른 주소지정 방식들이 사용된다. 먼저 LOAD 와 STORE 명령어에서 유효 주소 effective address : EA)가 계산되는 방법을 보면 다음과 같다.

EA = (R_SRC) + OFFSET

여기서 만약 OFFSET = 0 이라면 EA = (R_SRC)가 되어 레지스터 간접 주소지정(register indirect addressing) 방식이 되며, OFFSET 0 이면 인덱스 주소지정(index addressing)방식이 된다. 또한 만약 R_SRC = R₀ 라면, EA = OFFSET이 되므로 직접 주소지정(direct addressing) 방식이 된다. 그런데 OFFSET 필드는 13비트이므로, 이 방식을 사용하는 명령어는 전체 주소 공간의 최하위 2¹³ = 8192개의 기억 장소들만 주소 지정할 수 있다.

그 외에도 RISC II에서는 조건분기 명령어를 위하여 PC-relative 주소지정 방식이 추가되어 있다. 이 방식에서는 RISC I의  명령어 형식에서 DEST 필드의 비트들이 분기의 조건을 지정하는데 사용되고, SRC 필드를 포함한 하위 19비트들이 부호를 가진 변위(signed offset) 값으로 사용되어 PC 값에 더해져서 분기의  목적지 주소가 된다.

대부분의 RISC 프로세서들은 지금까지 살펴본 몇 가지 주소지정 방식들만 사용하기 때문에 명령어 형식이 고정되고, 명령어의 비트 수가 줄어들며, 유효 주소를 결정하는데 있어서 복잡한 계산이 필요하지 않도록 하고 있다.

4) 파이프 라이닝

RISC 프로세서에서 명령어들이 비록 간략화 되기는 하였으나, 사실상 명령어를 한 클럭 사이클 내에 실행하는 것은 불가능하다. 그러나 n 사이클 이내에 n 개의 명령어 실행을 완료할 수만 있다면, 평균적으로 한 사이클 당 한 개의 명령어를 실행한다고 말할 수 있을 것이다. 이를 위하여 모든 RISC들은 명령어 실행 과정을 파이프라이닝(pipelining)하고 있는데, 일반적으로 다음과 같은 파이프라인 단계(pipeling stages)들로 나누어진다: 명령어 인출 단계, 명령어 해독 단계, 실행 단계 및 기억장치 액세스 단계. 이들 중에서 명령어 인출 단계는 명령어 캐쉬가 적중(hit)된 경우에 한 사이클 내에 완료될 수 있고, 명령어의 해독과 실행도 각각 한 사이클 내에 처리될 수 있다. 그러나 기억장치를 액세스하는 LOAD와 STORE 명령어에 있어서는 실행 단계(execution stage)가 적어도 두 사이클은 소요된다. 그에 따른 문제점을 분석하기 위하여 다음과 같은 어셈블리 프로그램을 고려해보자.

LOAD R0, X ; 기억장치 X번지의 내용을 레지스터 R0로 적재하라.

ADD R1, R0 ; 레지스터 R0와 R1의 내용을 더하고, 결과를 R1에 저장하라.

이 프로그램의 처리 과정에서 두 명령어들이 순서대로 파이프라인을 통과하기 때문에 LOAD 명령어가 실행된 지 한 사이클 후에는 ADD 명령어의 실행이 시작될 것이다. 그러나 LOAD 명령어는 아직 실행이 완료되지 않았으므로 레지스터 R0에는 X의 내용이 적재되지 않았다. 따라서 ADD 명령어는 X번지의 내용이 아닌 원래 R0의 내용을 R1에 더하게 될 것이므로 잘못된 계산 결과를 산출하게 된다. 이를 방지하기 위하여 RISC 프로세서에서느 다음과 같은 두 가지 방법들이 사용된다.

 하드웨어 인터라킹(H/W interlocking): LOAD/STORE 명령어가 실행된 후에 해당 레지스터에 데이터가 적재될 때까지 자동적으로 NO-OP 명령어 코드에 해당하는 지연 슬롯(delay slot)을 삽입하는 방법이다. 프로세서 속도와 기억장치 속도의 차이가 큰 경우에는 여러 개의 지연 슬롯들이 삽입될 수도 있다. 이 방법은 하드웨어로 구현된다.

 프로그램 실행 순서의 재조정: 컴파일러가 어셈블리 프로그램 코드들을 조사하여 LOAD/STORE 명령어의 실행 완료 여부와 무관하게 실행될 수 있는 명령어를 LOAD/STORE 명령어의 다음에 위치시키는 방법이다. 만약 그러한 명령어를 찾지 못했을 때는 NO-OP 명령어 코드를 삽입한다.

이와 같은 파이프란인의 실제 처리 과정을 설명하기 위하여 [그림 1]과 같은 3단계 파이프라인을 고려해보자. [그림 1]에서는 10개의 명령어들이 순서대로 처리되고 있는데, 유의할 부분은 세 번째와 일곱 번째에 각각 위치하고 있는 LOAD와 STORE 명령어의 실행이다. 먼저 첫 번째 사이클에서 명령어 1이 인출된다. 두 번째 사이클에서는 명령어 2가 인출된다. 동시에 명령어 1은 실행된다. 세 번째 사이클에서는 명령어 3(LOAD임을 나타내기 위하여 L로 표시)이 인출되고, 동시에 명령어 2가 실행된다. 네 번째 사이클에서 LOAD 명령어의 실행이 시작되는데, 한 사이클 내에 완료되지 못한다. 따라서 다섯 번째 사이클에서 특별한 상황이 일어난다. 즉, LOAD 명령어 실행은 완료되지 못한 상태에서 명령어 4(<4>로 표시)가 실행된다. 만약 명령어 4가 앞의 LOAD 명령어의 목적지 레지스터를 사용하지만 않는다면 아무런 문제가 발생하지 않으며, 명령어 실행은 지연 없이 진행된다.

그것이 가능해지도록 하기 위하여 위에서 설명한 방법들 중에서 두 번째 방법을 사용한다면, 컴파일러가 LOAD 명령어의 다음 위치에 LOAD 명령어에 의하여 기억장치로부터 인출되는 데이터를 사용하는 명령어가 오지 않도록 순서를 조정해주면 된다. 만약 컴파일러가 그러한 명령어를 찾을 수 없을 때는 LOAD 명령어 다음에 NO-OP 명령어를 삽입해주어서 아무런 동작이 처리되지 않으면서 한 사이클을 기다리게 한다. STORE 명령어의 경우에도 비슷한 일이 발생하는데, 이때도 명령어 8이 STORE 명령어의 실행과 무관하다면 아무런 문제가 없다.

이와 같이 기억장치를 액세스하는 명령어의 다음 위치에 그와 무관한 명령어를 위치시키는 재구성 방법을 사용하면 H/W 인터라킹 방법보다 프로세서의 내부 하드웨어가 더 간단해진다. 그러나 컴퓨터시스템에 따라 프로세서의 속도와 기억장치 속도간의 차이가 더 커져서 기억장치 액세스에 여러 사이클들이 걸리는 경우에는 컴파일러가 그만큼 더 많은 명령어들을 찾아서 삽입해야 하고, 만약 그러한 명령어들을 찾을 수 없다면 그 수만큼의 NO-OP 명령어들을 삽입해야 한다. 이러한 동작은 컴파일러에게 큰 부담이 될 수 있기 때문에 MIPS에서는 이와 같은 명령어 실행 순서의 재조정을 담당하는 별도의 프로그램인 재구성기(reorganizer)를 사용한다. 재구성기는 어셈블리 프로그램을 조사하여 기억장치의 액세스의 지연에 따른 영향을 최소화시키기 위하여 명령어들의 실행 순서를 전체적으로 재조정해주는 역할을 한다.

5) 마이크로프로그램의 제거

독자들은 CISC 프로세서에서 제어 유니트가 명령어 해석과 제어 신호 발생을 위하여 마이크로프로그램을 사용하였다는 것을 기억할 것이다. 그 주요 이유는 제어 유니트 내부 회로의 복잡성을 줄이기 위한 것이었다. 그에 따라 제어 유니트의 내부에는 마이크로로그램을 저장하기 위한 제어 기억장치(control memory)가 필요하게 되었고, 그것으로부터 마이크로 코드(micro-code)를 인출해야 하기 때문에 실행 과정에 많은 시간이 걸리게 되었다. 즉, 명령어 실행 속도가 저하되는 주요 원인이 된 것이다.

RISC 프로세서에서는 모든 명령어 실행 과정이 하드웨어만에 의하여 이루어진다. 다시 표현하면, 명령어를 해석하고 제어 신호를 발생하는 과정에서 마이크로프로그램이 개입되지 않는다는 것이다. 명령어 인출 유니트(instruction fetch unit)에 의해 인출된 명령어 코드의 비트들이 그 명령어 실행에 필요한 제어 신호들을 발생시키는 데 직접 사용된다. 이것은 실제 RISC 프로세서의 고속화에 큰 기여를 하였다. 

▶ Conditions for deadlock 

1. Mutual exclusion condition : Each resource is either currently assigned to exactly one process or is available.
2. Hold and wait condition : Processes currently holding resources granted earlier can request new resources.
3. No preemption condition : Resources previously granted cannot be forcibly taken away from a process.

                                        They must be explicitly released by the process holding them.
4. Circular wait condition : There must be a circular chain of two or more processes,

                                      each of which is waiting for a resource held by the next member of the chain.

▶ Dining Philosophers Problem

Each lawyer needs two chopsticks to eat. Each grabs chopstick on the right first.
What if all grab at the same time? Deadlock.

 

+

철학자들은 원형테이블을 공유하며, 이 테이블은 가가 한 철학자에 속하는 5개의 의자로 둘러 싸여 있다. 테이블 중앙에는 한사발의 밥이 있고, 테이블에는 다섯개의 젓가락이 놓여있다.   - 철학자가 생각할때는 다른 동료들과 상호작용하지 않는다. - 철학자는 배가고프면 자신에 가장 가까이 있는 두개의 젓가락을 집으려고 시도한다.    (이미 옆사람의 손에 들어간 젓가락은 집을 수 없다.) - 식사중에는 젓가락을 놓지않고, 식사를 마치면 젓가락 두개를 모두 놓고 다시 생각을 시작한다.

- 교착상태(deadlock)가 발생하는 4가지 필요조건에 '식사하는 철학자 문제'에 적용해보자.

 

철 학자는 배가고프면 자신에게 가까운 양쪽의 젓가락을 집어야한다. 하지만 옆의 다른 철학자가 이미 젓가락을 집어서 사용하고 있다면 그 젓가락은 이미 쓰고 있는 철학자만이 공유되지 않고 사용할 수 있기 때문에 배고픈 철학자는 옆의 철학자가 식사를 마치고 젓가락을 놓을 때까지 기다려야한다.

이것은 상호배제(mutual exclusion) 조건으로 최소한 하나의 자원이 비공유 모드로 점유되어 어느 자원에 대해 한 프로세스가 이미 사용중이면 다른 프로세스는 기다려야 하는 것을 보여준다.

또한 배고픈 철학자는 자신의 양 옆중 놓여있는 젓가락을 사용하기위해 하나 집고 다른 철학자가 쓰고 있는 다른 하나의 젓가락을  식사가 끝마쳐져서 놓여지기를 기다리는 경우는, 점유와 대기(Hold and wait) 조건으로  하나 이상의 자원을 할당받은 채로 나머지 자원을 할당 받기 위해 다른 프로세스의 자원이 해제되기를 기다리는 프로세스가 존재하는 경우이다.

젓가락은 미리 선점할 수 없는데, 즉 젓가락을 집고 있는 중 강제로 방출할 수 없다. 식사를 마친 철학자가 젓가락을 자발적으로만 놓을 수 있는 것이다. 이것은 자원을 할당받은 프로세스로부터 자원을 강제로 빼앗지 못하는 비선점(Nopreemption) 조건이다.

마지막으로, 철학자1은 철학자2가 가지고 있는 젓가락을 내려놓기를 기다리고 있고, 철학자2는 철학자3을, 철학자3은 철학자4를, 철학자4는 철학자5를,철학자5는 철학자1의 젓가락을 기다린다면 이것은 자원 할당 그래프 상에서 프로세스의 환형 사슬이 존재하는 것으로 순환대기(circular wait) 조건이다.

이 4가지 조건이 동시에 성립된다면 교착상태가 발생할 것이다.

- '식사하는 철학자 문제'에서 기아상태가 발생하는 경우.

 철학자들은 식사를 하기 위해서 반드시 양쪽의 젓가락을 들어야한다.

 위의 그림을 참고해서 보면, 철학자1과 철학자4가 식사를 시작하면, 철학자5는 식사를 하지못하고, 철학자2와 철학자4가 식사를 시작하게 되면 철학자3이 식사를 하지못하는 무한정 대기상태인 기아상태가 발생하게 된다.

▶ 다단계 색인의 가장 대표적인 색인 구조 B- 트리와 B⁺- 트리

		B- 트리	B+- 트리
특  징		o 균형 m-원 탐색 트리  o 차수 m인 B-트리의 특성       - 루트와 리프를 제외한 노드의 서브트리 수 ≥ 2            * [m/2] ≤ 개수 ≤ m       - 모든 리프는 같은 레벨       - 키 값의 수            * 리프 : [m/2] -1 ~ (m-1)         * 리프가 아닌 노드 : 서브트리수 - 1      - 한 노드 내의 키값 : 오름차순  o 노드 구조      - Ki→ (Ki,Ai): 데이타 화일의 주소(Ai)	o 인덱스 세트 (index set)     - 내부 노드     - 리프에 있는 키들에 대한 경로 제공     - 직접처리 지원  o 순차 세트 (sequence set)     - 리프 노드     - 모든 키 값들을 포함     - 순차 세트는 순차적으로 연결          → 순차처리 지원     - 내부 노드와 다른 구조
연 산	탐색	o 직접 탐색 : 키 값에 의존한 분기      - 순차 탐색 : 중위 순회      - 삽입, 삭제 : 트리의 균형 유지      - 분할 높이 증가      - 합병 높이 감소	- B+-트리의 인덱스 셀 = m-원 탐색 트리  - 리프에서 검색
	삽입	리프노드     - 빈 공간이 있는 경우: 순 삽입     - 오버플로           * 두 노드로 분열(split)           * [m/2] 째의 키 값 → 부모노드           * 나머지는 반씩 나눔 (왼쪽, 오른쪽 서브트리)	- B-트리와 유사  - 오버플로우 (분열)      → 부모 노드, 분열노드 모두에 키 값 존재
	삭제	- 리프노드  - 삭제키가 리프가 아닌 노드에 존재      * 후행키 값과 자리교환(후행키-항상 리프에)      * 리프노드에서 삭제  - 언더플로 : 키수 < m/2�-1       * 재분배 (redistribution)         - 최소키 수 이상을 포함한 형제노드에서 이동            (형제노드의 키 → 부모노드 → 언더플로노드)     *합병 (merge)       - 재분배 불가능시 이용          (형제노드 + 부모노드의 키 + 언더플로노드)	리프에서만 삭제 (재분배, 합병 필요 없는 경우)    - 재분배: 인덱스 키 값 변화, 트리구조 유지    - 합병 : 인덱스의 키 값도 삭제

- 데이터가 왼쪽부터 차례대로 입력될 때 구축된 B-트리와 B⁺-트리의 최종적인 형태(차수는 3)

4,       8,        2,        3,       9,      7,       1,       6,       10,        5

B- 트리

B⁺- 트리 

+ 위의 구축한 트리에서 키 값 7이 삭제된 후 모습

 

B-트리

 

 B⁺- 트리

 

▶ Round Robin (RR)

- Each process gets a small unit of CPU time (time quantum), usually 10-100 milliseconds. 

   After this time has elapsed, the process is preempted and added to the end of the ready queue.

- If there are n processes in the ready queue and the time quantum is q,

                                                                  then each process gets 1/n of the CPU time in chunks of at most q time units at once. 

  No process waits more than (n-1)q time units.

- Performance

              q large → FIFO

              q small → q must be large with respect to context switch, otherwise overhead is too high.

 

 

+ 시간 할당량(time quantum) = 시간 조각(time slice)

RR 스케줄링 알고리즘은 시분할 시스템을 위해 특별히 설계되었기 때문에, RR 스케줄링 알고리즘의 성능은 시간 할당량의 크기에 매우 많은 영향을 받는다. 극단적인 경우, 시간 할당량이 매우 크면, RR 정책은 선입선출 정채과 같다. 시간 할당량이 매우 적다면(예를 들어 1마이크로초), 라운드 로빈 방식은 처리기 공유(processor sharing) 라 불리며, 이론적으로는 n 개의 프로세스들 각각이 실제 처리기의 1/n 속도록 실행되는 자신의 처리기를 가지고 있는 것처럼 사용자에게 보인다.

 

- 작은 시간 할당량은 문맥교환을 증가시킴을 보임

 

또한, RR 스케줄링의 성능에 문맥교환(context switching)의 영향을 고려해야 할 필요가 있다. 우리가 10시간 단위를 갖는 하나의 프로세스를 가지고 있다고 가정해보자. 시간 할당량이 12시간 단위라면, 프로세스는 아무런 오버헤드 없이 1시간 할당량 이전에 끝난다. 만일 시간할당량이 6시간 단위라면, 프로세스는 2시간 할당량이 필요하므로, 한번 문맥교환을 해야한다. 시간할당량이 1시간 단위라면, 9번의 문백 교환이 발생할 것이고, 따라서 프로세스의 실행이 느려진다.

그러므로, 우리는 시간 할당량이 문맥교환 시간에 비해 더 클 것을 원한다.

 

- 총처리 시간이 time quantum에 따라 변함을 예시

 

총처리 시간(turnaround time) 또한, 시간 할당량의 크기에 좌우된다. 한 프로세스 집합의 평균 총처리 시간은 시간 할당량의 크기가 증가하더라도 반드시 개선되지 않는다. 문맥 교환 시간이 추가된다면, 더 많은 문맥교환이 요구되기 때문에 더작은 시간 할당량에 대해서는 평균 총처리 시간이 증가된다. 반면에, 시간 할당량이 너무 크다면 RR 스케줄링은 선입 선처리 정책으로 퇴보한다. 

- A process can move between the various queues; aging can be implemented this way.

- Multilevel-feedback-queue scheduler defined by the following parameters:

     ㆍnumber of queues

     ㆍscheduling algorithms for each queue

     ㆍmethod used to determine when to upgrade a process

     ㆍmethod used to determine when to demote a process

     ㆍmethod used to determine which queue a process will enter when that process needs service

 

  + 다단계 피드백 큐 (Multievel Feedback Queue) 스케줄링 수행 시 기대효과 

일반적으로 프로세스들이 스시템 진입 시에 영구적으로 하나의 큐에 할당되며, 큐사이를 프로세스들은 이동하지 않는다. 그러나 다단계 피드백 큐 스케줄링 알고리즘에서는 프로세스가 큐들 사이로 이동한다. 어떤 프로세스가 CPU 시간을 너무 많이 사용하면, 낮은 우선순위의 큐로 이동되고, 입/출력 중심의 프로세스와 대화형 프로세스들을 높은 우선순위의 큐에 넣어주어 효율이 향상되는 효과를 갖게 한다.

 

 

자세히 살펴보면, 준비된 큐를 다수의 분리된 큐로 나누고 각 큐에 우선순위를 연관시킨다. 우선순위가 낮을수록 큐에서 사용하는 time quantum는 증가된다. 각 큐의 프로세스들은 그 큐보다 높은 우선순위의 큐들이 empty인 경우에만 CPU를 할당받을 수 있다. 모든 프로세스들은 처음에는 highest priority queue에 들어간다.

만약 주어진 time quantum가 만기되면 실행되던 프로세스는 그 프로세스가 있었던 우선순위 큐의 바로 하위의 우선순위 큐로 이동된다. 따라서 CPU-bounded process는 점차 낮은 우선순위 큐로 이동된다. lowest priority queue의 프로세스에 대해 time quantum가 만기된 경우였다면 그 프로세스는 다시 lowest priority queue에 들어간다.  

만약 프로세스가 I/O 종료 후 다시 큐로 들어가야 한다면 그 프로세스는 I/O 요청 이전에 있었던 우선순위 큐의 바로 상위의 우선순위 큐에 들어간다. 따라서 I/O-bounded process는 점차 높은 우선순위 큐로 이동된다. highest-priority queue의 프로세스에 대해 I/O 종료가 발생한 경우였다면 그 프로세스는 다시 highest priority queue에 들어간다.

 

+ 다단계 피드백 큐 스케줄링과 기아상태

스케줄링 수행시 실행 준비는 되어 있으나 CPU를 사용하지 못하는 프로세스는 CPU를 기다리면서 봉쇄된 것으로 간주될 수 있다. 예를 들면,부하가 과중한 컴퓨터 시스템에서 높은 우선순위의 프로세스들이 꾸준히 들어와 낮은 우선순위의 프로세스들이 CPU를 얻지 못하게 됨으로써, 낮은 순위의 프로세스들은 무한봉쇄(indefinite blocking) 또는 기아상태(starvation)가 되는 것이다.

낮은 우선순위의 프로세스들을 무한히 봉쇄하는 문제(기아상태)에 대한 해결방안은 노화(aging)이다. 노화란, 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 방법으로, 다단계 피드백 큐 스케줄링 수행시 낮은 우선순위의 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동하여 기아상태를 예방할 수 있다.

 

 높은 우선순위의 프로세스가 현재 낮은 우선순위의 프로세스에 의해 접그되고 있는 커널 자료를 읽거나 변경할 필요가 있을 경우 어떠한 일이 발생할 수 있을까? 이때 높은 우선순위의 프로세스는 낮은 우선순위의 프로세스가 끝나기를 기다려야 한다. 이는 우선순위 역전(inversion) 이라고 알려져 있다. 사실, 높은 우선순위의 프로세스가 필요로 하는 자원들을 접근하고 있는 프로세스들의 체인이 있을 수 있다.

이러한 문제는, 이러한 모든 프로세스들(높은 우선순위 프로세스가 필요로 하는 자원을 접근하는 모든 프로세스들) 이 그 자원을 사용 완료할 때까지 높은 우선순위를 상속하는, 우선순위 상속(priority-inheritance) 프로토콜로 해결할 수 있다. 이들은 종료할 때 우선순위가 원래의 값으로 복귀한다. 

 

- 경성 실시간 시스템(Hard real-time system)

ㆍ정해진 시간 내에 특정 작업이 완료되기를 요구한다. 

ㆍresource reservation : scheduler는 process가 정해진 시간 내에 완료되는 것이 보장될 경우 수행하고, 그렇지 않으면 요청을 거절한다.

ㆍ현대의 computer와 운영체제에는 완전한 기능성은 갖추어 있지 않으며 특정 process를 위해서 사용되는 hardware 상에서 실행되는 특수 목적의 software로 구성된다.

ㆍ단점 : scheduler가 각 type의 운영체제 기능이 수행되기 위해 얼마나 오랜 시간이 소요되는지 정확하게 알아야만 한다. 따라서 각 operation이 최대 시간을 취할 수 있도록 보장해야 한다. 그러나 이러한 보장은 secondary storage나 virtual memory를 가진 system에서는 불가능하다.

- 연성 실시간 시스템(Soft real-time system)

ㆍhard real-time system 보다는 덜 제한적이다. 중요한 process들이 상대적으로 덜 중요한 process들 보다 높은 priority를 가질 것을 요구한다.

ㆍ단점 :  time-sharing system에 soft real-time 기능을 첨가하는 것은 자원의 불공정한 할당을 야기할 수도 있으며 더 긴 지연이나 심지어는 starvation을 초래할 수도 있다. 

 

선점(preemptive)스케쥴링과 비선점(nonpreemptive)스케쥴링

가. 선점 스케쥴링

특정 프로세스가 중앙처리장치를 효율적으로 사용할 수 없는 시점에 이를 때마다 중 앙처리장치의 사용권이 다른 프로세스로 옮겨지는 방식으로 높은 우선순위의 프로세 스들이 급하게 실행해야 할 경우에 유용하다.

① 대화식 시분할 시스템에서 빠른 응답시간을 유지하는 데에 필요하다.

② 경비가 많이 들고 오버헤드까지 초래한다.

③ 효과적인 선점을 하려면 준비 상태의 프로세스가 많아야한다.

④ 우선순위를 고려해야 한다.

⑤ 문맥교환의 횟수가 비선점 방식에 비해서 많다.

나. 비선점 스케쥴링

어떤 자원이 어떤 프로세스에 할당이 되면 실행을 종료할 때까지 그 프로세스가 중앙처 리장치의 사용권을 독점하여 사용하는 것으로 짧은 작업들을 기다리게 되는 경우가 있 지만 모든 프로세스 관리에 공정하다.

① 응답시간의 예측이 쉽다.

② 문맥교환의 횟수가 적다.

③ 일괄처리 방식에 적합한 방식이다.

참조) 우선순위(Priority)

① 정적 우선순위(static priority): 프로세스 실행중 우선순위가 변하지 않는 것으로 구현이 용이하고 동적 우선순위에 비해 오버헤드가 적다.

② 동적 우선순위(dynamic priority): 처음에 정해진 우선순위를 상황에 맞게 계속조정하여 사용하므로 구현이 복잡하고 정적 우선순위에 비해 오버헤드가 크다.

프로세서 스케쥴링의 종류

선점( Preemption)

1. RR (Round Robin )

① FIFO스케쥴링과 같이 도착 순으로 디스패치되는 방식

② 타임 슬라이스(time slice) 혹은 시간 할당량(time quantum)에 의해 시간제한을 받음

시간할당량이 클 경우 : FIFO스케쥴링 방법과 차이가 없게 됨

시간할당량이 적은 경우 : 문맥교환 오버헤드가 상대적으로 커지게 되어 시스템은 대부분의 시간을 문맥교환(context switching)에 소비하게 됨

③ 대화식으로 사용하는 시분할 시스템에 적합

④ FIFO를 선점 스케쥴링으로 변형시킨 방법

2. SRT (Shortest Remaing Time)

① SJF스케쥴링기법을 선점 기법으로 변형시킨 방법

② 시분할 시스템에 유용하다.

③ 작업이 끝나기까지 남아 있는 실행시간의 추정치가 가장 작은 프로세스를 먼저 실행함

④ SJF스케쥴링기법보다 오버헤드가 큼

3. Multilevel Feedback Queue

① 짧은 작업에 우선권

② 입출력 위주의 작업들에게 우선권

③ 큐에서 FIFO 형태로 이동

(마지막 단계의 큐에서는 프로세스가 종료될 때까지 RR방식으로 순환)

④ 낮은 단계로 내려갈수록 프로세스의 시간 할당량이 커짐

비선점 ( Non - preemption )

1. FIFO ( First In First Out )

① 준비 큐(ready queue)에서 도착한 순서에 따라 디스패치 됨

② 응답시간 차가 적기 때문에 예측이 쉬움

③ 대화식 시스템에는 적합하지 않음

2. SJF ( Shortest Job First )

① 작업이 끝나기까지의 실행시간의 추정치가 가장 적은 작업을 먼저 실행 함 (짧은 작업들에 우선적으로 서비스)

② 평균 대기시간을 최소화 시킬수 있음

3. 우선순위 ( Priority )

① 각 프로세스에게 우선순위를 부여하여 우선순위가 높은 순서대로 처리함

② 우선순위가 같을 때는 FIFO또는 SJF을 도입하여 실행 함

4. 기한부 ( Deadline Scheduling )

작업들을 마감시간까지 완성하도록 계획한 스케쥴링

5. HRN ( Highest Response Ratio Next )

① SJF스케쥴링기법의 약점인 긴 작업과 짧은 작업간의 지나친 불평등들을 어느 정도 보완한 방법

② 각 작업의 우선순위는 그 작업이 서비스를 받을 시간뿐 아니라 그 작업이 서비스를 기다린 시간 두 가지의 함수로 결정됨

응답률 = (대기한 시간 서비스 받을 시간)/ 서비스 받을 시간

ㅁ 시스템이 안전 상태에 있는 지 알아보기 위해 safety algorithm 을 적용해본다.

 

          1) 초기상태 (n = 5, m = 4)

 Work := Available = (1, 5, 2, 0)
 Finish [i] := false for i = 1,2, …,5

	Allocation				Max				Need				Available
	A	B	C	D	A	B	C	D	A	B	C	D	A	B	C	D
P0	0	0	1	2	0	0	1	2	0	0	0	0	1	5	2	0
P1	1	0	0	0	1	7	5	0	0	7	5	0
P2	1	3	5	4	2	3	5	6	1	0	0	2
P3	0	6	3	2	0	6	5	2	0	0	2	0
P4	0	0	1	4	0	6	5	6	0	6	4	2

 

2) - Finish[i] = false and Needi ≤ Work,  If no such i exists, go to step 4

                  i = 1 ; Finish[1] = false & Need1(0, 0, 0, 0) ≤ Work (1, 5, 2, 0) → 성립

    - Work := Work + Allocation(i), Finish[i] := true, go to step 2

                  Work := Work (1, 5, 2, 0) + Allocation1(0, 0, 1, 2) = (1, 5, 3, 2)

                  Finish[1] := true, go to step 2

 

	Allocation				Max				Need				Available
	A	B	C	D	A	B	C	D	A	B	C	D	A	B	C	D
P0	0	0	0	0	0	0	0	0	0	0	0	0	1	5	3	2
P1	1	0	0	0	1	7	5	0	0	7	5	0
P2	1	3	5	4	2	3	5	6	1	0	0	2
P3	0	6	3	2	0	6	5	2	0	0	2	0
P4	0	0	1	4	0	6	5	6	0	6	4	2

 

 

3) 이렇게 적용해보면, 결과는  <P0, P2, P1, P3, P4>순서로 진행되어 safety requirement가 된다.

	Allocation				Max				Need				Available
	A	B	C	D	A	B	C	D	A	B	C	D	A	B	C	D
P0	0	0	0	0	0	0	0	0	0	0	0	0
P1	0	0	0	0	0	0	0	0	0	0	0	0
P2	0	0	0	0	0	0	0	0	0	0	0	0
P3	0	0	0	0	0	0	0	0	0	0	0	0
P4	0	0	0	0	0	0	0	0	0	0	0	0	3	14	12	12

 

3) 프로세스 P1이 (0, 4, 2, 0)의 자원 요청시, 그 요청의 수용여부

ㅁ Request1  ≤ Available ; Request1(0, 4, 2, 0)  ≤ Available(1, 5, 2, 0) → 성립

 

	Allocation				Max				Need				Available
	A	B	C	D	A	B	C	D	A	B	C	D	A	B	C	D
P0	0	0	1	2	0	0	1	2	0	0	0	0	1	1	0	0
P1	1	4	2	0	1	7	5	0	0	3	3	0
P2	1	3	5	4	2	3	5	6	1	0	0	2
P3	0	6	3	2	0	6	5	2	0	0	2	0
P4	0	0	1	4	0	6	5	6	0	6	4	2

 

ㅁ 요청시 P1의 Allocation  := P1의 Allocation +  Request1(0, 4, 2, 0) = (1, 4, 2, 0)

ㅁ 요청시 P1의 Need  := P1의 Need - 요청시 P1의 Allocation = (0, 3, 3, 0)

ㅁ 요청시 Available  := Available -  Request1(0, 4, 2, 0) = (1, 1, 0, 0)

 

ㅁ safety algorithm 을 적용해보면, <P0, P2, P1, P3, P4>순서로 진행되어 safety requirement가 된다.

    P1의 자원 요청은 그 즉시 수용하지는 못하나, 중간 정도에 수용요청을 들어줄 수 있다.

 

4) 은행원 알고리즘과 교착상태 방지(prevention)

ㅁ 은행원 알고리즘은 교착상태 회피(avoidance) 알고리즘이다. 교착상태를 회피하는 것은 사용자(프로세스)가 자원이 어떻게 요청될 지에 대한 추가 정보를 제공하도록 요청하는 것이다. 은행원 알고리즘은 프로세스가 시작할 때 프로세스가 가지고 있어야 할 자원의 최대 개수를 자원 종류마다 신고하여야 한다. 또한, 교착상태 회피 알고리즘은 시스템에 순환 대기 상황이 발생하지 않도록 자원 할당 상태(가용 자원의 수, 할당된 자원의 수, 프로세스들의 최대 요구 수)를 검사한다. 이에 반해 교착상태 방지(prevention)는 요청방법을 제약하여 교착상태를 예방하는 것인데, 교착상태가 발생할 때 필요한 네 가지의 필요 조건 중 최소한 하나가 성립하지 않도록 보장함으로써 교착상태의 발생을 예방한다.

 하지만, 교착 상태 방지(prevention)는 지나치게 제한적이며, 교착상태 회피(avoidance)도 흔하게 유효하지 않는 정보를 요구할 수 있다.

 

5) 은행원 알고리즘을 분산시스템에서 사용하는 방법 및 문제점

ㅁ 교착 상태 방지와 회피 알고리즘들을 약간 수정하면 분산 시스템에서도 사용될 수 있다. 예를 들면, 시스템 내의 스로세스 중 하나를 은행원 알고리즘을 수행하는 데 필요한 정보를 유지하는 프로세스(은행원)로 지정함으로써 은행원 알고리즘을 분산 시스템에 사용할 수 있다.

다만, 은행원 알고리즘은 쉽게 구현될 수 있지만, 추가 비용이 너무 크다. 은행원에게 오고 가는 메시지가 너무 많기 때문에 은행원이 병목(bottleneck)이 될 수 있다.

Deadlock의 4대 조건.

1. Mutual Exclusion

2. Hold and Wait

3. No Preemtion

4. Circular Wait

조건이 만족 됐을 때 Deadlock, 즉 교착상태에 빠지게 된다.

Deadlock 상태를 깨 부수기 위해서는 원인을 찾고, 그거에 맞는 대처 방법을 쓰면 된다.

이는 프로그래밍을 하는 사람이나, OS를 공부한 사람은 다 알고 있는 내용이다. 기본적인 내용이기도 하고.

OS 상태에서는 Deadlock에 대한 솔루션이 이미 나와있다. 그런데 현실세계는 어떠한가.

현재 나라가 돌아가는 모습이나 기타 다른 곳에서 돌아가는 것을 보면 교착상태에 빠진것 같다는 생각을 하곤 한다. 2개 아니 그 이상이 맞물려서 물러섬 없이 버티니깐 오도 가도 못하는 상태가 되는 것.

가장 화끈한건, 하나를 없애버리는 것이다. 그러면 방해물이 사라져서 잘 뚫릴테니깐. 그런데 현실성은 0이다. 쿠데타가 일어나지 않는 이상 이와 같은 일이 일어날 수가 있겠는가.

OS가 아닌 다른 곳에서의 교착상태에 대한 솔루션이 절실한 때가 아닌가 싶다. 그래야 교착상태를 해결하고 막힘 없이 잘 돌아갈 테니깐. 사회를 재부팅 할 수도 없는 노릇이고, 어서 잘 해결되기를 바랄 뿐이다. 그래야 다들 살아남을 수 있을테니깐.