进程定时器中断实现求助：C语言课程作业问题

我正在完成课程作业，需要实现预定义的processTimerInterrupt函数来处理进程定时器中断，完成进程调度。当前实现存在调度异常问题，特此求助。

给定函数定义 #

/* processTimerInterrupt()
 * Tells the system that an interrupt occurred. 
 * Returns the PID of the new running process
 * or -1 if none are running
 */
int processTimerInterrupt(processStructure* ps);

当前实现代码 #

// 假设processState是已定义的枚举类型
typedef enum {
    EMBRYO,
    RUNNABLE,
    RUNNING,
    // 其他状态如休眠等
} processState;

#define NPROC 5 // 根据示例数组长度假设NPROC为5

typedef struct {
    /* you should not use global variables. Therefore 
     * you use this structure to retain any context/state your
     * simulator needs between calls. Please add anything you need, and
     * the test code will pass this to your functions
     */
    int curr;
    processState state[NPROC];
    int childern[NPROC]; //0, 12, 14, 14, 16
    int parentOf[NPROC]; //-1, 0, 1, 1, 3
   
} processStructure;

int processTimerInterrupt(processStructure* ps) {
    for(int i=0; i < NPROC; i++){
        if(ps->state[i] == RUNNING && ps->state[i+1] == EMBRYO){
            //printf("process pior %d + %d = i 	 %d \n", ps->childern[i], i, ps->state[i]);
            return ps->childern[i];
        }else if(ps->state[i] == RUNNABLE){
            ps->state[i] = RUNNING;
            return ps->childern[i];
        }else if(ps->state[i] == RUNNING){
            ps->state[i] = RUNNABLE;
            continue;
        }
    }
    return -1;
}

问题现象 #

• 部分测试用例可运行，但添加第3个进程（父进程为0号）时陷入调度异常。
• 例如：0号进程休眠、1号进程处于RUNNING、2号和3号处于RUNNABLE时，永远无法调度到4号进程，出现类似无限循环的情况。
• 添加4号进程后，调用processTimerInterrupt的返回顺序为2、3、2、1、2，完全没有调度到4号的迹象，期间没有调用其他函数。
• 不确定是进程添加逻辑有误，还是processTimerInterrupt函数本身遗漏了关键调度逻辑。

问题分析与修正方案 #

原代码核心问题 #

1. 调度顺序逻辑错误：每次从索引0开始遍历，找到第一个RUNNABLE进程就直接返回，导致后面的进程（如4号）永远无法被调度到，前面的进程会持续抢占调度机会。
2. 数组越界风险：ps->state[i+1] == EMBRYO的判断在i = NPROC-1时会访问数组外的内存，引发未定义行为，且该判断的业务逻辑不清晰（定时器中断不应处理胚胎进程的唤醒）。
3. 未实现轮转调度：没有记录上一次调度的位置，无法保证所有RUNNABLE进程公平获取CPU时间。

修正后的实现代码 #

int processTimerInterrupt(processStructure* ps) {
    // 1. 先将当前运行的进程转为RUNNABLE状态
    for (int i = 0; i < NPROC; i++) {
        if (ps->state[i] == RUNNING) {
            ps->state[i] = RUNNABLE;
            break;
        }
    }

    // 2. 从上次调度的下一个位置开始，环形遍历找第一个RUNNABLE进程
    int start = (ps->curr + 1) % NPROC;
    for (int i = 0; i < NPROC; i++) {
        int idx = (start + i) % NPROC;
        if (ps->state[idx] == RUNNABLE) {
            ps->state[idx] = RUNNING;
            ps->curr = idx; // 更新本次调度的进程索引
            return ps->childern[idx]; // 返回该进程的PID
        }
    }

    // 3. 没有可运行进程时返回-1
    return -1;
}

修正说明 #

• 轮转调度实现：利用ps->curr字段记录上一次调度的进程索引，下次从该索引的下一个位置开始遍历，通过取模操作实现环形遍历，保证所有RUNNABLE进程都能被公平调度。
• 状态处理逻辑简化：先统一将当前运行的进程转为RUNNABLE，再寻找下一个可运行进程，避免原代码中状态切换的逻辑混乱。
• 消除越界风险：移除了访问数组边界外的逻辑，所有数组访问都通过取模控制在合法范围内。

额外建议 #

• 确认childern数组的含义：从注释看该数组存储的是进程PID，若实际是进程索引对应关系，需调整返回值为idx而非ps->childern[idx]。
• 进程添加逻辑需保证新进程的状态被正确设置为RUNNABLE，且ps->curr字段初始化为合理值（如-1或第一个进程的索引）。

内容的提问来源于stack exchange，提问作者user20384189