T202410246994709-106

struct proc {
  ...
  uint64 created_time;   // 进程创建时间
  uint64 finish_time;    // 进程结束时间
  uint64 running_time;   // 进程处于RUNNING状态的总时间
  uint64 runable_time;   // 进程处于RUNNABLE状态的总时间
  uint64 sleep_time;     // 进程处于SLEEPING状态的总时间
  uint64 start;          // 当前状态开始时间戳(ticks)
  uint64 end;            // 当前状态结束时间戳(ticks)
  ...
};
make qemu
stat 5
$ stat 5
PID: 4 | Runnable Time: 36 ticks | Running Time: 49 ticks | Sleep Time: 12 ticks
PID: 7 | Runnable Time: 39 ticks | Running Time: 61 ticks | Sleep Time: 12 ticks
PID: 5 | Runnable Time: 37 ticks | Running Time: 63 ticks | Sleep Time: 12 ticks
PID: 6 | Runnable Time: 44 ticks | Running Time: 60 ticks | Sleep Time: 12 ticks
PID: 8 | Runnable Time: 44 ticks | Running Time: 60 ticks | Sleep Time: 12 ticks
Average Turnaround Time: 110 ticks
// #define RR
#define PR
struct proc {
  ...
  int priority;  // 进程的静态优先级 [0..3]
};
p->priority = 2; // Default priority
#elif defined(PR)
struct proc *max_p = 0;
int max_priority = 4; // 高于最大优先级范围的初始值

// 遍历所有进程，寻找优先级最高的RUNNABLE进程
for(p = proc; p < &proc[NPROC]; p++){
  acquire(&p->lock);
  if(p->state == RUNNABLE && p->priority < max_priority){
    max_priority = p->priority;
    max_p = p;
  }
  release(&p->lock);
}

// 如果找到最高优先级的RUNNABLE进程，则进行调度
if (max_p != 0){
  acquire(&max_p->lock);
  // 进程状态更新、上下文切换与运行
  // 参考RR调度的上下文切换逻辑
  on_state_change(RUNNABLE, RUNNING, max_p);
  max_p->state = RUNNING;
  c->proc = max_p;
  swtch(&c->context, &max_p->context);
  c->proc = 0; // 进程运行结束后返回
  release(&max_p->lock);
}
#endif
$ priostat 5
$ priostat 5
Set priority 0 to PID 4
Set priority 1 to PID 5
Set priority 2 to PID 6
Set priority 3 to PID 7
Set priority 0 to PID 8
PID: 4 | Runnable Time: 9 ticks | Running Time: 48 ticks | Sleep Time: 12 ticks
PID: 8 | Runnable Time: 7 ticks | Running Time: 52 ticks | Sleep Time: 12 ticks
PID: 5 | Runnable Time: 25 ticks | Running Time: 57 ticks | Sleep Time: 12 ticks
PID: 6 | Runnable Time: 60 ticks | Running Time: 59 ticks | Sleep Time: 12 ticks
PID: 7 | Runnable Time: 95 ticks | Running Time: 51 ticks | Sleep Time: 12 ticks
Average Turnaround Time: 104 ticks
// proc.h

// 切换调度策略
// #define RR
// #define PR
#define MLFQ

#define NQUEUE 4             // 四个队列
#define TSLICE_Q0 4          // 队列0的时间片长度
#define TSLICE_Q1 8          // 队列1的时间片长度
#define TSLICE_Q2 16         // 队列2的时间片长度
#define TSLICE_Q3 32         // 队列3的时间片长度

struct proc {
  ...
  int queue_level;           // 当前队列级别 [0..NQUEUE-1]
  int time_slice_used;       // 当前队列中已使用的时间片数
  ...
};

struct runqueue {
  struct proc *procs[NPROC];
  int head;
  int tail;
};

extern struct runqueue mlfq_queue[NQUEUE];
// proc.c
struct runqueue mlfq_queue[NQUEUE];

static void init_mlfq_queues() {
  for (int i = 0; i < NQUEUE; i++) {
    mlfq_queue[i].head = 0;
    mlfq_queue[i].tail = 0;
  }
}

static int push_to_queue(int level, struct proc *p) {
  struct runqueue *q = &mlfq_queue[level];
  int next = (q->tail + 1) % NPROC;
  if (next == q->head) {
    // 队列已满，理论上不常发生
    return -1;
  }
  q->procs[q->tail] = p;
  q->tail = next;
  return 0;
}

static struct proc* pop_from_queue(int level) {
  struct runqueue *q = &mlfq_queue[level];
  if (q->head == q->tail) {
    // 队列为空
    return 0;
  }
  struct proc *p = q->procs[q->head];
  q->head = (q->head + 1) % NPROC;
  return p;
}

static int get_timeslice(int level) {
  switch(level) {
    case 0: return TSLICE_Q0;
    case 1: return TSLICE_Q1;
    case 2: return TSLICE_Q2;
    default: return TSLICE_Q3;
  }
}
// 在allocproc成功创建后
p->queue_level = 0;
p->time_slice_used = 0;
push_to_queue(p->queue_level, p);
// wakeup中，当进程变为RUNNABLE时
p->state = RUNNABLE;
push_to_queue(p->queue_level, p);
on_state_change(SLEEPING, RUNNABLE, p);

// yield中，当进程从RUNNING转回RUNNABLE时
p->state = RUNNABLE;
p->time_slice_used = 0;
push_to_queue(p->queue_level, p);
on_state_change(RUNNING, RUNNABLE, p);
// scheduler中
#elif defined(MLFQ)
for (int level = 0; level < NQUEUE; level++) {
  acquire(&plist_lock);
  struct proc *p = pop_from_queue(level);
  if (p) {
    acquire(&p->lock);
    if (p->state == RUNNABLE) {
      on_state_change(RUNNABLE, RUNNING, p);
      p->state = RUNNING;
      c->proc = p;
      p->time_slice_used = 0;
      release(&plist_lock);

      swtch(&c->context, &p->context);
      // 返回后进程可能已切换状态
      c->proc = 0;
      release(&p->lock);
      break;
    } else {
      // 状态不对则放回队列
      push_to_queue(p->queue_level, p);
      release(&p->lock);
    }
    release(&plist_lock);
  } else {
    release(&plist_lock);
    // 当前队列为空，检查下一个队列
  }
}
// trap.c usertrap函数中
if (which_dev == 2) { // timer interrupt
  struct proc *p = myproc();
  if (p && p->state == RUNNING) {
    p->time_slice_used++;
    if (p->time_slice_used >= get_timeslice(p->queue_level)) {
      // 用尽当前队列的时间片，降级队列（若可），并yield
      if (p->queue_level < NQUEUE - 1)
        p->queue_level++;
      yield();
    }
  }
  lapiceoi();
}
static void mlfq_rebalance() {
  for (struct proc *p = proc; p < &proc[NPROC]; p++) {
    acquire(&p->lock);
    if (p->state == RUNNABLE) {
      // 简单策略：若长期未调度，上调其优先级等级
      // p->queue_level = max(p->queue_level - 1, 0);
    }
    release(&p->lock);
  }
}
$ cpucalc &
$ cpucalc &
$ iotask &
$ iotask &