Operating Systems
Exam 1 Solutions
(1)
Multiprogramming / Timesharing
In a multiprogramming system, many processes are stored
in memory at the same time. When one process must block
for I/O, another process in memory is given the CPU. By
storing multiple programs in memory each at various stages
in their executions, the CPU does not sit idle waiting for
I/O operations to complete.
Busy Waiting / Blocking
Busy waiting and blocking are both ways a process can wait
for an event to occur. In busy waiting, the process repeatedly
checks to see if the event has occurred. When a process
blocks, it is suspended until some the external event occurs
at which time the operating systems puts the process back in the
ready queue. Blocking is a much better way to wait for an event
since it does not consume CPU cycles like busy waiting does.
(2)
Shortest Job First: Schedule the jobs in order of increasing
CPU burst.
P2 completes at time 1
P4 completes at time 2
P3 completes at time 4
P5 completes at time 9
P1 completes at time 19
Average Response Time = 1 + 2 + 4 + 9 + 19 = 7 ms
------------------
5
Round Robin using 1 ms time slice and assuming order of processes
in ready queue at time 0 is P1, P2, P3, P4, P5.
P2 completes at time 2
P4 completes at time 4
P3 completes at time 7
P5 completes at time 14
P1 completes at time 19
Average Response Time: 2 + 4 + 7 + 14 + 19 = 9.2 ms
-------------------
5
(3)
The system is guaranteed free from deadlock (no matter how the
tape drives are allocated) for n = 0, 1, 2, 3, 4, and 5.
It should be clear that it is free from deadlock when n = 0, 1, 2,
and 3 since even if each process requests the maximum number
of tape drives (2), each one's request can be forfilled immediately
since there are 6 tape drives.
For n = 4 and 5, if each process requests the maximum tape drives,
all their requests cannot be forfilled immediately, however they
can all be forfilled eventually meaning there is no deadlock.
Since there are six tape drives, at least one process can be
given 2 tapes drives so that it can complete. Once it completes,
the 2 tape drives it has can be given to another process that
is waiting and so on.... Eventually, all process can complete.
For n > 5, deadlock can occur. Consider the case when n = 6.
If all 6 processes hold one tape drive and then all 6 request
an additional tape drive, a deadlock results. None of the
processes will ever finish because they are all waiting for another
process to complete so that they can use its tape drive.
(4)
The system is in a safe state because there is a way to allocate
the remaining resources so that eventually all processes complete.
For example, P2 currently has all the plotters it needs to complete.
Once it finishes, its two plotters can be given to P0 and
P1. When P0 and P1 complete, there are a total of 4 plotters
free. 3 of these 4 plotters can be given to P4 which then can
complete. When P4 completes there are 7 plotters available which
can be given to P3.
(5)
Brief Explaination of Modified Readers/Writers Code Below:
To make it so that new readers have to wait to enter the database
if a writer is waiting, we can add a new semaphore called no_writer_waiting.
It is initially 1 to indicate that no writer is waiting.
When a writer is ready to access the database,
it first performs a down on no_writer_waiting and doesn't perform
an up on it until it has control of the database.
A reader process must also perform a down on no_writer_waiting before trying
to access the database. If a writer is waiting (no_writer_waiting =
0), this down operation will cause the reader to wait until the
writer gets control of the database. If no writer is waiting
(no_writer_waiting = 1), then the reader does not have to wait
for the down operation. The reader immediately does an up operation
so that other readers can enter.
semaphore db = 1;
semaphore mutex = 1;
int rc = 0;
semaphore no_writer_waiting = 1;
void writer( void )
{
while ( TRUE )
{
generate_data();
down( no_writer_waiting );
down( db );
up( no_writer_waiting );
write_data_base();
up( db );
}
}
void reader( void )
{
while ( TRUE )
{
down( no_writer_waiting );
up( no_writer_waiting );
down( mutex );
rc = rc + 1;
if ( rc == 1 ) down( db );
up( mutex );
read_data_base();
down( mutex );
rc = rc - 1;
if ( rc == 0 ) up( db );
up( mutex );
use_data_read();
}
}
(6)
In this particular system, the CPU activity consists of
processing a job (for time 1.5ms on average) and then
switching to a new job (in time .12ms). This activity
is diagrammed below:
Time ---->
{--------1.5ms--------}{--0.12ms--}{--------1.5ms--------}{--0.12ms--}....
The CPU utilization (or efficiency) is the percent of time
the CPU is doing useful work. (Running a process is useful
work; switching to a new job is overhead and is not
useful work even though it is necessary.) Therefore the
CPU utilization of this system is:
1.5 ms
CPU Utilization = -------------- = 92%
1.5ms + 0.12ms
(Note that on average a process goes to I/O before its
time-slice expires and therefore the length of the time-slice
does not play a role in the calculations.)
(7)
Two-level scheduling is used when not all ready processes
can fit into main memory and thus some must reside on disk.
The processes in memory are scheduled using one algorithm
(called the low-level schduling algorithm) and occasionally a second
scheduling algorithm (the high-level schduling algorithm)
moves processes from disk to memory (and vice versa).
Because it takes a relatively long time to get a process from
disk into main memory and ready to run, the two classes of
jobs cannot be scheduled in the same way, hence the need
for two-level scheduling.
(8)
A block device stores data in fixed sized blocks each having a unique
address. A character device accpets or generates a stream of bytes --
there is no way to address the data.
Block Device Examples: floppy disk, hard drive, cdrom
Character Device Examples: printer, mouse, modem