[자료구조] 덱 응용 : Work-Steal(A-steal) 알고리즘 구현

구현 사항

 

 

 

 

 

- 각 프로세서들이 각자의 queue를 가지고 작업을 수행


-queue 안에는 순차적으로 실행되어야 하는 Job이 존재


- 동시에 모든 큐를 진행해서 Job을 하나씩 처리한다.


- 자신의 큐가 비어있으면 다른 큐에서 Job을 뺏어 처리한다.

 

 

 

 

구현 방식

 

큐라고는 하지만
처리하는 일은 앞에서 하고
뺏길 때 뺏기는 큐에서는 뒤에서 뺏기기 때문에
앞과 뒤에서 둘 다 요소를 뺄 수 있는 덱을 이용해야 한다.

 

 

덱을 이용해서 큐잉 모델 형식으로
구현을 하면 된다고 생각하고 구현하였다.

 

 

구현

#include <stdio.h>
#include <stdlib.h>
#define MAX_DEQUE 100

int total = 0;
typedef struct{
    char* data[MAX_DEQUE];
    int front,rear;
}Deque;

void error(const char* msg){
    printf("%s\n",msg);
    exit(1);
}
void init(Deque* q){
    q ->front = 0;
    q ->rear = 0;
}
int isFull(Deque* q){
    return q -> front == ((q -> rear) + 1)%MAX_DEQUE;
}
int isEmpty(Deque* q){
    return q -> front == q -> rear;
}
int size(Deque* q){
    return (((q->rear)-(q->front))+MAX_DEQUE)%MAX_DEQUE;
}
int add_front(Deque* q, char* item){
    if(isFull(q)) error("큐 가득참");
    //front는 첫번째 요소 하나 앞이기 때문에 front가 가리키는 곳에는 값이 없다.
    //그러니 front가 가리키는 곳에 값을 넣어준다.
    q -> data[q->front] = item;
    q -> front = (((q -> front) - 1) + MAX_DEQUE) % MAX_DEQUE;
}
int add_rear(Deque* q,char* item){
    if(isFull(q)) error("큐 가득참");
    q -> rear = ((q -> rear) +1) % MAX_DEQUE;
    q -> data[q -> rear] = item;
}
char* delete_front(Deque* q){
    if(isEmpty(q)) error("큐 빔");
    q -> front = ((q -> front) +1) % MAX_DEQUE;
    return q->data[q->front];
}
char* delete_rear(Deque* q){
    if(isEmpty(q)) error("큐 빔");
    // rear 인덱스에는 값이 들어있기 때문에 해당 요소의 값을 반환한다.
    char* ret = q->data[q->rear];
    q -> rear = (((q->rear)-1)+MAX_DEQUE)%MAX_DEQUE;
    return ret;
}
//========================= 덱 구현 함수 ==================
}
int main(){
	Deque cpu[3];
	for(int i = 0; i < 3; i++) init(&cpu[i]);
	add_rear(&cpu[0],"Job1");add_rear(&cpu[0],"Job2");add_rear(&cpu[0],"Job3");
	add_rear(&cpu[1],"Job4");add_rear(&cpu[1],"Job5");
	add_rear(&cpu[2],"Job6");
	printf("===========작업 시작=========\n");
	while(1){
    	//무한 반복 -> 종료는 밑에서 따로해줌
		total++;
		for(int i = 0; i< 3; i++){
        	//Job이 덱 안에 있다면
			if(!isEmpty(&cpu[i])) {
            	// 덱 안에 있는 Job을 처리
				printf("cpu%d가 %s를 처리했습니다.\n",i,delete_front(&cpu[i]));
			}
            // 덱 안에 없다면
			else
			{
            	// 다른 덱에서 Job을 탐색
				int flag = 0; // 덱을 다 돌았음을 확인하는 플래그
				int idx = i; // 덱의 번호 인덱스
				do{
					idx = (idx+1) % 3; // 덱의 개수만큼 1씩 더하면서 확인
					flag++;
				}
                // 비지 않은 덱을 발견하거나, 덱을 다 돌때까지 반복
				while(isEmpty(&cpu[idx]) && flag < 3);
				if(flag >= 3) {
                //덱을 다 돌았음에도 Job을 발견하지 못하면 종료
					printf("프로세스 종료\n");
					printf("총 프로세스 진행 횟수 : %d\n",total);
					exit(1);
				}
                //찾았으면 그 덱에서 뒤에서 뽑는 것으로 처리
				printf("cpu%d가 cpu%d의 %s를 가져와 처리했습니다.\n",i,idx,delete_rear(&cpu[idx]));
			}
		}
		printf("===========%d번째 작업 종료=========\n",total);
	}

}

결과