Changing the Priority Queue of Minix3

Question

I installed minix3 on a virtual machine and was hoping I could manipulate the current queue selection algorithm so that I could change it from a priority order to a priority order that includes a random assortment of lower priority jobs. I was able to find that the section of code I needed to change was in proc.c with the specific section being pick_proc.c.

/*===========================================================================*
 *                pick_proc                     * 
 *===========================================================================*/
PRIVATE struct proc * pick_proc(void)
{
    /* Decide who to run now.  A new process is selected and returned.
     * When a billable process is selected, record it in 'bill_ptr', so that the 
     * clock task can tell who to bill for system time.
     */
    register struct proc *rp;  /* process to run */
    int q;                     /* iterate over queues */

    /* Check each of the scheduling queues for ready processes. The number of
     * queues is defined in proc.h, and priorities are set in the task table.
     * The lowest queue contains IDLE, which is always ready.
     */
    for (q=0; q < NR_SCHED_QUEUES; q++) {    
        if(!(rp = rdy_head[q])) {
            TRACE(VF_PICKPROC, printf("queue %d empty\n", q););
            continue;
        }

        u64_t timecount;
        u32_t randdom;
        read_tsc_64(&timecount);
        rand = timecount.lo;

        #if DEBUG_RACE
        rp = random_process(rdy_head[q]);
        #endif

        TRACE(VF_PICKPROC, printf("found %s / %d on queue %d\n", 
              rp->p_name, rp->p_endpoint, q););
        assert(proc_is_runnable(rp));
        if (priv(rp)->s_flags & BILLABLE)         
            bill_ptr = rp;        /* bill for system time */
        return rp;
    } 
    return NULL;
}

I already put some code to start the randomization process but I don't know where to go from here. I know I need to add something to this file but I'm not sure which variables do what and which pointers I need to change. I was hoping someone could show me how to do this or point out which part I need to change to help me move along. Right now I'm pretty stuck.

Answer 1

Feels like a delicate question; changing the algorithm could leave high priority tasks unfulfilled. Q1: what is a "lower priority task"? Is that NR_SCHED_QUEUES/2? Q2: how many higher priority tasks must at most be waiting before you are willing to prefer a lower priority task? With this answered, you can change q=0 in the for loop to e.g. q=low_tasks and select a process from there.

for (p=0, q=0; q < NR_SCHED_QUEUES/2; q++)
    p += rdy_tail[q] - rdy_head[q]; // number of processes in this queue
if (p<some_value) q= NR_SCHED_QUEUES / 2; else q= 0;

for (; q < NR_SCHED_QUEUES; q++) {    
    if(!(rp = rdy_head[q])) {
        TRACE(VF_PICKPROC, printf("queue %d empty\n", q););
        continue;
    }

    TRACE(VF_PICKPROC, printf("found %s / %d on queue %d\n", 
          rp->p_name, rp->p_endpoint, q););
    assert(proc_is_runnable(rp));
    if (priv(rp)->s_flags & BILLABLE)         
        bill_ptr = rp;        /* bill for system time */
    return rp;
} 
return NULL;

Note: this is demo only and not guaranteed to work properly!

Note: you must also check there are lower priority tasks to run.