/* The following code implements a priority queue as a heap. Each node of the heap has an identifier (id) as well as a priority. insertIntoHeap() is used to add a node to the heap. extractFromHeap() is used to extract the node with the highest priority from the heap and return its identifier. whoIsOnTopOfHeap() simply returns the identifier of this node, without affecting the heap. deleteFromHeap() is used to remove an arbitrary node from the heap. (See further comments for each individual function.) The variable "heapsize" is the number of nodes in the heap at any given moment. getPriority() can be used to check the priority of a node, and setPriority() can be used to change the priority, which will cause the heap to be reconfigured. Also, a "wait counter" has been added to each node. This counts the number of nodes that have been removed from the queue since the given node was inserted. The function getWaitCounter() can be used to obtain this value. The function bumpAllPriorities() can be used to change all priorities by a certain amount. These four utility functions (or a subset of them) can be used to implement a dynamic priority policy to avoid starvation. */ /* Should below main() function (which is just test code) be included? */ #define INCLUDE_TEST_CODE /* Should heapsize be defined here (or is it defined elsewhere)? */ #define HEAPSIZE_DEFINED_LOCALLY /* Are we compiling as part of the Minix kernel? */ /* #define USING_IN_MINIX */ /* If so, should node identifiers really be pointers to proc structures? */ /* In this case, "id" is misleading since it suggests an integer */ /* #define PTR_TO_PROC_MODE */ /* Are we debugging in a stand alone environment? */ #define DEBUG_OUTSIDE_MINIX /* Are we debugging as part of the Minix kernel? */ /* #define DEBUG_INSIDE_MINIX */ /* If more than one process has the highest priority and if the constant TRY_TO_BE_FAIR_WHEN_EQUAL_PRIORITIES is defined, then it will "try" to extract the one added first to the heap. */ /* #define TRY_TO_BE_FAIR_WHEN_EQUAL_PRIORITIES */ /* How big can the heap get? */ #define MAX_NODES 1000 /* Now begin generating code for the heap. */ #ifdef INCLUDE_TEST_CODE #include #endif #ifdef HEAPSIZE_DEFINED_LOCALLY int heapsize = 0; #endif /* Corresponding triples of entries from the following three arrays constitute a single entry ("node") in a priority queue, implemented as a heap. */ #ifdef PTR_TO_PROC_MODE struct proc *id_array[MAX_NODES]; #else int id_array[MAX_NODES]; #endif int priority_array[MAX_NODES]; int wait_counter_array[MAX_NODES]; #ifdef USING_IN_MINIX /* Given pointer to proc structure, returns offset index to it in the proc array. SHould be same as "nr" but I don't trust. */ #ifdef PTR_TO_PROC_MODE int proc_index(p) struct proc *p; { int i; if (p == NIL_PROC) { #ifdef DEBUG_INSIDE_MINIX kprintf("!"); #endif return -1; } for (i = 0; i < NR_PROCS; i++) if (p == pproc_addr[NR_TASKS+i]) { #ifdef DEBUG_INSIDE_MINIX /* should never print these */ if (i != p->p_nr) kprintf("@"); if (proc_addr(i) != p) kprintf("&"); #endif return i; } #ifdef DEBUG_INSIDE_MINIX kprintf("?"); #endif return -1; } #endif /* PTR_TO_PROC_MODE */ #endif /* USING_IN_MINIX */ #ifndef USING_IN_MINIX #ifdef DEBUG_OUTSIDE_MINIX /* Display heap (for debugging outside Minix) */ void showHeap(char c) { int i; printf("%c ",c); for (i=0; i < heapsize; i++) printf("%d ", id_array[i]); printf("\n "); for (i=0; i < heapsize; i++) printf("%d ", priority_array[i]); printf("\n"); } #endif #endif /* Switch two nodes in the heap */ void swapInHeap(i, j) int i; int j; { #ifdef PTR_TO_PROC_MODE struct proc *temp1; #else int temp1; #endif int temp2; temp1 = id_array[i]; id_array[i] = id_array[j]; id_array[j] = temp1; temp2 = priority_array[i]; priority_array[i] = priority_array[j]; priority_array[j] = temp2; temp2 = wait_counter_array[i]; wait_counter_array[i] = wait_counter_array[j]; wait_counter_array[j] = temp2; } /* Heapify from the bottom up */ void heapifyUp() { int n, parent; n = heapsize - 1; while (n > 0) { parent = (n-1)/2; if (priority_array[parent] >= priority_array[n]) break; #ifdef TRY_TO_BE_FAIR_WHEN_EQUAL_PRIORITIES if (parent % 2 == 1 && priority_array[parent] == priority_array[parent+1]) swapInHeap(parent,parent+1); #endif swapInHeap(n,parent); #ifdef TRY_TO_BE_FAIR_WHEN_EQUAL_PRIORITIES if (parent % 2 == 1 && priority_array[parent] == priority_array[parent+1]) swapInHeap(parent,parent+1); #endif n = parent; #ifdef DEBUG_OUTSIDE_MINIX showHeap('.'); #endif } } /* Add a node to the heap if room for it. */ /* Return -1 if not. */ int insertIntoHeap(id, priority) #ifdef PTR_TO_PROC_MODE struct proc *id; #else int id; #endif int priority; { if (heapsize >= MAX_NODES) return -1; id_array[heapsize] = id; priority_array[heapsize] = priority; wait_counter_array[heapsize++] = 0; heapifyUp(); #ifdef DEBUG_INSIDE_MINIX kprintf("(+ %d %d)", heapsize, proc_index(id)); #endif #ifdef DEBUG_OUTSIDE_MINIX showHeap('^'); #endif return 0; } /* Recursively heapify downwards from index n */ void heapifyDown(n) int n; { int left, right, bigger; bigger = left = 2*n + 1; right = 2*n + 2; if (left >= heapsize) return; else if (right < heapsize && priority_array[left] < priority_array[right]) bigger = right; if (priority_array[n] < priority_array[bigger]) { swapInHeap(n,bigger); #ifdef TRY_TO_BE_FAIR_WHEN_EQUAL_PRIORITIES if (bigger == right && priority_array[left] == priority_array[right]) swapInHeap(left,right); if (n % 2 == 1 && priority_array[n] == priority_array[n+1]) swapInHeap(n,n+1); #endif #ifdef DEBUG_OUTSIDE_MINIX showHeap('.'); #endif heapifyDown(bigger); } #ifdef DEBUG_OUTSIDE_MINIX showHeap('V'); #endif } /* Return id of node at top of heap (highest priority) or -1 or NIL_PROC if empty. */ #ifdef PTR_TO_PROC_MODE struct proc *whoIsOnTopOfHeap() { if (heapsize > 0) return id_array[0]; else return NIL_PROC; } #else int whoIsOnTopOfHeap() { if (heapsize > 0) return id_array[0]; else return -1; } #endif /* Extract the top node of the heap (highest priority) and return the id for this node. Also, increment all counters. If heap is empty, return -1 or NIL_PROC. */ #ifdef PTR_TO_PROC_MODE struct proc *extractFromTopOfHeap() #else int extractFromTopOfHeap() #endif { int i; #ifdef PTR_TO_PROC_MODE if (heapsize == 0) return NIL_PROC; #else if (heapsize == 0) return -1; #endif for (i=0; i < heapsize; i++) wait_counter_array[i]++; swapInHeap(0,--heapsize); heapifyDown(0); #ifdef DEBUG_INSIDE_MINIX kprintf("(^ %d %d)", heapsize, proc_index([id_array[heapsize])); #endif return id_array[heapsize]; } /* Delete specified node and reheapify. Return -1 if not found. */ int deleteFromHeap(id) #ifdef PTR_TO_PROC_MODE struct proc *id; #else int id; #endif { int i, hold_heapsize; for (i=0; i < heapsize; i++) if (id == id_array[i]) break; if (i == heapsize) return -1; if (i == 0) { swapInHeap(0,--heapsize); heapifyDown(0); } else { swapInHeap(i,--heapsize); hold_heapsize = heapsize; for (heapsize = 2; heapsize <= hold_heapsize; heapsize++) heapifyUp(); heapsize = hold_heapsize; } #ifdef DEBUG_INSIDE_MINIX kprintf("(- %d %d)", heapsize, proc_index(id)); #endif return 0; } /* Return size of heap */ int getHeapsize() { return heapsize; } /* rebuild whole heap from arrays */ void rebuildHeap() { int hold_heapsize; hold_heapsize = heapsize; for (heapsize = 2; heapsize <= hold_heapsize; heapsize++) { heapifyUp(); #ifdef DEBUG_OUTSIDE_MINIX showHeap('^'); #endif } heapsize = hold_heapsize; } /* Find wait count for node with given id. Return -1 if not found. */ int getWaitCount(id) #ifdef PTR_TO_PROC_MODE struct proc *id; #else int id; #endif { int i; for (i=0; i < heapsize; i++) if (id == id_array[i]) return wait_counter_array[i]; return -1; } /* Find priority of node with given id. Return -1 if not found. */ int getPriority(id) #ifdef PTR_TO_PROC_MODE struct proc *id; #else int id; #endif { int i; for (i=0; i < heapsize; i++) if (id == id_array[i]) return priority_array[i]; return -1; } /* Set the priority of a node. Return 0 if successful, else -1. */ int setPriority(id, priority) #ifdef PTR_TO_PROC_MODE struct proc *id; #else int id; #endif int priority; { int i, hold_heapsize; i = 0; while (i < heapsize) { if (id == id_array[i]) { priority_array[i] = priority; rebuildHeap(); return 0; } i++; } return -1; } /* Increase priorities of all nodes by some amount */ void bumpAllPriorities(amount) int amount; { int i; for (i=0; i < heapsize; i++) priority_array[i] += amount; } void promoteIdleNodes(delay, amount) int delay, amount; { int i; for (i=0; i < heapsize; i++) if (wait_counter_array[i] >= delay) { priority_array[i] += amount; } else { wait_counter_array[i]++; } } #ifndef USING_IN_MINIX #ifdef INCLUDE_TEST_CODE void main() { insertIntoHeap(1,13); insertIntoHeap(2,22); insertIntoHeap(3,45); insertIntoHeap(4,81); insertIntoHeap(5,13); insertIntoHeap(6,22); insertIntoHeap(7,13); insertIntoHeap(8,45); insertIntoHeap(9,81); /* insertIntoHeap(1,81); insertIntoHeap(2,45); insertIntoHeap(3,13); insertIntoHeap(4,22); insertIntoHeap(5,13); insertIntoHeap(6,81); insertIntoHeap(7,45); insertIntoHeap(8,22); insertIntoHeap(9,13); */ #ifdef DEBUG_OUTSIDE_MINIX showHeap('*'); #endif setPriority(4,13); setPriority(10,10); #ifdef DEBUG_OUTSIDE_MINIX showHeap('*'); #endif printf("%d\n", extractFromTopOfHeap()); printf("%d\n", extractFromTopOfHeap()); printf("%d\n", extractFromTopOfHeap()); printf("%d\n", extractFromTopOfHeap()); #ifdef DEBUG_OUTSIDE_MINIX printf("Wait count for %d is %d.\n", 7, getWaitCount(7)); printf("Wait count for %d is %d.\n", 10, getWaitCount(10)); #endif printf("%d\n", extractFromTopOfHeap()); printf("%d\n", extractFromTopOfHeap()); printf("%d\n", extractFromTopOfHeap()); printf("%d\n", extractFromTopOfHeap()); printf("%d\n", extractFromTopOfHeap()); printf("%d\n", extractFromTopOfHeap()); printf("\n"); } #endif /* INCLUDE_TEST_CODE */ #endif /* USING_IN_MINIX */