In a cloud environment, workflow management system which executes the user requested workflow application within SLA by allocating resources from cloud service providers is emerged. Therefore, multi workflow scheduling problem within the SLA received attentions. Most of research works on workflow scheduling were limited to the single workflow. In addition, research works about multi workflow scheduling considers only the workflow execution priorities or do not copes with user SLA. Therefore we propose a multi-workflow scheduling heuristics that changes the workflow topology into fragments and schedule them onto proper VM. Our heuristics have three steps: workflow fragmentation, fragment scheduling, workflow configu-ration.
Workflow fragmentation process recursively identifies the workflow’s critical path by Petri Net model. Then, sub-critical paths in identifying process will be included to the fragments. With this step, we can simpli-fy the complex workflow topology into fragments with sequential tasks. Therefore, we can expect the com-plexity of scheduling process will get lower and resources will be scheduled in an economizing way.
Fragment scheduling heuristics schedules fragments onto the VMs in a fast way using the fact that fragments are consisted of sequential tasks. Our heuristics are suitable for the cloud environment and has a low complexity. Therefore it can be applied to the multi-workflow environment.
Workflow reconfiguration schemes offers some algorithms that save the resources or the execution time by simply changing the assigned VMs.
클라우드 환경에서 여러 사용자가 보낸 워크플로우 어플리케이션을 클라우드 제공자로부터 VM을 할당받아 사용자가 원하는 SLA 이내로 수행시키는 워크플로우 관리 시스템이 주목을 받게 되었고, 여러 워크플로우 요청과 각 SLA를 보장하기 위한 스케줄링 알고리즘이 필요하게 되었다. 기존에도 워크플로우 스케줄링에 관한 연구는 많이 있었으나 대부분이 단일 워크플로우에 국한되고, 다중 워크플로우의 경우에 관한 연구도 SLA를 고려하지 않거나 워크플로우 구조를 바꾸지 않고 들어온 요청에 대한 우선순위를 바꿔 수행하는 정도라는 한계가 있었다. 따라서 본 논문에서는 워크플로우 구조를 임계 경로(Critical Path)를 이용해 여러 조각으로 분할하고, 각각의 조각을 순서에 맞게 스케줄링해 전체 워크플로우를 SLA 이내로 수행시키는 휴리스틱에 대해 연구하였다. 휴리스틱은 워크플로우 분할 과정, 조각 스케줄링 과정, 워크플로우 재구성 과정의 3개 단계로 구성된다.
워크플로우 분할 과정은 복잡한 워크플로우 구조가 요청으로 들어오면 페트리넷 모델을 이용해 재귀적으로 워크플로우의 임계 경로를 구하고, 그 과정 속에서 나온 부분 임계경로를 워크플로우 조각으로 취하는 방법이다. 이 과정을 거침으로 인해 복잡한 워크플로우 구조가 일련의 작업의 집합들로 나뉘게 되며, 스케줄링 휴리스틱의 복잡도가 낮아지게 되는 효과를 볼 수 있다. 또한, 다중 워크플로우들을 일련의 조각들로 나눠놓음으로써 자원을 절약적으로 사용할 수 있도록 해 준다.
조각 스케줄링 과정은 위에서 구한 워크플로우 조각들이 순차적인 구조를 띄고 있음을 이용해 클라우드 과금 정책을 이용하여 최소한의 VM만을 사용토록 하는 스케줄링 정책이다. 시간 복잡도가 낮고 클라우드 환경에서 적용 가능해 다중 워크플로우 환경에서의 스케줄링에 적합하다.
클라우드 재구성 과정은 위의 과정을 통해 스케줄링을 했을 때, VM의 배치를 바꿈으로써 비용이나 실행 시간 측면에서 추가적인 이득을 볼 수 있는 경우 적용되는 여러 가상 머신 관리 알고리즘을 제시하고 있다.
