Skip to content
TheChatArchiveThe Chat Archive
GPT 5.1 Codex Max· openaiHugging Face Frontier Reasoning Traces

Write a process scheduler for a custom OS using a multilevel feedback queue. New…

  1. User

    Write a process scheduler for a custom OS using a multilevel feedback queue. New processes start in the highest priority queue with short time slices and get demoted if they use their full slice without blocking. Add priority boosting every N seconds to prevent starvation.

  2. Assistant

    Outlining multilevel feedback queue scheduler

    The plan details a C-like pseudocode design for an MLFQ with multiple priority queues, time slices doubling per level, and periodic priority boosting to prevent starvation. It covers process struct, ready queues, scheduling logic on timer ticks, demotion on full quantum, and preserving priority on blocking. The next step is producing clean, commented code illustrating this design. Below is a skeletal preemptive scheduler implementing a multilevel feedback queue (MLFQ) with demotion on full quantum consumption and periodic priority boosting. It assumes a hardware timer that fires at HZ ticks per second and a simple ready–queue abstraction for each priority level:

    #include <stdint.h>
    #include <stddef.h>
    
    #define NUM_QUEUES   4             /* 0 = highest priority, NUM_QUEUES-1 = lowest */
    #define HZ           1000          /* timer ticks per second */
    #define BOOST_SEC    10            /* boost every N seconds */
    #define BOOST_TICKS  (BOOST_SEC*HZ)
    
    /* Time quantum (in ticks) per level: shorter at higher priorities */
    static const uint32_t quantum[NUM_QUEUES] = { 4, 8, 16, 32 };
    
    typedef enum { PROC_READY, PROC_RUNNING, PROC_BLOCKED } proc_state_t;
    
    struct proc {
        int             pid;
        int             prio;           /* 0..NUM_QUEUES-1 */
        uint32_t        remaining;      /* ticks left in this time slice */
        proc_state_t    state;
        /* … CPU context, address space pointer, etc … */
        struct proc    *next;           /* linked list pointer for queues */
    };
    
    /* Simple FIFO ready queues for each priority */
    struct queue {
        struct proc *head;
        struct proc *tail;
    };
    
    static struct queue readyq[NUM_QUEUES];
    static struct proc *current = NULL;
    static uint64_t     tick_count = 0;
    
    /* Queue helpers */
    static void enqueue(struct queue *q, struct proc *p) {
        p->next = NULL;
        if (q->tail) {
            q->tail->next = p;
            q->tail = p;
        } else {
            q->head = q->tail = p;
        }
    }
    
    static struct proc *dequeue(struct queue *q) {
        struct proc *p = q->head;
        if (p) {
            q->head = p->next;
            if (q->head == NULL) q->tail = NULL;
            p->next = NULL;
        }
        return p;
    }
    
    /* Add a new process: put it at highest priority with full quantum */
    void add_new_process(struct proc *p) {
        p->prio      = 0; /* highest queue */
        p->remaining = quantum[p->prio];
        p->state     = PROC_READY;
        enqueue(&readyq[p->prio], p);
    }
    
    /* Called when a blocked process becomes ready again */
    void unblock_process(struct proc *p) {
        p->state     = PROC_READY;
        /* Return to same priority it had when it blocked */
        p->remaining = quantum[p->prio];
        enqueue(&readyq[p->prio], p);
    }
    
    /* Periodic priority boosting to prevent starvation */
    static void priority_boost(void) {
        for (int lvl = 1; lvl < NUM_QUEUES; ++lvl) {
            struct proc *p;
            while ((p = dequeue(&readyq[lvl])) != NULL) {
                p->prio      = 0;
                p->remaining = quantum[0];
                enqueue(&readyq[0], p);
            }
        }
        /* You may also want to boost blocked processes when they wake up */
    }
    
    /* Pick the next runnable process from the highest nonempty queue */
    static struct proc *pick_next(void) {
        for (int lvl = 0; lvl < NUM_QUEUES; ++lvl) {
            if (readyq[lvl].head) {
                struct proc *p = dequeue(&readyq[lvl]);
                p->state = PROC_RUNNING;
                if (p->remaining == 0) {
                    p->remaining = quantum[p->prio];
                }
                return p;
            }
        }
        return NULL; /* idle */
    }
    
    /* Main scheduler entry: choose next and context switch */
    void schedule(void) {
        struct proc *next = pick_next();
        if (next == NULL) {
            /* switch to idle thread */
            return;
        }
    
        struct proc *prev = current;
        current = next;
    
        /* perform low-level context switch from prev to current */
        // context_switch(prev, current);
    }
    
    /* Timer interrupt handler: called every tick (1/HZ seconds) */
    void timer_interrupt(void) {
        tick_count++;
    
        if (tick_count % BOOST_TICKS == 0) {
            priority_boost();
        }
    
        if (current && current->state == PROC_RUNNING) {
            if (current->remaining > 0) {
                current->remaining--;
            }
    
            if (current->remaining == 0) {
                /* Used full slice, demote if not already at lowest */
                if (current->prio < NUM_QUEUES - 1) {
                    current->prio++;
                }
                current->state     = PROC_READY;
                current->remaining = quantum[current->prio];
                enqueue(&readyq[current->prio], current);
                current = NULL;
                schedule();
                return;
            }
        }
    
        /* Preempt if a higher-priority process arrived */
        for (int lvl = 0; lvl < (current ? current->prio : NUM_QUEUES); ++lvl) {
            if (readyq[lvl].head) {
                /* preempt current and reschedule */
                if (current && current->state == PROC_RUNNING) {
                    current->state = PROC_READY;
                    enqueue(&readyq[current->prio], current);
                }
                current = NULL;
                schedule();
                break;
            }
        }
    }
    
    /* Called by a running process to voluntarily yield */
    void yield_cpu(void) {
        if (current && current->state == PROC_RUNNING) {
            current->state = PROC_READY;
            /* It did not consume full quantum; keep same priority */
            enqueue(&readyq[current->prio], current);
            current = NULL;
            schedule();
        }
    }
    
    /* Called when a running process blocks for I/O etc. */
    void block_current(void) {
        if (current) {
            current->state = PROC_BLOCKED;
            /* remaining quantum is discarded; will be reset on unblock */
            current = NULL;
            schedule();
        }
    }
    

    Key points:

    • quantum[] controls the time slice per level; you can tune it to grow with lower priorities.
    • New processes start at level 0. If they exhaust their slice without blocking or yielding, they are demoted (prio++) and given the next level's longer quantum.
    • If a process blocks or yields before using its entire quantum, it stays at the same priority.
    • Every BOOST_SEC seconds (BOOST_TICKS ticks), priority_boost() moves all ready processes back to the top queue to avoid starvation.
    • The timer interrupt decrements the current process' quantum, demotes on exhaustion, and also checks whether a higher-priority runnable process should preempt the current one.

    This skeleton omits low‑level context switching and locking; in a real kernel you would need to protect queue operations with interrupts disabled or a scheduler lock, and save/restore CPU context in context_switch.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.