Description
Consider the following specification of three periodic tasks:
Period CPU time / Period
Task 1 T seconds 1 seconds
Task 2 5 seconds 1 second
Task 3 7 seconds 2 seconds
What is the minimum value of T that would result in a schedulable system using Rate Monotonic Scheduling?
Show the first 21 seconds of execution of the system above using the value of T that you obtained in part (a) above. Assume that all tasks are started at time 0 and that RMS scheduling is used.
What is the minimum value of T that would result in a schedulable system using Earliest Deadline First?
Show the first 21 seconds of execution of the system above using the value of T that you obtained in part (c) above. Assume that all tasks are started at time 0 and that EDF scheduling is used.
A web server has a caching subsystem that holds a set of files out of all the files in the system. Each file in the file system has a unique ID (e.g., filename). Requests served from the cache take much less time than those served from the disk. Thus, in an attempt to speed up its operation, the web server uses the following scheduler for HTTP requests:
When a request for a file fi is received, if fi is in the cache, then the request is put in Q1, otherwise it is put in Q2.
When the server is available to process a request: If Q1 is not empty, then the server picks the next request from Q1, otherwise the server picks a request fj from Q2, where fj is the smallest ID of all requests larger than the maximum ID of any file in the cache.
When a file fj is retrieved from disk (in response to a request de-queued from Q2), then fj is cached by replacing the file fk with the minimum ID amongst all files in the cache.
Answer the following questions:
Show that starvation is possible in the above system… Specifically, describe a particular scenario under which starvation is possible.
To minimize the impact of starvation, a friend of yours suggested that the following initial step be incorporated at the beginning of the above solution:
Requests to the web server are batched up in groups of up to N requests. A batch is processed by going through steps (i), (ii) and (iii) for all requests in the batch. Once all requests in a batch are processed, a new batch is considered, etc.
What kind of disk scheduling algorithm was your friend thinking of when he suggested the above fix?
Discuss the effect of N on the effectiveness of the cache (i.e., is a large N better for improving the cache performance or is a small N better?)
Discuss the effect of N on the fairness of the above system (i.e., is a large N better for improving fairness or is a small N better for fairness?)
Requests for disk I/O arrive according to a Poisson process with rate Lambda (requests per second). Each request for disk access targets a specific track. Requests for tracks are uniformly distributed over the set of N tracks in the disk. The service time Ts for a request to track x is given by:
Ts = U + V * | y – x |
where y is the location of the disk head prior to serving the request, and where U and V are constants.
You are to write a simulator to compare the performance of the RANDOM, FCFS and SCAN disk schedulers when used to manage the above disk. Your simulator should evaluate the performance of all three schedulers when subjected to a workload of 10,000 requests.
Hint: Think about what constitutes the state of the disk. Also, for each request in the queue you should specify a track number from [1,N] (generated uniformly at random). Now, upon a death event, if the queue is not empty, the scheduler would select one of the requests according to what the scheduling algorithm implies.
For each scheduler, you need to calculate the following:
The total head movement
The average response time
The 95th percentile of the response time
Use the following parameters:
Lambda = 50 requests per second
N = 500 tracks
U = 2 msec
V = 0.1 msec/track
What did you expect the results to show? Did they match your expectations?