Operating Systems scheduler

this is a class room assignment. deadline is 10/21/04 PART ONE Implement a multi-level feedback Q scheduler satisfying the following requirements: • The scheduler consists of 4 linear Q's. • The first Q is FIFO, second Q is priority-based, third Q is SJF and the fourth (highest Priority) is round robin. • Feedback occurs through aging, aging parameters differ, i.e., each Q has a different aging threshold (time) before a process can migrate to a higher priority Q. (should be a variable parameter for each Q). • The time slot for the Round Robin Q is a variable parameter. • Implement a switch (variable parameter) to allow choosing pre-emptive or non pre-emptive scheduling in the SJF, and priority-based Q's. • Jobs cannot execute in a Q unless there are no jobs in all higher priority Q's. • The jobs are to be created with the following fields in their PCB: Job number, arrival time, actual execution time, priority, Queue number (process type 1 - 4). The creation is done randomly; choose your own ranges for the different fields in the PCB definition. • Output should indicate a time line, i.e., every time step, indicate which processes are created (if any), which ones are completed (if any), processes which aged in different Q's, etc. • You should allow a variable context switching time to be specified by the user. PART TWO Very Important: After completing the implementation and doing a few sample runs, start thinking of this problem as a multivariable optimization problem. From an algorithmic design point of view, you can think of this problem as a problem that involves the following parameters: • Context Switching Time. • Three Aging Parameters. • Time slot. • Two switches for Preemption/Non-preemption. The eventual goal could be to optimize several (or some) performance measures (criteria) such as: • Average waiting time. • Average turnaround time. • CPU utilization. • Maximum turnaround time. • Maximum wait time. • CPU Throughput. Perform several test runs and write a summation indicating how sensitive are some of the performance measures to some of the above parameters (or a combination of the above parameters). Include some of the results (time lines and/or graphs) with your observations and conclusions regarding the effect of changing the values of different parameters on the performance measures. PART THREE: Implement the above but have the process mix (the PCB's) created dynamically, i.e., jobs keep on arriving while the scheduler is running. i.e., create jobs at run time, use a randomizer to decide whether to generate a job (and its PCB) or not every time step, you can vary the probability of generating a job by playing around with your randomizer threshold (e.g., (rand leq 0.2) implies generate job with 0.2 probability, etc.) PART FOUR (Required from graduate students) and Bonus Question (for undergraduate students): • Don't use the actual execution time to do ordering and scheduling in the SJF Q, but use instead an estimation formula to estimate the execution time based on previously executed jobs of the same kind (i.e, ones that have arrived in the same initial Q) • Implement an © updating scheme (sum of square difference method) for each one of the 4 © estimates. • Study the effect of changing the four estimation Coefficients © (one for each Q), and the initial four estimates for execution time © (one for each Q), on the behavior of the performance measures.