과제 최종 보고서 | 20185196 추교현

// automated_warehouse.c /// run_automated_warehouse 함수 n = atoi(argv[1]); const char* input = argv[2]; char** segments = parse_string(input); create_maps(); // 이동에 참고할 maps 초기화 init_message_boxes(n+1); // 모든 스레드가 참고할 message_box 초기화

// aw_manager.c /// parse_string 함수 char** parse_string(const char* str) { int num_segments = 1; // 최소 하나의 세그먼트 존재 // ':' 기준으로 세그먼트의 개수 파악 for (int i = 0; str[i] != '\0'; i++) { if (str[i] == ':') { num_segments++; } } // 문자열 포인터 배열 동적 할당 char** result = (char**)malloc(sizeof(char*) * num_segments); if (result == NULL) { return NULL; } char* saveptr; // strtok_r 상태 저장을 위한 포인터 int index = 0; char* temp_str = my_strdup(str); char* token = strtok_r(temp_str, ":", &saveptr); while (token != NULL) { result[index++] = my_strdup(token); token = strtok_r(NULL, ":", &saveptr); } free(temp_str); // 사용한 임시 문자열 메모리 해제 return result; }

// aw_manager.c /// create_maps 함수 void create_maps() { for (int i = 0; i < ROW; i++){ for (int j = 0; j < COL; j++){ if (map_draw_default[i][j] == 'X' || (map_draw_default[i][j] >= '0' && map_draw_default[i][j] <= '9')) { maps[i][j] = 1; } else { maps[i][j] = 0; } } } }

// aw_manager.c /// init_message_boxes 함수 void init_message_boxes(int n) { boxes_from_center = malloc(sizeof(struct message_box) * (n+1)); boxes_from_robots = malloc(sizeof(struct message_box) * (n+1)); for (int i = 0; i < n; i++) { // 처음 위치는 무조건 W(5, 5) boxes_from_center[i].msg.row = ROW_W; boxes_from_center[i].msg.col = COL_W; boxes_from_center[i].dirtyBit = 1; // 1인 이유 : 처음에는 center에서 모든 로봇에게 메시지를 보내야 하기 때문 boxes_from_robots[i].msg.row = ROW_W; boxes_from_robots[i].msg.col = COL_W; boxes_from_robots[i].dirtyBit = 0; } }

// automated_warehouse.c /// robot 생성 및 초기화 char name[10]; robots = malloc(sizeof(struct robot) * (n+1)); for (int i = 0; i < n; i++) { snprintf(name, sizeof(name), "R%d", i+1); NumCharPair pairs = split_string(segments[i]); // Ex) "2A" => {2, 'A'} // Ex) 2와 'A'에 해당하는 좌표 각각 구하기 Position mid_pos = findCharPosition(pairs.num + '0'); // '0' 넣은 이유 : 숫자를 문자로 바꾸기 위해 Position final_pos = findCharPosition(pairs.letter); // 초기 좌표는 W 위치인 (5, 5)로 설정 setRobot(&robots[i], name, 5, 5, 0, 0, mid_pos.row, mid_pos.col, 0, final_pos.row, final_pos.col, 0); }

// automated_warehouse.c /// robots thread 생성 tid_t* threads = malloc(sizeof(tid_t) * (n+1)); int* idx = malloc(sizeof(int) * (n+1)); for (int i = 0; i < n; i++) { idx[i] = i; threads[i] = thread_create(robots[i].name, 0, &robots_thread, &idx[i]); } /// center thread 생성 thread_create("CNT", 0, &cnt_thread, NULL);

// aw_thread.c /// 현재 스레드를 block시키고 blocked_threads 리스트에 넣는 함수 void block_thread(){ enum intr_level old_level; old_level = intr_disable (); list_push_back(&blocked_threads, &thread_current ()->elem); thread_block (); intr_set_level (old_level); }

// aw_thread.c /// blocked_threads 리스트 안에 있는 모든 스레드들을 꺼내고 unblock 시키는 함수 void unblock_threads(){ enum intr_level old_level; old_level = intr_disable (); while (!list_empty(&blocked_threads)){ struct thread *t = list_entry(list_pop_front(&blocked_threads), struct thread, elem); thread_unblock(t); } intr_set_level (old_level); }

// aw_message.c /// message_box : robot -> center void message_from_robots(int idx, struct message_box* msg_box, int robot_row, int robot_col) { msg_box->msg.row = robot_row; msg_box->msg.col = robot_col; msg_box->dirtyBit = 1; }

// aw_message.c /// message_box : center -> robot void message_from_center(int idx, struct message_box* msg_box, int n_r, int n_c) { msg_box->msg.row = n_r; msg_box->msg.col = n_c; msg_box->dirtyBit = 1; }

// aw_manager.c int get_next_pos(int c_r, int c_c, int t_r, int t_c) { int min_distance = 1000; int next_pos = 4; // 4인 이유 : 움직일 수 없을 때, 제자리 유지를 위해서 for (int i = 0; i < 4; i++) { int nr = c_r + dr[i]; int nc = c_c + dc[i]; // 만약 다음 지점이 목표 지점이라면, 그 방향으로 이동 if (nr == t_r && nc == t_c) { return i; } if (isValid(nr, nc) && maps[nr][nc] == 0) { /// 목표 지점까지 가장 짧은 거리에 해당하는 방향으로 이동 int distance = bfs(nr, nc, t_r, t_c); if (distance < min_distance) { min_distance = distance; next_pos = i; } } } return next_pos; }

// aw_manager.c int bfs(int c_r, int c_c, int t_r, int t_c) { int visited[ROW][COL] = {0}; // 방문 배열 초기화 int distance[ROW][COL] = {0}; // 거리 저장 배열 // 큐 초기화 Point queue[ROW * COL]; int front = 0, rear = 0; // 시작점을 큐에 삽입 후, 방문 표시 queue[rear++] = (Point){c_r, c_c}; visited[c_r][c_c] = 1; while (front < rear) { // 큐의 맨 앞에 있는 요소 꺼내기 Point cur = queue[front++]; // 만약 목표 지점에 도달했다면, 거리 반환 if (cur.row == t_r && cur.col == t_c) { return distance[t_r][t_c]; } for (int i = 0; i < 4; i++) { int nr = cur.row + dr[i]; int nc = cur.col + dc[i]; // 만약 다음 지점이 목표 지점이라면, 거리 반환 (이게 없으면, 진입 불가) if (nr == t_r && nc == t_c) { return distance[cur.row][cur.col] + 1; } if (isValid(nr, nc) && maps[nr][nc] != 1 && !visited[nr][nc]) { visited[nr][nc] = 1; distance[nr][nc] = distance[cur.row][cur.col] + 1; queue[rear++] = (Point){nr, nc}; } } } return 1000; }

// automated_warehouse.c /// cnt_thread() 함수 int target_row, target_col; if (robots[i].is_loaded) { // 하역 장소로 이동 target_row = robots[i].f_row; target_col = robots[i].f_col; } else { // 적재 장소로 이동 target_row = robots[i].l_row; target_col = robots[i].l_col; }

// automated_warehouse.c void cnt_thread(){ while(1) { // robots thread가 모두 block되면, 실행 int is_full = is_blocked_thread_full(n); if (is_full) { print_map(robots, n); int final_cnt = 0; for (int i = 0; i < n; i++) { if(boxes_from_robots[i].dirtyBit == 1) { // 각 robot이 보낸 메시지를 바탕으로 명령 내리기 ... // 각 robot에게 보낼 message_box 업데이트 message_from_center(i, &boxes_from_center[i], n_row, n_col); boxes_from_robots[i].dirtyBit = 0; } } // 모든 robot이 작업을 완료 if (final_cnt == n) { printf("\n--------- 🎉🎉🎉🎉🎉 Mission Complete 🎉🎉🎉🎉🎉 ---------\n"); break; } increase_step(); unblock_threads(); } } }

// automated_warehouse.c void robots_thread(void* aux){ int idx = *((int *)aux); int test = 0; while(1) { if (boxes_from_center[idx].dirtyBit == 1) { // center가 보낸 메시지를 각 robot 구조체에 업데이트 ... // center에게 보낼 message_box를 업데이트 message_from_robots(idx, &boxes_from_robots[idx], robots[idx].row, robots[idx].col); boxes_from_center[idx].dirtyBit = 0; } // message_box를 보냈다면, 스스로 block 되기 block_thread(); } }

void setRobot(struct robot* _robot, const char* name, int row, ...){ _robot->name = name; _robot->row = row; ... }

char* my_strdup(const char* s) { if (s == NULL) return NULL; size_t size = strlen(s) + 1; char* new_str = malloc(size); if (new_str == NULL) return NULL; strlcpy(new_str, s, size); // strcpy가 아닌 strlcpy를 사용하여 버퍼 오버플로 방지하면서 문자열 복사 return new_str; }

// robots thread 생성 tid_t* threads = malloc(sizeof(tid_t) * (n+1)); for (int i = 0; i < n; i++) { threads[i] = thread_create(robots[i].name, 0, &robots_thread, i); }

// robots thread 생성 tid_t* threads = malloc(sizeof(tid_t) * (n+1)); int* idx = malloc(sizeof(int) * (n+1)); for (int i = 0; i < n; i++) { idx[i] = i; threads[i] = thread_create(robots[i].name, 0, &robots_thread, &idx[i]); }

// aw_thread.c /// 모든 thread가 block되었는지 알려주는 함수 int is_blocked_thread_full(int n) { int size = list_size(&blocked_threads); return size == n; }