CSE2302 CMG-2003-09

CSE2302 Operating Systems

Assignment 2

Operating Systems

Due Date: 13th. October 2003

This Assignment has 6 sections, and you should complete all 6 sections. The Assignment contributes 15% to the assessment of the subject.

Make sure you show all calculations, and provide justification for decisions and assumptions you make.

  1. Process Synchronisation

    1. [0.5mark] Write a brief description of the possible coding errors which could occur in the use of semaphores. The description could start with syntax errors, and must, of course, end with runtime errors.

    2. [1mark]Consider synchronisation based on the monitor type-specification:

      1. What is the main advantage of using monitors?
      2. Most Operating Systems textbooks present the implementation of monitors using semaphores and condition variables. Write a brief description of an example implementation in your own words, taken from any textbook or from NET. You must reference material that you have used.

    3. [1mark] Use the NET to determine whether the Intel Pentium processor architecture provides synchronisation hardware. Usually these instructions take the form of atomic test-and-set instructions. Write a brief description of results of your search and include references to literature that you have used.

    4. Attempt only ONE of the following

      1. [1mark] Several text books present solutions to the reader/writer problem with the additional condition that: writers have priority over readers. Write out the code solving this problem, and write a short description to accompany the code.

      2. [1mark] Write code to implement a solution to the following problem. You must also write a brief description of your code and reference all of the sources which you used to produce your solution.

        Santa Claus sleeps in his shop at the North Pole and can only be awakened by either:
        1. all 5 reindeer being back from their vacation, or
        2. 3 elves having difficulties, while making toys, and wanting to speak to him.
        If Santa wakes and finds 3 elves and 5 reindeer then he decides to deliver toys using the sleigh pulled by the reindeer, leaving the 3 elves to have their questions answered after Christmas. (based on problem from Stallings Operating Systems 4Ed. Pg262)

  2. Process Scheduling

    1. [1mark] Briefly explain how FCFS scheduling can favour CPU-bound processes. Then briefly describe the convoy effect in the context of process scheduling.

    2. [1mark] For the processes listed in the table below, use a gantt chart to illustrate their execution using:

      1. First-come, First-served scheduling
      2. Shortest job first(non-preemtive) scheduling
      3. Shortest remaining time scheduling
      4. Round-robin scheduling with quantum 2
      5. Preemtive priority scheduling with 0(zero) being the highest priority.

      Process Arrival Time (mS) Burst Time (mS) Priority
      P1 0 11 5
      P2 2 3 2
      P3 3 3 3
      P4 5 4 0
      P5 8 4 1

    3. [1mark] For the same table of processes and the same set of scheduling policies, determine the average turn around times.

    4. [1mark] Most systems using preemptive prioritised scheduling seem to have an idle process. Briefly describe the purpose of this process.
    5. [1mark] Briefly explain why nonpreemtive scheduling is not a good choice for an interactive computer system.(response time)

  3. Deadlocks

    1. [1mark] Modern cities tend to be layed-out on a regular square grid of roads. So city road traffic authorities must be aware of the conditions for deadlock(gridlock):

      1. Describe how the 4 necessary conditions conditions apply in the case of city traffic management.
      2. State a simple traffic management rule that will avoid deadlocks.

    2. [1mark] Assume that a system has four resource types, labelled A to D, and has 6 instances of A, 4 instances of B and C, and 2 instances of D. Given the Maximum Claim Table and Current Allocation Table, below, use the bankers algorithm to determine whether the system is in a safe state.

      • Maximum Claim Table
        Process Resource A Resource B Resource C Resource D
        P1 3 2 1 1
        P2 1 2 0 2
        P3 1 1 2 0
        P4 3 2 1 0
        P5 2 1 0 1
      • Current Allocation Table
        Process Resource A Resource B Resource C Resource D
        P1 2 0 1 0
        P2 1 1 0 0
        P3 1 1 0 0
        P4 1 0 1 0
        P5 0 1 0 1

  4. File System Interface and Implementation

    1. [1mark] The MSDOS operating system had a file manager which required that each file have a file control block. In your own words, write a brief description of his data structure and describe the equivalent structure found in the UNIX file system.

    2. [1mark] File System Performance is disk read/write head scheduling. Briefly define seek-time and rotational latency. Given a disk drive which has 5000 cylinders, numbered sequentially from 0 to 4999, and that the drive is currently serving cylinder 150, and that the FIFO queue of pending cylinder requests is: 80, 1500, 910, 1600, 950, 1500, 1000, 1850, 110. Estimate the total distance that the disk arm move for each of the following disk-scheduling algorithms:

      1. FCFS
      2. SSTF
      3. SCAN
      4. C-SCAN
      5. LOOK
      6. C-LOOK

    3. [1mark]

      Briefly describe purpose of the UNIX inode data structure.

    4. [2marks]

      Briefly describe the term external fragmentation in the context of dynamic storage allocation.

  5. Memory management and Virtual Memory

    1. [1mark] In the context of Virtual Memory, briefly define(in your own words) the following:

      1. Page Fault
      2. Translation Lookaside Buffer
      3. Effective Access Time
      4. Inverted page table

    2. [1mark] Write a brief description of the need for code to be relocatable if we are going to use a Virtual Memory system.

    3. [1mark] In tracing a particular process , the following address sequence was recorded 0701, 0402, 0101, 0612, 0122, 0204, 0101, 0601, 0302, 0103, 0404, 0201, 0602, 0102, 0103, 0104,0609, 0102, 0405. Here the page size is set to 100 bytes(not a power of 2, in order to simplify the problem). Addresses start at 0000, and are given in base 10. How many page faults would occur for the following replacement algorithms, assuming that the number of frames is 3:

      1. Optimal Replacement
      2. Least Recently Used Replacement
      3. Second Chance(Clock algorithm) replacement.

    4. [1mark] Since handling page faults is timeconsuming, increasing the page size will reduce the number of page faults. How would an operating System designer determine the optimum page size?

    5. [1mark] Consider an operating system which uses basic paging(without demand paging) with logical address space of 1024 Mbytes and a page size of 128Kbytes. And given that the hardware of the system consists of 32 Mbytes of main memory, with access time of 65 nanosec, and a smallest addressable unit of 4 bytes.

      1. How many frames are there in main memory? (Show you calculations)
      2. Determine the number of bits required for the page number, and the number of bits required for the page offset.
      3. Assume that the page table is stored in main memory. What is the effective memory access time of this simple system. Describe how the page table organisation could affect your answer.(hint: single level or two level address decoding.)

  6. Protection and Security

    1. [1mark] Briefly describe the Protection mechanisms in the context of the enforcement security policies governing resource use.

    2. [1mark] Briefly define the term security policy.

    3. [1mark]Briefly define the term security mechanism.

    4. [1mark]Briefly describe why unauthorised access(stealing) computational bandwith or digital storage space is a security issue. Surely stealing information would be the only security issue on a computer system.

    5. [1mark]Write a brief description of the protection mechanisms available in JAVA. Could a downloaded JAVA program erase all of the files on a users disk?