마지막 프로세스의 메모리 시작 주소 값을 First Fit, Best Fit, Worst Fit로 얻어오는 과제입니다.
1. 스레드를 사용한다
2. Process 메소드에서 3개의 작업을 돌린다
3. 그 외의 방법
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class allocation_unicode {
static int[][] process;
static int process_max;
static ArrayList<int[]> memory = new ArrayList<>();
// 순서대로 대기(시간이 되지 않음), 대기 큐에 들어감, 작업 중, 작업 완료
static final int STATUS_WAIT_FOR_TIME = 0;
static final int STATUS_WAIT = 1;
static final int STATUS_WORK = 2;
static final int STATUS_FINISH = 3;
// 프로세스
static final int PROC_ARRIVE = 0;
static final int PROC_DELAY = 1;
static final int PROC_EXEC = 2;
static final int PROC_SIZE = 3;
static final int PROC_STATUS = 4;
public static void main(String[] args) {
Read("allocation.inp");
String data = "";
data += Process(0) + System.getProperty("line.separator");
data += Process(1) + System.getProperty("line.separator");
data += Process(2);
Write("allocation.out", data);
}
static void Write(String path, String data) {
try {
FileWriter out = new FileWriter(path);
out.append(data);
out.close();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
static void Read(String path) {
FileReader in;
try {
StringTokenizer token;
in = new FileReader(path);
BufferedReader reader = new BufferedReader(in);
process_max = Integer.parseInt(reader.readLine().trim());
process = new int[process_max][5];
for (int i = 0; i < process_max; i++) {
token = new StringTokenizer(reader.readLine());
process[i][PROC_ARRIVE] = Integer.parseInt(token.nextToken());
process[i][PROC_DELAY] = 0;
process[i][PROC_EXEC] = Integer.parseInt(token.nextToken());
process[i][PROC_SIZE] = Integer.parseInt(token.nextToken());
process[i][PROC_STATUS] = STATUS_WAIT_FOR_TIME;
}
reader.close();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
static int Process(int alloc_type) {
ArrayList<Integer> queue = new ArrayList<>();
boolean finished = false;
for (int[] proc : process) {
proc[PROC_STATUS] = STATUS_WAIT_FOR_TIME;
}
int[] hole = { 0, -1, 1000 };
memory.clear();
memory.add(hole);
for (int time = 0; finished==false; time++) {
for (int i = 0; i < process_max; i++) {
if (process[i][PROC_STATUS] == STATUS_FINISH) // 작업이 종료된 프로세스
continue;
if (process[i][PROC_STATUS] == STATUS_WAIT_FOR_TIME
&& process[i][PROC_ARRIVE] == time) {
// 작업 시작
System.out.println(" Find Hole :" + i);
boolean result = Find_Hole(i, alloc_type);
if (result == true)
process[i][PROC_STATUS] = STATUS_WORK;
else if (result == false)
queue.add(i);
}
if (process[i][PROC_STATUS] == STATUS_WORK) {
int time_exec = process[i][PROC_ARRIVE]
+ process[i][PROC_DELAY] + process[i][PROC_EXEC];
if (time_exec == time) {
// 시간이 다 되어 반환한다
Return_Memory(i);
int req_queue = 0;
if (queue.size() > 0) {
do {
int req_queue_pid = queue.get(req_queue);
boolean result = Find_Hole(req_queue_pid,
alloc_type);
System.out.println(" Request Memory : "
+ req_queue_pid + " : " + result);
if (result == true) {
process[req_queue_pid][PROC_DELAY] = time
- process[req_queue_pid][PROC_ARRIVE];
process[req_queue_pid][PROC_STATUS] = STATUS_WORK;
queue.remove(req_queue);
} else {
req_queue++;
}
} while (req_queue < queue.size());
}
}
}
}
System.out.println(GetMemory(time));
if (process[process_max - 1][PROC_STATUS] == STATUS_WORK) {
System.out.println("Finish");
for (int i = 0; i < memory.size(); i++) {
if (memory.get(i)[1] == process_max - 1) {
finished = true;
return memory.get(i)[0];
}
}
}
}
return -1;
}
static String GetMemory(int time) {
String str = "Time " + time + " : ";
for (int[] is : memory) {
str += "<" + is[0] + ", " + is[1] + ", " + is[2] + "> ";
}
return str;
}
// 홀을 찾아 빈 곳 중 가장 처음에 배치한다
static boolean Find_Hole(int pid, int alloc_type) {
int need_for_memory = process[pid][PROC_SIZE];
int pos = -1;
int difference = -1;
for (int i = 0; i < memory.size(); i++) {
int[] mem_tmp = memory.get(i);
// 만약 홀 공간이 필요한 공간보다 크다?
if (mem_tmp[1] == -1 && mem_tmp[2] >= need_for_memory) {
if (alloc_type == 0) {
pos = i;
break;
} else if (alloc_type == 1) { // Best Fit
int diff_tmp = mem_tmp[2] - need_for_memory;
if (difference == -1 || diff_tmp < difference) {
difference = diff_tmp;
pos = i;
}
} else if (alloc_type == 2) { // Worst Fit
int diff_tmp = mem_tmp[2] - need_for_memory;
if (difference == -1 || diff_tmp > difference) {
difference = diff_tmp;
pos = i;
}
}
}
}
if (pos != -1) {
int[] mem_add = new int[3];
int[] mem_set = memory.get(pos);
mem_add[0] = mem_set[0];
mem_add[1] = pid;
mem_add[2] = need_for_memory;
memory.add(pos, mem_add);
mem_set[0] += need_for_memory;
mem_set[2] -= need_for_memory;
memory.set((pos + 1), mem_set);
return true;
}
return false;
}
static void Return_Memory(int pid) {
int pid_pos = 0;
System.out.println(" Return Memory : " + pid);
for (int i = 0; i < memory.size(); i++) {
if (memory.get(i)[1] == pid) {
pid_pos = i;
break;
}
}
int[] mem_return = memory.get(pid_pos);
int[] mem_return_prev = null;
int[] mem_return_next = null;
int merge_type = 0; // 0 : 합쳐지지 않음, 1 : 이전과 합쳐짐, 2 : 다음과 합쳐짐, 3 : 3개가
// 합쳐짐
if (pid_pos > 0)
mem_return_prev = memory.get(pid_pos - 1);
if (pid_pos < memory.size() - 1)
mem_return_next = memory.get(pid_pos + 1);
mem_return[1] = -1;
// 이전 메모리 공간이 홀인지 확인
if (mem_return_prev != null && mem_return_prev[1] == -1) {
// 이전 메모리 공간과 합침
merge_type = 1;
mem_return_prev[2] += mem_return[2];
}
// 다음 메모리 공간이 홀인지 확인
if (mem_return_next != null && mem_return_next[1] == -1) {
// 이전 메모리 공간과 합침
if (merge_type == 0) {
merge_type = 2;
mem_return[2] += mem_return_next[2];
} else if (merge_type == 1) {
merge_type = 3;
mem_return_prev[2] += mem_return_next[2];
}
}
switch (merge_type) {
case 0:
break;
case 1:
memory.remove(pid_pos);
break;
case 2:
memory.remove(pid_pos + 1);
break;
case 3:
memory.remove(pid_pos);
memory.remove(pid_pos);
break;
}
}
}
