From 872687ddfcc1ef98b49860c587af786834efc49d Mon Sep 17 00:00:00 2001 From: Jorrit Herder Date: Mon, 22 Aug 2005 15:14:11 +0000 Subject: [PATCH] Scheduling updates to the kernel. Sched() function now is single point for policy. Actual policy not yet implemented. PM calculates nice values for processes in boot image. IS debug dumps improved (Shift+F1-F4). --- kernel/clock.c | 8 +-- kernel/glo.h | 1 - kernel/main.c | 3 +- kernel/proc.c | 122 ++++++++++++++++------------------------ kernel/proc.h | 9 +-- kernel/system/do_fork.c | 8 ++- servers/is/dmp.c | 1 + servers/is/dmp_fs.c | 1 + servers/is/dmp_kernel.c | 7 +-- servers/is/dmp_pm.c | 59 +++++++++++++++++-- servers/is/proto.h | 1 + servers/pm/main.c | 21 ++++++- 12 files changed, 140 insertions(+), 101 deletions(-) diff --git a/kernel/clock.c b/kernel/clock.c index fbf2d8430..e5624d2ec 100755 --- a/kernel/clock.c +++ b/kernel/clock.c @@ -118,7 +118,7 @@ message *m_ptr; /* pointer to request message */ * no more time left, it will get a new quantum and inserted at the right * place in the queues. As a side-effect a new process will be scheduled. */ - if (prev_ptr->p_sched_ticks <= 0 && priv(prev_ptr)->s_flags & PREEMPTIBLE) { + if (prev_ptr->p_ticks_left <= 0 && priv(prev_ptr)->s_flags & PREEMPTIBLE) { lock_dequeue(prev_ptr); /* take it off the queues */ lock_enqueue(prev_ptr); /* and reinsert it again */ } @@ -182,17 +182,17 @@ irq_hook_t *hook; */ proc_ptr->p_user_time += ticks; if (priv(proc_ptr)->s_flags & PREEMPTIBLE) { - proc_ptr->p_sched_ticks -= ticks; + proc_ptr->p_ticks_left -= ticks; } if (! (priv(proc_ptr)->s_flags & BILLABLE)) { bill_ptr->p_sys_time += ticks; - bill_ptr->p_sched_ticks -= ticks; + bill_ptr->p_ticks_left -= ticks; } /* Check if do_clocktick() must be called. Done for alarms and scheduling. * Some processes, such as the kernel tasks, cannot be preempted. */ - if ((next_timeout <= realtime) || (proc_ptr->p_sched_ticks <= 0)) { + if ((next_timeout <= realtime) || (proc_ptr->p_ticks_left <= 0)) { prev_ptr = proc_ptr; /* store running process */ lock_notify(HARDWARE, CLOCK); /* send notification */ } diff --git a/kernel/glo.h b/kernel/glo.h index a80b84dc6..71fcf0ebb 100755 --- a/kernel/glo.h +++ b/kernel/glo.h @@ -30,7 +30,6 @@ EXTERN struct proc *proc_ptr; /* pointer to currently running process */ EXTERN struct proc *next_ptr; /* next process to run after restart() */ EXTERN struct proc *bill_ptr; /* process to bill for clock ticks */ EXTERN char k_reenter; /* kernel reentry count (entry count less 1) */ -EXTERN int sched_ticks; /* keep track of quantum usage */ EXTERN unsigned lost_ticks; /* clock ticks counted outside clock task */ diff --git a/kernel/main.c b/kernel/main.c index 8af1329d7..7f8f1d13f 100755 --- a/kernel/main.c +++ b/kernel/main.c @@ -77,8 +77,7 @@ PUBLIC void main() rp->p_max_priority = ip->priority; /* max scheduling priority */ rp->p_priority = ip->priority; /* current priority */ rp->p_quantum_size = ip->quantum; /* quantum size in ticks */ - rp->p_sched_ticks = ip->quantum; /* current credit */ - rp->p_full_quantums = QUANTUMS(ip->priority); /* nr quantums left */ + rp->p_ticks_left = ip->quantum; /* current credit */ strncpy(rp->p_name, ip->proc_name, P_NAME_LEN); /* set process name */ (void) get_priv(rp, (ip->flags & SYS_PROC)); /* assign structure */ priv(rp)->s_flags = ip->flags; /* process flags */ diff --git a/kernel/proc.c b/kernel/proc.c index 618dbb19a..59225177d 100755 --- a/kernel/proc.c +++ b/kernel/proc.c @@ -12,8 +12,8 @@ * lock_dequeue: remove a process from the scheduling queues * * Changes: - * Aug 19, 2005 rewrote multilevel scheduling code (Jorrit N. Herder) - * Jul 25, 2005 protection and checks in sys_call() (Jorrit N. Herder) + * Aug 19, 2005 rewrote scheduling code (Jorrit N. Herder) + * Jul 25, 2005 rewrote system call handling (Jorrit N. Herder) * May 26, 2005 rewrote message passing functions (Jorrit N. Herder) * May 24, 2005 new notification system call (Jorrit N. Herder) * Oct 28, 2004 nonblocking send and receive calls (Jorrit N. Herder) @@ -56,7 +56,6 @@ FORWARD _PROTOTYPE( void enqueue, (struct proc *rp) ); FORWARD _PROTOTYPE( void dequeue, (struct proc *rp) ); FORWARD _PROTOTYPE( void sched, (struct proc *rp, int *queue, int *front) ); FORWARD _PROTOTYPE( void pick_proc, (void) ); -FORWARD _PROTOTYPE( void balance_queues, (struct proc *rp) ); #define BuildMess(m_ptr, src, dst_ptr) \ (m_ptr)->m_source = (src); \ @@ -401,44 +400,28 @@ int dst; /* who is to be notified */ PRIVATE void enqueue(rp) register struct proc *rp; /* this process is now runnable */ { -/* Add 'rp' to one of the queues of runnable processes. We need to decide - * where to put the process based on its quantum. If there is time left, it - * is added to the front of its queue, so that it can immediately run. - * Otherwise its is given a new quantum and added to the rear of the queue. +/* Add 'rp' to one of the queues of runnable processes. This function is + * responsible for inserting a process into one of the scheduling queues. + * The mechanism is implemented here. The actual scheduling policy is + * defined in sched() and pick_proc(). */ - register int q; /* scheduling queue to use */ - int time_left; /* quantum fully used? */ - - /* Check if the process has time left and determine what queue to use. A - * process that consumed a full quantum is given a lower priority, so that - * the CPU-bound processes cannot starve I/O-bound processes. When the - * threshold is reached, the scheduling queues are balanced to prevent all - * processes from ending up in the lowest queue. - */ - time_left = (rp->p_sched_ticks > 0); /* check ticks left */ - if ( ! time_left) { /* quantum consumed ? */ - rp->p_sched_ticks = rp->p_quantum_size; /* give new quantum */ -#if DEAD_CODE - if (proc_nr(rp) != IDLE) { /* already lowest priority */ - rp->p_priority ++; /* lower the priority */ - if (rp->p_priority >= IDLE_Q) /* threshold exceeded */ - balance_queues(rp); /* rebalance queues */ - } -#endif - } - q = rp->p_priority; /* scheduling queue to use */ + int q; /* scheduling queue to use */ + int front; /* add to front or back */ #if DEBUG_SCHED_CHECK check_runqueues("enqueue"); if(rp->p_ready) kprintf("enqueue() already ready process\n"); #endif + /* Determine where to insert to process. */ + sched(rp, &q, &front); + /* Now add the process to the queue. */ if (rdy_head[q] == NIL_PROC) { /* add to empty queue */ rdy_head[q] = rdy_tail[q] = rp; /* create a new queue */ rp->p_nextready = NIL_PROC; /* mark new end */ } - else if (time_left) { /* add to head of queue */ + else if (front) { /* add to head of queue */ rp->p_nextready = rdy_head[q]; /* chain head of queue */ rdy_head[q] = rp; /* set new queue head */ } @@ -447,7 +430,9 @@ register struct proc *rp; /* this process is now runnable */ rdy_tail[q] = rp; /* set new queue tail */ rp->p_nextready = NIL_PROC; /* mark new end */ } - pick_proc(); /* select next to run */ + + /* Now select the next process to run. */ + pick_proc(); #if DEBUG_SCHED_CHECK rp->p_ready = 1; @@ -461,8 +446,10 @@ register struct proc *rp; /* this process is now runnable */ PRIVATE void dequeue(rp) register struct proc *rp; /* this process is no longer runnable */ { -/* A process has blocked. See ready for a description of the queues. */ - +/* A process must be removed from the scheduling queues, for example, because + * it has blocked. If the currently active process is removed, a new process + * is picked to run by calling pick_proc(). + */ register int q = rp->p_priority; /* queue to use */ register struct proc **xpp; /* iterate over queue */ register struct proc *prev_xp; @@ -496,15 +483,6 @@ register struct proc *rp; /* this process is no longer runnable */ prev_xp = *xpp; /* save previous in chain */ } -#if DEAD_CODE - /* The caller blocked. Reset the scheduling priority and quantums allowed. - * The process' priority may have been lowered if a process consumed too - * many full quantums in a row to prevent damage from infinite loops - */ - rp->p_priority = rp->p_max_priority; - rp->p_full_quantums = QUANTUMS(rp->p_priority); -#endif - #if DEBUG_SCHED_CHECK rp->p_ready = 0; check_runqueues("dequeue"); @@ -515,48 +493,42 @@ register struct proc *rp; /* this process is no longer runnable */ /*===========================================================================* * sched * *===========================================================================*/ -PRIVATE void sched(sched_ptr, queue, front) -struct proc *sched_ptr; /* process to be scheduled */ +PRIVATE void sched(rp, queue, front) +register struct proc *rp; /* process to be scheduled */ int *queue; /* return: queue to use */ int *front; /* return: front or back */ { +/* This function determines the scheduling policy. It is called whenever a + * process must be added to one of the scheduling queues to decide where to + * insert it. + */ + int time_left; + int penalty; -} - -/*===========================================================================* - * balance_queues * - *===========================================================================*/ -PRIVATE void balance_queues(pp) -struct proc *pp; /* process that caused this */ -{ -/* To balance the scheduling queues, they will be rebuild whenever a process - * is put in the lowest queues where IDLE resides. All processes get their - * priority raised up to their maximum priority. - */ - register struct proc *rp; - register int q; - int penalty = pp->p_priority - pp->p_max_priority; - - /* First clean up the old scheduling queues. */ - for (q=0; qp_ticks_left > 0); /* check ticks left */ + if ( ! time_left) { /* quantum consumed ? */ + rp->p_ticks_left = rp->p_quantum_size; /* give new quantum */ } - /* Then rebuild the queues, while balancing priorities. Each process that is - * in use may get a higher priority and gets a new quantum. Processes that - * are runnable are added to the scheduling queues, unless it concerns the - * process that caused this function to be called (it will be added after - * returning from this function). + /* Determine the new priority of this process. User and system processes + * are treated different. They can be distinguished because only user + * processes (and IDLE) are billable. */ - for (rp=BEG_PROC_ADDR; rpp_rts_flags & SLOT_FREE)) { /* update in-use slots */ - rp->p_priority = MAX(rp->p_priority - penalty, rp->p_max_priority); - rp->p_sched_ticks = rp->p_quantum_size; - if (rp->p_rts_flags == 0) { /* process is runnable */ - if (rp != pp) enqueue(rp); /* add it to a queue */ - } - } + penalty = 0; + if (priv(rp)->s_flags & BILLABLE) { /* user process */ } + else { /* system process */ + } + rp->p_priority = MIN((rp->p_max_priority + penalty), (IDLE_Q - 1)); + + /* If there is time left, the process is added to the front of its queue, + * so that it can immediately run. The queue to use simply is always the + * process' current priority. + */ + *queue = rp->p_priority; + *front = time_left; } diff --git a/kernel/proc.h b/kernel/proc.h index 12b88583e..5350779f9 100755 --- a/kernel/proc.h +++ b/kernel/proc.h @@ -33,8 +33,9 @@ struct proc { char p_priority; /* current scheduling priority */ char p_max_priority; /* maximum scheduling priority */ char p_quantum_size; /* quantum size in ticks */ - char p_sched_ticks; /* number of scheduling ticks left */ - char p_full_quantums; /* number of full quantums left */ + char p_ticks_left; /* number of scheduling ticks left */ + char p_history; /* scheduling history ageing algorithm */ + short p_block_count; /* times blocked in current quantum */ struct mem_map p_memmap[NR_LOCAL_SEGS]; /* memory map (T, D, S) */ @@ -42,7 +43,6 @@ struct proc { clock_t p_sys_time; /* sys time in ticks */ struct proc *p_nextready; /* pointer to next ready process */ - struct notification *p_ntf_q; /* queue of pending notifications */ struct proc *p_caller_q; /* head of list of procs wishing to send */ struct proc *p_q_link; /* link to next proc wishing to send */ message *p_messbuf; /* pointer to passed message buffer */ @@ -80,9 +80,6 @@ struct proc { #define MIN_USER_Q 14 /* minimum priority for user processes */ #define IDLE_Q 15 /* lowest, only IDLE process goes here */ -/* Each queue has a maximum number of full quantums associated with it. */ -#define QUANTUMS(q) (1 + (NR_SCHED_QUEUES - (q))/2) - /* Magic process table addresses. */ #define BEG_PROC_ADDR (&proc[0]) #define BEG_USER_ADDR (&proc[NR_TASKS]) diff --git a/kernel/system/do_fork.c b/kernel/system/do_fork.c index 6a1ed6a99..a500da249 100644 --- a/kernel/system/do_fork.c +++ b/kernel/system/do_fork.c @@ -51,8 +51,12 @@ register message *m_ptr; /* pointer to request message */ rpc->p_user_time = 0; /* set all the accounting times to 0 */ rpc->p_sys_time = 0; - rpc->p_sched_ticks /= 2; /* parent and child have to share quantum */ - rpp->p_sched_ticks /= 2; + /* Parent and child have to share the quantum that the forked process had, + * so that queued processes do not have to wait longer because of the fork. + * If the time left is odd, the child gets an extra tick. + */ + rpc->p_ticks_left = (rpc->p_ticks_left + 1) / 2; + rpp->p_ticks_left = rpp->p_ticks_left / 2; /* If the parent is a privileged process, take away the privileges from the * child process and inhibit it from running by setting the NO_PRIV flag. diff --git a/servers/is/dmp.c b/servers/is/dmp.c index 866ced590..ffe0e66bd 100644 --- a/servers/is/dmp.c +++ b/servers/is/dmp.c @@ -57,6 +57,7 @@ PUBLIC int do_fkey_pressed(message *m) /* Also check Shift F1-F6 keys. */ if (pressed(SF1)) mproc_dmp(); + if (pressed(SF2)) sigaction_dmp(); if (pressed(SF3)) fproc_dmp(); if (pressed(SF4)) dtab_dmp(); diff --git a/servers/is/dmp_fs.c b/servers/is/dmp_fs.c index 5b132eb5e..12c548020 100644 --- a/servers/is/dmp_fs.c +++ b/servers/is/dmp_fs.c @@ -68,6 +68,7 @@ PUBLIC void dtab_dmp() printf("Major Proc\n"); printf("----- ----\n"); for (i=0; ip_name, rp->p_priority, rp->p_max_priority, - rp->p_sched_ticks, rp->p_quantum_size, - rp->p_full_quantums, + rp->p_ticks_left, rp->p_quantum_size, rp->p_user_time, rp->p_sys_time, click_to_round_k(text), click_to_round_k(data), click_to_round_k(size), diff --git a/servers/is/dmp_pm.c b/servers/is/dmp_pm.c index 938fbf44f..a813a4865 100644 --- a/servers/is/dmp_pm.c +++ b/servers/is/dmp_pm.c @@ -17,6 +17,26 @@ PUBLIC struct mproc mproc[NR_PROCS]; /*===========================================================================* * mproc_dmp * *===========================================================================*/ +PRIVATE char *flags_str(int flags) +{ + static char str[10]; + str[0] = (flags & WAITING) ? 'W' : '-'; + str[1] = (flags & ZOMBIE) ? 'Z' : '-'; + str[2] = (flags & PAUSED) ? 'P' : '-'; + str[3] = (flags & ALARM_ON) ? 'A' : '-'; + str[4] = (flags & TRACED) ? 'T' : '-'; + str[5] = (flags & STOPPED) ? 'S' : '-'; + str[6] = (flags & SIGSUSPENDED) ? 'U' : '-'; + str[7] = (flags & REPLY) ? 'R' : '-'; + str[8] = (flags & ONSWAP) ? 'O' : '-'; + str[9] = (flags & SWAPIN) ? 'I' : '-'; + str[10] = (flags & DONT_SWAP) ? 'D' : '-'; + str[11] = (flags & PRIV_PROC) ? 'P' : '-'; + str[12] = '\0'; + + return str; +} + PUBLIC void mproc_dmp() { struct mproc *mp; @@ -27,7 +47,7 @@ PUBLIC void mproc_dmp() getsysinfo(PM_PROC_NR, SI_PROC_TAB, mproc); - printf("-process- -nr-prnt- -pid/ppid/grp --uid--gid- -flags- --ignore--catch--block--\n"); + printf("-process- -nr-prnt- -pid/ppid/grp- -uid--gid- -nice- -flags------\n"); for (i=prev_i; imp_pid == 0 && i != PM_PROC_NR) continue; @@ -36,10 +56,8 @@ PUBLIC void mproc_dmp() mp->mp_name, i, mp->mp_parent, mp->mp_pid, mproc[mp->mp_parent].mp_pid, mp->mp_procgrp); printf("%d(%d) %d(%d) ", mp->mp_realuid, mp->mp_effuid, mp->mp_realgid, mp->mp_effgid); - printf("0x%04x ", - mp->mp_flags); - printf("0x%05x 0x%05x 0x%05x", - mp->mp_ignore, mp->mp_catch, mp->mp_sigmask); + printf(" %3d %s ", + mp->mp_nice, flags_str(mp->mp_flags)); printf("\n"); } if (i >= NR_PROCS) i = 0; @@ -49,7 +67,36 @@ PUBLIC void mproc_dmp() /*===========================================================================* - * ...._dmp * + * sigaction_dmp * *===========================================================================*/ +PUBLIC void sigaction_dmp() +{ + struct mproc *mp; + int i, n=0; + static int prev_i = 0; + clock_t uptime; + + printf("Process manager (PM) signal action dump\n"); + + getsysinfo(PM_PROC_NR, SI_PROC_TAB, mproc); + getuptime(&uptime); + + printf("-process- -nr- --ignore- --catch- --block- -tomess-- -pending-- -alarm---\n"); + for (i=prev_i; imp_pid == 0 && i != PM_PROC_NR) continue; + if (++n > 22) break; + printf("%8.8s %3d ", mp->mp_name, i); + printf(" 0x%06x 0x%06x 0x%06x 0x%06x ", + mp->mp_ignore, mp->mp_catch, mp->mp_sigmask, mp->mp_sig2mess); + printf("0x%06x ", mp->mp_sigpending); + if (mp->mp_flags & ALARM_ON) printf("%8u", mp->mp_timer.tmr_exp_time-uptime); + else printf(" -"); + printf("\n"); + } + if (i >= NR_PROCS) i = 0; + else printf("--more--\r"); + prev_i = i; +} diff --git a/servers/is/proto.h b/servers/is/proto.h index c79c8ec5c..5299308a6 100644 --- a/servers/is/proto.h +++ b/servers/is/proto.h @@ -21,6 +21,7 @@ _PROTOTYPE( void timing_dmp, (void) ); /* dmp_pm.c */ _PROTOTYPE( void mproc_dmp, (void) ); +_PROTOTYPE( void sigaction_dmp, (void) ); /* dmp_fs.c */ _PROTOTYPE( void dtab_dmp, (void) ); diff --git a/servers/pm/main.c b/servers/pm/main.c index 2634843e7..b56f131af 100644 --- a/servers/pm/main.c +++ b/servers/pm/main.c @@ -16,7 +16,7 @@ #include #include #include -#include +#include #include #include "mproc.h" #include "param.h" @@ -24,9 +24,11 @@ #include "../../kernel/const.h" #include "../../kernel/config.h" #include "../../kernel/type.h" +#include "../../kernel/proc.h" FORWARD _PROTOTYPE( void get_work, (void) ); FORWARD _PROTOTYPE( void pm_init, (void) ); +FORWARD _PROTOTYPE( int get_nice_value, (int queue) ); FORWARD _PROTOTYPE( void get_mem_chunks, (struct memory *mem_chunks) ); FORWARD _PROTOTYPE( void patch_mem_chunks, (struct memory *mem_chunks, struct mem_map *map_ptr) ); @@ -207,6 +209,7 @@ PRIVATE void pm_init() rmp = &mproc[ip->proc_nr]; strncpy(rmp->mp_name, ip->proc_name, PROC_NAME_LEN); rmp->mp_parent = SM_PROC_NR; + rmp->mp_nice = get_nice_value(ip->priority); if (ip->proc_nr == INIT_PROC_NR) { /* user process */ rmp->mp_pid = INIT_PID; rmp->mp_flags |= IN_USE; @@ -267,6 +270,22 @@ PRIVATE void pm_init() printf(" free %u KB.\n", click_to_round_k(free_clicks)); } +/*=========================================================================* + * get_nice_value * + *=========================================================================*/ +PRIVATE int get_nice_value(queue) +int queue; /* store mem chunks here */ +{ +/* Processes in the boot image have a priority assigned. The PM doesn't know + * about priorities, but uses 'nice' values instead. The priority is between + * MIN_USER_Q and MAX_USER_Q. We have to scale between PRIO_MIN and PRIO_MAX. + */ + int nice_val = (queue - USER_Q) * (PRIO_MAX-PRIO_MIN+1) / + (MIN_USER_Q-MAX_USER_Q+1); + if (nice_val > PRIO_MAX) nice_val = PRIO_MAX; /* shouldn't happen */ + if (nice_val < PRIO_MIN) nice_val = PRIO_MIN; /* shouldn't happen */ + return nice_val; +} #if _WORD_SIZE == 2 /* In real mode only 1M can be addressed, and in 16-bit protected we can go -- 2.44.0