Description
No handwritten submissions will be accepted or graded. Your submission must be a pdf (not doc, docx, tex, html, rtf and any other format, but pdf) file with the typed solutions to the 5 problems included in this document.
This is an individual assignment. Individual assignments, as the word indicate, are to be done INDIVIDUALLY. Any sign of collaboration will result in a 0 and being reported to the Honor Board.
Problem 1. (10 pts)
Does the busy waiting solution using the turn variable (Fig. 2-23 in the book) solves the mutual exclusion problem when two processes are running on a shared-memory multiprocessor, that is, two CPUs sharing a common memory?
Problem 2. (20 pts)
Five batch jobs. A through E, arrive at a computer center at almost the same time. They have estimated running times of 10, 6, 2, 4, and 8 minutes. Their (externally determined) priorities are 3, 5, 2, 1, and 4, respectively, with 5 being the highest priority. For each of the following scheduling algorithms, determine the mean process turnaround time. Ignore process switching overhead.
-
Round robin.
-
Priority scheduling.
-
First-come, first-served (run in order 10, 6, 2, 4, 8).
-
Shortest job first.
For (a), assume that the system is multiprogrammed, and that each job gets its fair share of the CPU. For
-
through (d), assume that only one job at a time runs, until it finishes. All jobs are completely CPU bound.
Problem 3. (20 pts)
A soft real-time system has four periodic events with periods of 50, 100, 200, and 250 msec each. Suppose that the four events require 35, 20, 10, and x msec of CPU time, respectively. What is the largest value of x for which the system is schedulable?
Problem 4. (25 pts)
Consider the following state of a system with four processes, P1, P2, P3, and P4, and five types of resources, RS1, RS2, RS3, RS4, and RS5:
Using the deadlock detection algorithm described in Section 6.4.2, show that there is a deadlock in the system. Identify the processes that are deadlocked.
Problem 5. (25 pts)
A system has four processes and five allocable resources. The current and maximum needs are as follows:
What is the smallest value of x for which this is a safe state? Show your calculations using the Banker’s Algorithm.
