6

Homework Solution 2

1. Show how to implement monitors using locks and condition variables.

Answer : Every external procedure is replaced by

Lock acquire

Procedure

Lock release

For every condition defined inside the monitor, we use a condition variable as follows:

X ( X-condition(lock) )

X.wait()

{

X-condition.wait();

}

X.signal()

{

X-condition.signal();

}

Note that we are NOT implementing Hoare style monitors here. In fact, we are supporting option 2 discussed in page 218 of Silberschatz.

6.3 Consider the following set of processes, with the length of the CPU-burst time given in

milliseconds:

Process	Burst Time	Priority
P1	10	3
P2	1	1
P3	2	3
P4	1	4
P5	5	2

The processes are assumed to have arrived in the order P1, P2, P3, P4, P5, all at time 0.

a. Draw four Gantt charts illustrating the execution of these processes using FCFS, SJF, a

nonpreemptive priority (a smaller priority number implies a higher priority), and RR

(quantum = 1) scheduling.

b. What is the turnaround time of each process for each of the scheduling algorithms in

part a?

c. What is the waiting time of each process for each of the scheduling algorithms in part

d. Which of the schedules in part a results in the minimal average waiting time (over all

processes)?

Answer:

a. The four Gantt charts are

FCFS

SJF

Priority

b. Turnaround time

Process	FCFS	RR	SJF	Priority
P1	10	19	19	16
P2	11	2	1	1
P3	13	7	4	18
P4	14	4	2	19
P5	19	14	9	6

C.. Waiting time (turnaround time minus burst time)

Process	FCFS	RR	SJF	Priority
P1	0	9	9	6
P2	10	1	0	0
P3	11	5	2	16
P4	13	3	1	18
P5	14	5	4	1

d. Shortest Job First

6.4 Suppose that the following processes arrive for execution at the times indicated. Each

process will run the listed amount of time. In answering the questions, use nonpreemptive

scheduling and base all decisions on the information you have at the time the decision

must be made.

Process Arrival Time Burst Time

P1 0.0 8

P2 0.4 4

P3 1.0 1

a. What is the average turnaround time for these processes with the FCFS scheduling

algorithm?

b. What is the average turnaround time for these processes with the SJF scheduling algorithm?

c. The SJF algorithm is supposed to improve performance, but notice that we chose to

run process P1 at time 0 because we did not know that two shorter processes would

arrive soon. Compute what the average turnaround time will be if the CPU is left

idle for the first 1 unit and then SJF scheduling is used. Remember that processes P1

and P2 are waiting during this idle time, so their waiting time may increase. This

algorithm could be known as future-knowledge scheduling.

Answer:

a. 10.53

b. 9.53

c. 6.86

Remember that turnaround time is finishing time minus arrival time, so you have to sub-tract

the arrival times to compute the turnaround times. FCFS is 11 if you forget to subtract

arrival time.

6.6 What advantage is there in having different time-quantum sizes on different levels of a

multilevel queueing system?

Answer: Processes that need more frequent servicing, for instance, interactive processes

such as editors, can be in a queue with a small time quantum. Processes with no need

for frequent servicing can be in a queue with a larger quantum, requiring fewer context

switches to complete the processing, making more efficient use of the computer.

6.9 Suppose that a scheduling algorithm (at the level of short-term CPU scheduling) favors

those processes that have used the least processor time in the recent past. Why will this algorithm

favor I/O-bound programs and yet not permanently starve CPU-bound programs?

Answer: It will favor the I/O-bound programs because of the relatively short CPU burst

request by them; however, the CPU-bound programs will not starve because the I/O-bound

programs will relinquish the CPU relatively often to do their I/O.

6.10 Explain the differences in the degree to which the following scheduling algorithms discriminate

in favor of short processes:

a. FCFS

b. RR

c. Multilevel feedback queues

Answer:

a. FCFS—discriminates against short jobs since any short jobs arriving after long jobs

will have a longer waiting time.

b. RR—treats all jobs equally (giving them equal bursts of CPU time) so short jobs will

be able to leave the system faster since they will finish first.

c. Multilevel feedback queues—work similar to the RR algorithm—they discriminate

favorably toward short jobs.

7. Explain the difference between a virtual address and a physical address.

Answer: Virtual address is the address generated by the user-level program. The address seen by the memory unit is the physical address. The mapping between these addresses is done by the memory management unit (typically through paging, segmentation, or both). The virtual address differs from the physical address due to this execution time address binding.

9.2 Explain the difference between internal and external fragmentation.

Answer: Internal Fragmentation is the area in a region or a page that is not used by the

job occupying that region or page. This space is unavailable for use by the system until

that job is finished and the page or region is released.

9.9 On a system with paging, a process cannot access memory that it does not own; why? How

could the operating system allow access to other memory? Why should it or should it not?

Answer: An address on a paging system is a logical page number and an offset. The

physical page is found by searching a table based on the logical page number to produce

a physical page number. Because the operating system controls the contents of this table,

it can limit a process to accessing only those physical pages allocated to the process. There

is no way for a process to refer to a page it does not own because the page will not be in

the page table. To allow such access, an operating system simply needs to allow entries

for non-process memory to be added to the process’s page table. This is useful when two

or more processes need to exchange data—they just read and write to the same physical

addresses (which may be at varying logical addresses). This makes for very efficient

interprocess communication.

9.10 Consider a paging system with the page table stored in memory.

a. If a memory reference takes 200 nanoseconds, how long does a paged memory reference

take?

b. If we add associative registers, and 75 percent of all page-table references are found

in the associative registers, what is the effective memory reference time? (Assume

that finding a page-table entry in the associative registers takes zero time, if the entry

is there.)

Answer:

a. 400 nanoseconds; 200 nanoseconds to access the page table and 200 nanoseconds to

access the word in memory.

b. Effective access time = 0.75X (200 nanoseconds) + 0.25 X (400 nanoseconds) = 250

nanoseconds.

9.12 Why are segmentation and paging sometimes combined into one scheme?

Answer: Segmentation and paging are often combined in order to improve upon each

other. Segmented paging is helpful when the page table becomes very large. A large

contiguous section of the page table that is unused can be collapsed into a single segment

table entry with a page-table address of zero. Paged segmentation handles the case of

having very long segments that require a lot of time for allocation. By paging the segments,

we reduce wasted memory due to external fragmentation as well as simplify the allocation.

9.16 Consider the following segment table:

Segment Base Length

0 219 600

1 2300 14

2 90 100

3 1327 580

4 1952 96

What are the physical addresses for the following logical addresses?

a. 0,430

b.1,10

c. 2,500

d. 3,400

e. 4,112

Answer:

a. 219 + 430 = 649

b. 2300 + 10 = 2310

c. illegal reference, trap to operating system

d. 1327 + 400 = 1727

e. illegal reference, trap to operating system

10.3 A certain computer provides its users with a virtual-memory space of 2 32 bytes. The computer

has 2 18 bytes of physical memory. The virtual memory is implemented by paging,

and the page size is 4096 bytes. A user process generates the virtual address 11123456.

Explain how the system establishes the corresponding physical location. Distinguish between

software and hardware operations.

Answer: The virtual address in binary form is

0001 0001 0001 0010 0011 0100 0101 0110

Since the page size is 2 12 , the page table size is 2 20 . Therefore the low-order 12 bits “0100

0101 0110” are used as the displacement into the page, while the remaining 20 bits “0001

0001 0001 0010 0011” are used as the displacement in the page table.

10.5 Assume we have a demand-paged memory. The page table is held in registers. It takes 8

milliseconds to service a page fault if an empty page is available or the replaced page is

not modified, and 20 milliseconds if the replaced page is modified. Memory access time

is 100 nanoseconds.

Assume that the page to be replaced is modified 70 percent of the time. What is the maximum

acceptable page-fault rate for an effective access time of no more than 200 nanoseconds?

Answer:

0.2 _sec = (1- P)X 0.1 _sec + (0.3P)X 8 millisec + (0.7P)X20 millisec

0.1 = - 0.1P + 2400 P + 14000 P

0.1 = 16,400 P(approx)

P = 0.000006 (approx)

10.9 Consider a demand-paging system with the following time-measured utilizations:

CPU utilization 20%

Paging disk 97.7%

Other I/O devices 5%

Which (if any) of the following will (probably) improve CPU utilization? Explain your answer.

a. Install a faster CPU.

b. Install a bigger paging disk.

c. Increase the degree of multiprogramming.

d. Decrease the degree of multiprogramming.

e. Install more main memory.

f. Install a faster hard disk or multiple controllers with multiple hard disks.

g. Add prepaging to the page fetch algorithms.

h. Increase the page size.

Answer: The system obviously is spending most of its time paging, indicating over-allocation

of memory. If the level of multiprogramming is reduced resident processes

would page fault less frequently and the CPU utilization would improve. Another way to

improve performance would be to get more physical memory or a faster paging drum.

a. Get a faster CPU—No.

b. Get a bigger paging drum—No.

c. Increase the degree of multiprogramming—No.

d. Decrease the degree of multiprogramming—Yes.

e. Install more main memory—Likely to improve CPU utilization as more pages can

remain resident and not require paging to or from the disks.

f. Install a faster hard disk, or multiple controllers with multiple hard disks—Also an

improvement, for as the disk bottleneck is removed by faster response and more

throughput to the disks, the CPU will get more data more quickly.

g. Add prepaging to the page fetch algorithms—Again, the CPU will get more data

faster, so it will be more in use. This is only the case if the paging action is amenable

to prefetching (i.e., some of the access is sequential).

h. Increase the page size—Increasing the page size will result in fewer page faults if

data is being accessed sequentially. If data access is more or less random, more

paging action could ensue because fewer pages can be kept in memory and more

data is transferred per page fault. So this change is as likely to decrease utilization

as it is to increase it.

SG10.11:
Consider the following page reference string:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6.
How many page faults would occur for the following replacement algorithms, assuming 5 frames? Remember all frames are initially empty, so your first unique pages will all cost one fault each.
LRU

FIFO
Optimal replacement

For 5 frames

LRU 8

FIFO 10

Optimal Replacement 7

10.17 Consider a demand-paging system with a paging disk that has an average access and

transfer time of 20 milliseconds. Addresses are translated through a page table in main

memory, with an access time of 1 microsecond per memory access. Thus, each memory

reference through the page table takes two accesses. To improve this time, we have added

an associative memory that reduces access time to one memory reference, if the page-table

entry is in the associative memory.

Assume that 80 percent of the accesses are in the associative memory and that, of the

remaining, 10 percent (or 2 percent of the total) cause page faults. What is the effective

memory access time?

Answer:

effective access time = (0.8)X(1 usec) + (0.1)X (2 usec) + (0.1)X(5002 usec)

= 501.2 usec

= 0.5 millisec

10.18 Consider a demand-paged computer system where the degree of multiprogramming is

currently fixed at four. The system was recently measured to determine utilization of CPU

and the paging disk. The results are one of the following alternatives. For each case, what

is happening? Can the degree of multiprogramming be increased to increase the CPU

utilization? Is the paging helping?

a. CPU utilization 13 percent; disk utilization 97 percent

b. CPU utilization 87 percent; disk utilization 3 percent

c. CPU utilization 13 percent; disk utilization 3 percent

Answer:

a. Thrashing is occurring.

b. CPU utilization is sufficiently high to leave things alone, an increase degree of multiprogramming.

c. Increase the degree of multiprogramming.