is a VecDeque a good idea for the runqueues for a RR scheduler

[RayanMargham]

Code: Select all

struct thread {
...,
next: ptr to next thread,
...
}

struct cpu_data {
...
prempt: bool,
run_queue: ptr to next thread,
cur_thread: ptr to current thread,
...
}

e.g
coming from a timer like the lapic
if (cpu_data.prempt)
  schedule();
else
  return_from_interrupt_frame();

i was thinking of having the scheduler i want to do look like this and use freelists but would a vedeque be a better choice, the clanker seems to agree. its basically a growable ring buffer https://doc.rust-lang.org/std/collectio ... Deque.html ive also forgotten a lot of how context switching works but thats my job to figure out i guess

[Demindiro]

Short answer: no. Use a singly/doubly linked list.

Thread switching is tricky to get right. VecDeque potentially requires resizing the allocation, which may cause trouble. It also won't have any performance benefits, as all operations you'll do will be O(1) anyway (or they should be, for a RR queue).

A singly linked list here requires just a single pointer in the Thread Control Block. If you need to be able to dequeue threads at arbitrary points in the queue (e.g. for high-priority events) you should use a doubly linked list. You can put the TCB directly on the stack, which should be at minimum 4K anyway as you definitely want a stack guard.