algorithms代做、program代写、代做Java/Python，c/c++编程语言

日期：2020-05-04 11:07

Project 1

Due: April 7

th, 11:59 pm

Option 1:

11.2 Batch scheduling algorithms

Project objective

Study the impact of different scheduling algorithms on the average turnaround time of

concurrent processes.

Description

A simulation mimics the execution of n different processes under different scheduling

algorithms. The simulation maintains a table that reflects the current state of the

system:

The table is initialized as follows:

? The field "active" indicates whether the process is currently competing for the

CPU. The value becomes 1 at the time of process arrival and 0 at the time of

process termination. Initially, the value is set to 1 for all processes with arrival

time A? = 0.

? Each A? is an integer chosen randomly from a uniform distribution between 0

and some value k, where k is a simulation parameter.

? Each T? is an integer chosen randomly from a normal (Gaussian) distribution

with an average d and a standard deviation v, where d and v are simulation

parameters.

? Each R? is initialized to T?, since prior to execution, the remaining time is equal

to the total CPU time required.

The simulation maintains the current time, t, which is initialized to 0 and is

incremented after each simulation step. Each simulation step then consists of the

following actions:

Assignment

? Implement the above simulation for the 3 scheduling algorithms, FIFO, SJF,

SRT.

? Assume a value for k, which is the time interval during which processes may

arrive. Ex: k = 1000.

? Using a random number generator, derive n arrival times, A?, for all processes,

distributed uniformly within the interval [0 : k].

? Choose an average total CPU time, d, and a standard deviation, v, and derive n

total CPU times, T?, using a normal (Gaussian) distribution.

? Repeat the simulation for different values of d and v. (For simplicity, v could

be just be a fixed percentage of d.)

? The values d and v should be selected relative to k. The value k/n represents the

frequency of process arrivals. When d is much smaller than k/n, then most

processes run in isolation, without having to compete with other processes for

the CPU. As a result, all scheduling algorithms should produce similar results.

On the other hand, when d is much larger than k/n, then many processes will

overlap in time and compete for the CPU. Consequently, different scheduling

algorithms should yield different results.

? To compare the different algorithms, plot the values d/ATT over d. The value

d/ATT shows how competition for CPU slows down the processes. The smaller

the value, the worse the overall performance. The ideal case is d/ATT = 1,

which indicates that all processes ran without any delays.

Option 2:

11.1 Two versions of the process creation

hierarchy

Project objective

Compare the performance of process creation and destruction when implemented with

and without linked lists.

Description

Version 1 of the process creation hierarchy uses linked lists to keep track of child

processes as described in section "The process control block", subsection "The PCB

data structure".

For the purposes of performance evaluation, the PCBs are simplified as follows:

? All PCBs are implemented as an array of size n.

? Each process is referred to by the PCB index, 0 through n-1.

? Each PCB is a structure consisting of only the two fields:

o parent: a PCB index corresponding to the process's creator

o children: a pointer to a linked list, where each list element contains the

PCB index of one child process

The necessary functions are simplified as follows:

? create(p) represents the create function executed by process PCB[p]. The

function creates a new child process PCB[q] of process PCB[p] by performing

the following tasks:

o allocate a free PCB[q]

o record the parent's index, p, in PCB[q]

o initialize the list of children of PCB[q] as empty

o create a new link containing the child's index q and appends the link to

the linked list of PCB[p]

? destroy(p) represents the destroy function executed by process PCB[p]. The

function recursively destroys all descendent processes (child, grandchild, etc.)

of process PCB[p] by performing the following tasks:

o for each element q on the linked list of children of PCB[p]

? destroy(q) /* recursively destroy all progenies */

? free PCB[q]

? deallocate the element q from the linked list

Version 2 of the same process creation hierarchy uses no linked lists. Instead, each

PCB contains the 4 integer fields parent, first_child, younger_sibling, and

older_sibling, as described in the subsection "Avoiding linked lists".

Assignment

1. Implement the two versions of the process creation hierarchy.

2. Assume that PCB[0] is the only currently existing process and write a test

program that performs a series of process creations and destructions. Ex:

3. Run the test program repeatedly in a long loop using both versions and

compare the running times to see how much time is saved in version 2, which

avoids dynamic memory management.