我正在尝试编写一个程序来模拟调度算法(FCFS)。该程序接受一个输入,一个包含以下信息的
txt
文件:
# Number of Processes
#PID #CPUTime #IOTime #ArrivalTime
输入文件示例如下:
3
0 2 2 0
1 2 1 5
2 2 1 2
我正在尝试编写一个程序来获取此进程元数据,并模拟 FCFS 算法。每个进程运行 1/2 * CPU 时间,阻塞 IO 时间,然后再运行 1/2 * CPU 时间。这里所需的输出是:
0 0:running
1 0:blocked
2 0:blocked
3 0:running 2:ready
4 2:running
5 1:running 2:blocked
6 1:blocked 2:running
7 1:running
我目前有以下内容,为了重现性而最小化:
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>
struct Process;
struct MyCustomQueue;
void fcfs(int, FILE);
void enqueue(struct MyCustomQueue *, struct Process *);
struct Process *dequeue(struct MyCustomQueue *);
struct Process *peek(struct MyCustomQueue *queue);
struct Process {
int processID;
int cpuTime;
int ioTime;
int arrivalTime;
int cpu_half_1;
int cpu_half_2;
bool ready;
bool running;
bool blocked;
bool completed;
struct Process *next;
};
struct MyCustomQueue {
struct Process *front;
struct Process *tail;
int size;
};
void enqueue(struct MyCustomQueue *queue, struct Process *process) {
if (queue->size == 0) {
queue->front = process;
queue->tail = process;
} else {
queue->tail->next = process;
queue->tail = process;
}
queue->size++;
}
struct Process *dequeue(struct MyCustomQueue *queue) {
if (queue->size == 0) {
return NULL;
} else {
struct Process *process = queue->front;
queue->front = process->next;
queue->size--;
return process;
}
}
struct Process *peek(struct MyCustomQueue *queue) {
if (queue->size == 0) {
return NULL;
} else {
return queue->front;
}
}
int main(int argc, char *argv[]) {
FILE * fp; // for creating the output file
char filename[100] = ""; // the file name
//Check that the file specified by the user exists and open it
if (!(fp = fopen(argv[1], "r"))) {
printf("Cannot open file %s\n", argv[2]);
exit(1);
}
int num_processes; // the number of processes
fscanf(fp, "%d", &num_processes); // read the number of processes
fcfs(num_processes, *fp);
// Close the processes file
fclose(fp);
return 0;
}
void fcfs(int num_processes, FILE fp) {
struct Process processes_array[num_processes];
struct MyCustomQueue ready_queue = {NULL, NULL, 0};
// Add each process to the array
int i;
for (i = 0; i < num_processes; i++) {
int processID, cpuTime, ioTime, arrivalTime;
fscanf(&fp, "%d %d %d %d", &processID, &cpuTime, &ioTime, &arrivalTime);
struct Process process = {processID, cpuTime, ioTime, arrivalTime, ceil(0.5*cpuTime), ceil(0.5*cpuTime), false, false, false, false, NULL};
processes_array[i] = process;
}
// Sort the array by arrival time, and if there is a tie, sort by process ID.
for (int a = 0; a < num_processes; a++) {
for (int b = 0; b < num_processes - 1; b++) {
if (processes_array[b].arrivalTime > processes_array[b + 1].arrivalTime) {
struct Process temp = processes_array[b];
processes_array[b] = processes_array[b + 1];
processes_array[b + 1] = temp;
} else if (processes_array[b].arrivalTime == processes_array[b + 1].arrivalTime) {
if (processes_array[b].processID > processes_array[b + 1].processID) {
struct Process temp = processes_array[b];
processes_array[b] = processes_array[b + 1];
processes_array[b + 1] = temp;
}
}
}
}
int cycle = 0;
int completed_processes = 0;
struct Process *current_process = malloc(sizeof(struct Process));
struct Process default_process = {-1, -1, -1, -1, -1, -1, false, false, false, false, NULL};
current_process = &default_process;
while (completed_processes < num_processes) {
printf("%d ", cycle);
// Go through processes_array and check if any processes have arrived. If they have, enqueue them.
for (int i = 0; i < num_processes; i++) {
if (processes_array[i].arrivalTime == cycle) {
enqueue(&ready_queue, &processes_array[i]);
}
}
// Go through the processes_array and check all processes that marked as blocked. If they are done with their IO time, mark them as ready.
// Otherwise, print "%d:blocked" for the process.
for (int i = 0; i < num_processes; i++) {
if (processes_array[i].blocked) {
if (processes_array[i].ioTime == 0) {
processes_array[i].blocked = false;
processes_array[i].ready = true;
processes_array[i].completed = false;
processes_array[i].running = false;
enqueue(&ready_queue, &processes_array[i]);
} else {
printf("%d:blocked ", processes_array[i].processID);
}
}
}
// If the current process is not assigned, assign it to the first process in the ready queue.
if (current_process->processID == -1) {
current_process = dequeue(&ready_queue);
current_process->ready = false;
current_process->running = true;
current_process->blocked = false;
current_process->completed = false;
printf("%d:running ", current_process->processID);
}
// Print the ready queue, not including the process already running.
struct Process *current = ready_queue.front;
while (current != NULL) {
printf("%d:ready ", current->processID);
current = current->next;
}
// Scheduling Logic
// A Process takes up `cpu_half_1` cycles to complete the first half of its CPU time.
// Then it is blocked for IO time.
// Then it takes up `cpu_half_2` cycles to complete the second half of its CPU time.
// Then it is completed.
if (current_process->cpu_half_1 > 0) {
current_process->cpu_half_1--;
} else {
current_process->cpu_half_2--;
}
if (current_process->cpu_half_1 == 0) {
// First Half done - block for IO
if (current_process->ioTime > 0) {
current_process->blocked = true;
current_process->running = false;
current_process->ready = false;
current_process->completed = false;
}
// Second Half done - complete
if (current_process->cpu_half_2 == 0) {
current_process->blocked = false;
current_process->running = false;
current_process->ready = false;
current_process->completed = true;
completed_processes++;
}
current_process = &default_process;
}
printf("\n");
// completed_processes++;
cycle++;
}
printf("\n");
}
我得到的输出是(使用 lldb 运行)
0 0:running
1
2 0:blocked 1:running
3 0:blocked 2:ready
4 0:blocked 2:ready
5 0:blocked 1:blocked 2:running
6 0:blocked 1:blocked
7 0:blocked 1:blocked
8 0:blocked 1:blocked
Process 57668 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=1, address=0x18)
frame #0: 0x0000000100003a3c scheduling`zero(num_processes=3, fp=FILE @ 0x000000016fdfef80) at scheduling.c:237:36
234 // If the current process is not assigned, assign it to the first process in the ready queue.
235 if (current_process->processID == -1) {
236 current_process = dequeue(&ready_queue);
-> 237 current_process->ready = false;
238 current_process->running = true;
239 current_process->blocked = false;
240 current_process->completed = false;
Target 0: (fcprogram) stopped.
所以到目前为止的输出都是不受欢迎的,并且分段错误让我感到困惑。
几个问题:
您应该始终检查 fscanf() 的返回值。例如:
if (fscanf(fp, "%d", &num_processes) != 1) {
<<error handling >>
您应该在访问 argv[] 之前检查
argc
,并打印与文件名相同的值(argv[1] 或 argv[2]):
if (!(fp = fopen(argv[1], "r"))) {
printf("Cannot open file %s\n", argv[2]);
exit(1);
}
堆栈跟踪非常有帮助。但是...
代码中的哪一行崩溃了?哪个语句对应于“scheduling.c:237:36”?
您是否已单步执行调试器、在第 237 行设置断点并检查变量?
我发现了一些其他问题:
删除行
struct Process *current_process = malloc(sizeof(struct Process));
:这是内存泄漏。
你已经这样做了,所以你无论如何都不需要多余的行/不必要的“malloc()”:
struct Process default_process = {-1, -1, -1, -1, -1, -1, false, false, false, false, NULL};
struct Process *current_process = &default_process;
我怀疑这就是你崩溃的原因:
// If the current process is not assigned, assign it to the first process in the ready queue.
if (current_process->processID == -1) {
current_process = dequeue(&ready_queue);
// <-- So what happens if dequeue() returns NULL?