Solutions to Practice Problems

 

 

1)

6.23-6.24

Write a bounded-buffer monitor in which the buffers (portions) are embedded within the monitor itself. Answer:

 

Monitor boundedbuffer

{                  

                  Const bufsize = 100;

                 item buf[100];

                 int in, out, count;

                 condition Producer, Consumer;

                

                  void produce (item x)  {

                     

                     if (count == bufsize) Producer.wait();

                     buf[in] = x;

                    count++;

                    in = (in + 1) % n;

                    Consumer.signal();

                 }

 

                  void consume (item& x)   {

                       if (count == 0) Consumer.wait();

                       x = buf[out];

                       count --;

                       out = (out + 1) % n;

                       Producer.signal();

                }

                   

                 initialization_code() {

                       in:=0;

                       out:=0;                     

                       count:=0;

                   }

}

 

The strict mutual exclusion within a monitor makes the bounded-buffer monitor of Exercise 6.23 mainly suitable for small portions.

Explain why this assertion is true.

Design a new scheme that is suitable for larger portions.

Answer:

a.

If the portions are large, then adding and removing data to the shared pool requires a considerable amount of time. Since the producer and consumer cannot execute in the monitor concurrently, parallelism is lost.

b.

No Answer

 

6.33

in a multi processor system the busy waiting is offloaded to the other cpu and primary functions aren’t hindered.  On a single processor system spinlocks introduce a lot of busy waiting and wast processor cycles.

 

6.37

A)  available resources is the date in the race condition

B)  P273

C)  int decrease_count(int count)

{

if (available_resources<count)

            return -1

else

for(int i=0; i<count; i++)

            wait(available_resources);

return 0;

}

 

int increase_count(int count)

{

for(int i=0; i<count; i++) signal(available resources);

return 0;

}

 

 

7.9

Yes it is possible to have a deadlock using only a single process.  Should it require access to a resource it locked previously but didn’t meet the requirements to unlock a deadlock will be experienced.

 

Is it possible to have a deadlock involving only one single process? Explain your answer. Answer: No. This follows directly from the hold-and-wait condition.

People have said that proper spooling would eliminate deadlocks. Certainly, it eliminates from contention card readers, plotters, printers, and so on. It is even possible to spool tapes (called staging them), which would leave the resources of CPU time, memory, and disk space. Is it possible to have a deadlock involving these resources? If it is, how could

such a deadlock occur? If it is not, why not? What deadlock scheme would seem best to eliminate these deadlocks (if any are possible), or what condition is violated (if they are not possible)? Answer: It is possible to still have a deadlock. Process P1 holds memory pages that are required by process P2 , while P2 is holding the CPU that is required by P1.The best way to eliminate these types of deadlock is to use preemption.

 

7.16

a)  The max need is between 1 & m inorder to insure that a process doesn’t require more resources than actually exist.

b)  The sum of all max needs is less than m + n.  if not you run the risk of waiting for resources that wont be released.  For example you have 2 resources and 2 process and each have a max need of two.  If each takes 1 they will forever wait for the other to realesas the resouce which it wont do till it gets 2 total.

 

7.20

allocation

0

0

1

2

1

0

0

0

1

3

5

4

0

6

3

2

0

0

1

4

Max

0

0

1

2

1

7

5

0

2

3

5

6

0

6

5

2

0

6

5

6

Available

1

5

2

0

A)

Need (max-allocation)

0

0

0

0

0

7

5

0

1

0

0

2

0

0

2

0

0

6

4

2

B)

There is a sequence that each process can take to complete max so yes in safe state.

C)

The request can be filled since there is enough available resources. 0,4,2,0

 

7.22

North

{

wait(bridge)

cross()

signal()

 

{

 

South

{

wait(bridge)

cross()

signal()

 

}

7.23

North

{

Signal(south)

wait(bridge)

cross()

signal()

 

{

 

South

{

signal(north)

wait(bridge)

cross()

signal()

 

}

 

8.10

a)

b)

the object  modules and the location of the other needed object modules are reuired to be passed to the linkage editor in order for it to be able to properly link the program.

 

 8.18

I can’t figure out how these numbers are derived

 

8.4 Consider a logical address space of eight pages of 1024 words each,

mapped onto a physical memory of 32 frames.

a. How many bits are there in the logical address?

b. How many bits are there in the physical address?

Answer:

a. Logical address: 13 bits

b. Physical address: 15 bits

8.22

Reentrant code works best with segmentation because is treats each part of the code as its own separate element and makes accessing the shared parts of the code easy to follow from a programming point of view.  Strait paging does everything automatically and give the programmer no control over what is done and how its stored in memory.

 

8.25

3 memory operations are performed retrieve section, retrieve page, and retrieve data at offset.  Retreive the pate table entry for the page table entry.  Need to retrieve page table entry for the frame where the data is.  Get data

9.3

Demand paging

Good

Stack – resides in memory and as things are required they are recovered from the secondary memory and added to the stack as necessary.

Hashed Symbol table – This will keep things out of memory until they are required.

Binary search – will be able to go through on a needed bases and unsearched values need not be loaded to memory.

Pure code – good because the code is already divided into parts and those parts only need to be loaded as needed.

 

Not good

Sequential Search -  this will result in an excessive amount of page faults and greatly slow the system.

 

????????

Vector operations –  array multiplication

Indirection –  usage of lots of pointers

 

9.7

a. The page reference string is

0, 1, 0, 2, 0, ..., 0, 49, 0, 1, 0, 2, 0, ..., 0, 49, ...

and thus there will be 5000 page faults.

b. The page reference string is

0, 1, 0, 2, 0, ..., 0, 49

and thus there will be 50 page faults.

 

 

9.12

a

the processes are just starting to rev up and a lot of paging is going on in order to load the code into the cpu  “thrashing

 

b

all the needed code has been paged and the cpu is actively running all the processes

could increase through increased multiprogramming is this right?

 

C

The processes have done most of the heave work and things have slowed down for both the cpu and I/O usage.  Increasing multiprogramming will increase utilization.

 

2]

The CCR equivalent to the monitor program: (changes in red)

        region Simple when ((count mod 2) = 0) do  // condition changed from != to =

         count = count+1;

 

Alternate Solution

       region Simple do

           begin

              count = count +1;

              await (count mod 2) != 0;

           end;

3]

Deadlocks can be detected, avoided or prevented. Comment on the following statements: (i.e. state if they are correct or wrong and why).

4]

Some operating systems use base and bound registers to protect memory. The bounds registers updated (or changed)

When?

Why?

By whom?

5]

Swapping is a method of increasing the capacity of the main memory. Note that swapping is not the same as demand paging.

Read the book for a description of swapping - processes are swapped out when there is not enough memory to run all of them and swapped in when some memory is cleared by swapping someone else out. The entire process has to be in memory, as there is no support for demand paging in swapping systems.

6]

Consider a demand paged system using "lazy" or "pure" demand paging.

Lazy demand paging is where a page is loaded only on demand. That is when a process starts, zero pages are loaded, and when a page fault happens only 1 page is loaded (as opposed to several pages, in pre-paging systems.) MAX number of pages is determined by page table size limit, working set limit and disk swap space limits. MAX for all processes are for same reasons.

Page fault rate is determined by page replacement policy, program structure and main memory size.

7]

The virtual memory system using demand paging, also provides memory protection.

Via the page table and the page table limit register.

Page not in memory is an access within the page table bounds, but the valid bit in the PTE is zero. Illegal page is outside the bounds of the page table.

8]

Show that the “Optimal Page Replacement Policy (OPT)" is indeed optimal, that is there is no algorithm, known or unknown that can perform better than the OPT policy.

Construct a page reference string and show that for any other algo, a page will be replaced that will be referenced in the future - before the page the OPT algo will reference.

9]

A method of deadlock prevention is the use of ordered resource allocation.

Does this scheme work when there are multiple instances of each resource?

Justify your answer.

Does not work - think of a case where there is only 1 resource type and n instances.

10]

The device driver for disk devices is used to read and write blocks of data to and from disk units.

The 2 halves are the interrupt half and the user half. The user half works synchronously with the operating system, the interrupt half works using interrupts and facilitates the walking up of the process when the I/O is over. Scheduling policy is implemented in the driver, in the user half.

No connection between disk head scheduling and page replacement.

Neither.