Algorithms presented in this thesis are based on general request models, OR model and AND/OR model. In the models, each task may wish for any one of a number of resources. For such a general model, this proposes distributed deadlock detection algorithms and a real-time scheduling algorithm.
This thesis proposes two deadlock detection algorithms: an algorithm for OR-model and an algorithm for AND/OR model. The algorithm for OR-model is useful for a system of processes with CSP-$like^1$ communication. In the model, the existence of a cycle in a wait-for graph is the necessary condition of a deadlocked state. The proposed algorithm does not send control messages for deadlock detection to all dependents at the same time, but it sends a message to only one selected node of several dependents until a cycle is detected. If any cyclic wait-for state is not found, there is not any deadlock. When several separate cycles of wait-for processes are found by several initiators, all deadlocks are detected by communication of leader processes of those cycles.
For the AND/OR model, there does not appear to be a familiar construct of graph theory to describe a deadlock situation in terms of the wait-for graph. But, the existence of a cycle in a wait-for graph is the necessary condition of any deadlock. The algorithm uses two levels in detecting a deadlock. The first level algorithm detects a wait-for cycle with a low cost. In the first level of the algorithm, some AND-deadlock and no-deadlock are detected. If a cycle is not found by the algorithm, a deadlock does not exist. If all nodes of a detected cycle have AND-type requests, they are deadlocked. The algorithm in this paper detects such a simple deadlock or a no-deadlock of a no-deadlocked state with low cost. Thereafter, if there is a possibility that a complex deadlock exists, a more expensive algorithm is initiated as the second level algorithm by qualified initiators, which satisfy a condition for the initiation.
The scheduling algorithm proposed in this thesis uses two measures, survivability and impact, for scheduling tasks with timing and resource constraints which a have alternative resources. The survivability is a metric to show how much a task is urgent and it is constrained to its resources. The impact of a resource for a task is to show how much other tasks are influenced by the allocation of the resource to the task. The scheduling algorithm uses the survivability to schedule tasks on multiple processors. After a task is picked out to be run in a time slice with the survivability, the least impact resources are allocated from several alternative resources.
분산 환경등에서는 시스템 내의 각 자원을 대체할 수 있는 대체 자원이 존재한다. 본 논문에서는 여러 대체자원 중 하나의 자원을 요구하는 일들을 지원하는 OR 모델 및 AND/OR 모델을 위한, 분산 교착 상태 검출 알고리즘 및 스케쥴링 알고리즘을 제시한다.
분산 시스템에서의 교착 상태를 검출하기 위해서는 시스템내의 각 노드간의 커뮤니케이션이 필요하다. 교착 상태를 검출하기 위한 기존의 방법들은 OR 모델 혹은 AND/OR 모델에서의 교착 상태를 검출 하지 못하거나, 시스템내의 각 노드간의 커뮤니케이션 양이 지나치게 많다는 단점이 있다. 본 논문에서는 OR 및 AND/OR 모델에서의 교착 상태를 적은 양의 커뮤니케이션 메세지 로써 검출할 수 있기 위해 두 계층을 갖도록 설계했다. 첫 번째 계층은 분산 시스템에서의 각 노드간의 대기 상태 (Cyclic Wait-for State) 를 적은 양의 커뮤니케이션 메세지 로써 검출하는 역할을 한다. 첫 번째 계층 알고리즘에 의해 검출이 된 그러한 대기 상태가 OR 형태의 자원을 요구 하는 OR-노드를 포함하지 않으면 그 대기 상태(Cyclic Wait-for State)는 교착 상태(Deadlocked State)인 것으로 선언 된다. 만약 OR-노드를 포함하면 좀 더 복잡한 형태의 교착 상태가 의심 되므로 두 번째 계층의 알고리즘을 수행한다. 두 번째 계층의 알고리즘은 AND/OR 모델을 위해 기존에 발표된 방법을 이용하는 데, 기존의 방법만으로는 최악의 경우에는 모든 노드가 그 알고리즘을 동작시켜서 엄청난 양의 메세지가 분산 시스템내에 흐를 수 있다. 이에 반해 본 논문에서 제안하는 방법은 최악의 경우라도 자격을 갖춘 노드(Qualified node)만이 두 번째 계층의 알고리즘을 동작시킴으로써 메세지 수를 줄일 수 있도록 설계했다.
본 논문에서 제안한 스케쥴링 방법은 대체 자원을 갖는 실시간 작업 들을 효율적으로 마감 시간안에 처리 해주기 위해 두가지 정보 Survivability와 Impact를 정의하여 이용한다. Survivability 는 각 실시간 작업들이 마감 시간과 자원들에 의해 제약을 받는 정도(Resource Constraints)를 측정 하기 위한 척도로서, Impact는 각 실시간 작업들에 의해 요구되는 각 대체 자원의 다른 실시간 작업들에 대한 영향을 측정 하기 위해 정의 했다. 모의 시험에 의해 기존의 방법과 본 논문에서 정의한 Survivability 와 Impact 를 이용한 방법을 비교해 보았으며, 그 결과로써 본 논문에서 제안된 방법이 유용함을 보였다.
