PCB实现阶段调度前就绪队列的链表实现及相关技术疑问

1. 为什么就绪队列要使用链表？ #

• 动态适配进程数量：进程的创建和销毁是动态的，链表不需要预先分配固定大小的内存空间，能随实际需求自由添加或移除节点，不会像静态数组那样出现空间浪费或者容量不足的问题。
• 高效完成队列操作：就绪队列核心的入队（加队尾）、出队（取队头）操作，在链表结构下只要维护好队头和队尾指针，就能做到O(1)时间复杂度完成，比数组的O(n)操作效率高得多。
• 适配内存分配场景：链表的节点是分散分配的，不需要连续的大块内存，更符合操作系统中动态内存分配的实际情况，减少内存碎片化的影响。

2. 链表在就绪队列中是如何使用的？ #

结合《Operating System Concepts》中的代码实现，具体用法如下：

1. PCB节点设计：每个PCB结构体自带next指针，用来指向队列中的下一个PCB，以此把多个PCB串联成链表。
2. 就绪队列的管理结构：用ReadyQueue结构体维护链表的队头（first）和队尾（last）指针，让入队和出队操作能快速定位到目标位置。
3. 核心队列操作：
   • 入队：如果队列是空的，直接把新PCB同时设为队头和队尾；如果队列非空，就把当前队尾节点的next指向新PCB，再更新队尾指针。
   • 出队：取出当前队头节点，把队头指针移到下一个节点；如果取出后队列变空了，同步把队尾指针设为NULL。

翻译后的完整代码实现：

// 定义进程控制块（PCB）
typedef struct PCB {
    int pid; // 进程ID
    char state[10]; // 进程状态（例如："就绪"、"运行"等）
    struct PCB* next; // 指向就绪队列中的下一个PCB
} PCB;

// 定义就绪队列结构，包含指向队列首尾PCB的指针
typedef struct ReadyQueue {
    PCB* first; // 指向就绪队列的第一个PCB
    PCB* last;  // 指向就绪队列的最后一个PCB
} ReadyQueue;

// 创建新PCB的函数
PCB* createPCB(int pid, const char* state) {
    PCB* newPCB = (PCB*)malloc(sizeof(PCB)); // 为新PCB分配内存
    newPCB->pid = pid; // 分配进程ID
    snprintf(newPCB->state, sizeof(newPCB->state), "%s", state); // 分配进程状态
    newPCB->next = NULL; // 初始化next指针为NULL
    return newPCB; // 返回新PCB的指针
}

// 初始化就绪队列的函数
ReadyQueue* initializeReadyQueue() {
    ReadyQueue* rq = (ReadyQueue*)malloc(sizeof(ReadyQueue)); // 为就绪队列分配内存
    rq->first = NULL; // 将队头指针设为NULL
    rq->last = NULL;  // 将队尾指针设为NULL
    return rq;
}

// 将PCB添加到就绪队列（队尾）的函数
void enqueue(ReadyQueue* rq, PCB* pcb) {
    if (rq->last == NULL) { // 如果队列为空
        rq->first = pcb; // 队头和队尾都指向新PCB
        rq->last = pcb;
    } else { // 如果队列非空
        rq->last->next = pcb; // 将新PCB链接到队列尾部
        rq->last = pcb; // 更新队尾指针为新PCB
    }
}

// 从就绪队列中移除PCB（队头）的函数
PCB* dequeue(ReadyQueue* rq) {
    if (rq->first == NULL) { // 如果队列为空
        printf("就绪队列为空。\n");
        return NULL;
    }
    
    PCB* temp = rq->first; // 获取队头PCB
    rq->first = rq->first->next; // 将队头指针移到下一个PCB

    if (rq->first == NULL) { // 如果出队后队列为空
        rq->last = NULL; // 将队尾指针设为NULL
    }

    return temp; // 返回出队的PCB
}

3. 栈和队列在此过程中发挥了什么作用？ #

• 队列的作用：就绪队列本身就是基于队列的「先进先出（FIFO）」规则实现的，能保证最早进入就绪状态的进程优先被调度器选中执行，完美适配先来先服务、时间片轮转这类基础调度算法的需求。代码里的入队、出队操作严格遵循FIFO逻辑：新进程从队尾加入，调度器从队头选取下一个执行的进程。
• 栈的作用：每个进程的执行上下文（比如寄存器值、程序计数器、栈指针等）都存在自己的内核栈中。当进程被调度器切换出CPU时，当前的上下文会被压入栈保存；当进程被再次调度执行时，调度器会从栈中恢复之前保存的上下文，让进程能从暂停的位置继续运行。

4. 这对调度器和PCB的执行有何影响？ #

• 对调度器的影响：
  • 调度核心操作效率高：调度器选取下一个执行进程时，通过出队操作能在O(1)时间内拿到队头进程，不需要遍历整个队列，减少了调度的开销。
  • 实现更灵活：链表的动态特性允许调度器随时将从阻塞态转为就绪态的进程加入队列，不用受固定队列容量的限制，适配复杂的进程状态切换场景。
• 对PCB执行的影响：
  • 状态切换更顺畅：进程变为就绪态时能快速入队，被调度执行时能快速出队，状态更新和队列操作的开销极低，不会拖慢进程的执行节奏。
  • 内存利用率更高：链表采用动态内存分配，每个PCB只在需要时才分配内存，避免了固定大小队列带来的内存浪费，提升了系统资源的利用率。

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