COSC 4330 Operating Systems Assignment

Programming Assignment 1 - Deadlock Avoidance and SJF/LLF Scheduling

In this assignment, you will implement a deadlock avoidance algorithm as part of the process manager to avoid deadlocks in a Unix/Linux system. Part of the assignment requires the manipulation of Unix/Linux processes and part of it consists of simulation.

Both the deadlock-handling process and the processes requesting resources are real Unix/Linux processes created using fork(). However, you do not need to actually allocate any resource. The main process executes the Banker’s algorithm. The resource-requesting processes make requests by communicating with the deadlock-handling process with either Unix/Linux pipes or shared memory controlled by semaphores (your choice, but pipes are easier to use).

The deadlock-handling process chooses the next process with the shortest computation time (SJF) to be serviced. After having one request serviced, a process has to allow another process to make a request before making another one, that is, another process with the shortest computation time is chosen for service. Ties are broken arbitrarily. A process can also release resources during its execution, and releases all resources held when it terminates.

Associated with each process is also a relative deadline (that is, the deadline from the current time instant). One time unit is needed for servicing each request (whether the resource is allocated or not), so the relative deadline for each process is decreased by 1 whether it is serviced or not. If the resource is allocated for a request, then the computation time of this process decreases by 1; otherwise, the computation time remains the same. If a process misses its deadline, keep servicing its requests but indicate the deadline miss in the output. A release instruction also needs 1 unit of computation time just like a request. The input format is as follows:

{`
m	/* number of resources */ n	/* number of processes */
available[1] = number of instances of resource 1 : available[m] = number of instances of resource m
max[1,1] = maximum demand for resource 1 by process 1 :
max[n,m] = maximum demand for resource m by process n
process_1:	
deadline_1	/* an integer, must be >= computation time */
computation_time_1
:	/* an integer, equal to number of requests and releases */
request(0,1,0,...,2)
:	/* request vector, m integers */
release(0,1,0,...,1)	/* release vector, m integers */
:	
request(1,0,3,...,1)
: end.
:
process_n:	/* request vector, m integers */
deadline_n	/* an integer */
computation_time_n
:	/* an integer, equal to number of requests and releases */
request(0,2,0,...,2)
:	/* request vector, m integers */
release(0,1,0,...,2)
:	/* release vector, m integers */
request(1,0,3,...,1)
: end.	/* request vector, m integers */
`}

For output, print the state of the system after servicing each request: the arrays available, allocation, need, and deadline misses, if any.

Next, let’s try LLF (least laxity first scheduling) instead of SJF. The deadlock-handling process chooses the next process with the least laxity (slack) to be serviced. Laxity (l) is defined as deadline (d) minus remaining computation time (c) at a specific time (t), that is, l(t) = d(t) - c(t). Which scheduling technique yields fewer deadline misses?

---

COSC 4330-Operating System Fundamentals

Assignment #1: Process Scheduling

Objective

This assignment will introduce you to CPU scheduling.

2. Specifications

You are to simulate the execution of processes by a cheap tablet with a large memory, one display, a dualcore CPU, and one solid-state drive. Each process will be described by its start time followed by a sequence of resource requests.

These resources requests will include CPU requests (CPU), SSD requests (SSD) and input requests

(INPUT). Your input will be a sequence of pairs as in:

NEW 12000 // new process

CPU 100 // request CPU for 100 ms

INPUT 5000 // request INPUT for 5000 ms

CPU 80 // request CPU for 80 ms

SSD 0 // request SSD for 0 ms

CPU 30 // request CPU for 30 ms SSD 1 // request SSD for 1 ms

CPU 20 // request CPU for 20 ms NEW 12040// new process ...

All times will be expressed in milliseconds.

CPU Management: Your program should have a single ready queue. That queue should be a FIFO queue and keep all processes ordered according to their queue arrival time in strict first-come first-served order.

SSD Management: SSD access times are much shorter than disk access times with write requests taking less than a millisecond and read requests taking much less than that. As a result, write request timings will be rounded up to one millisecond and read requests timing will be rounded down to zero ms. SSD scheduling will be strictly first-come first-served (FCFS). To simplify your life, we will also assume that:

1. There is enough memory space for all processes,
2. Context switch times can be neglected, and
3. User think times and other delays, like overlapping windows, are included in the input times.

Program organization: Your program should read its input file name though input redirection as in:

If by accident, two resources allocations need to be made at the same time, you should allocate the CPU first and then the SSD before performing the INPUT request. Your program should have one process table with one entry per process containing a process sequence number, the process class, its process arrival time and its current state

(RUNNING, READY or WAITING).

Each time a process starts or terminates your program should print:

1. the current simulated time in milliseconds,
2. the sequence number of the process that terminates, and the states of all other active processes When all the processes in your input stream have completed, your simulator should print a summary report listing:
3. the number of processes that have completed,
4. the total number of SSD accesses,
5. the average duration of a SSD access (including the waiting time in the SSD queue),
6. the total time elapsed since the start of the first process,
7. the CPU utilization, that is, the average number of busy cores (between zero and two),
8. the SSD utilization, that is, the fraction of time the device was busy (between zero and one). 

3. Important

To get full credit, your program should start by a block of comments containing your name, the course number, the due date and a very short description of the assignment. It should contain functions and these functions should have arguments.

Each function should start by a very brief description of the task it performs. Each variable definition should be followed by a comment describing the function of the variable.

All numerical constants should be specified using symbolic constants defined at the beginning of the program.