联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codehelp

您当前位置:首页 >> Python程序Python程序

日期:2020-05-05 10:56

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.

版权所有:留学生编程辅导网 2021,All Rights Reserved 联系方式:QQ:99515681 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。