Electrical, Computer, and Systems Engineering

ECSE-4730 Computer Systems Architecture

Fall 1998

 

Problem Set 5/6-- Due MONDAY, November 23, 1998

 

Your Name

Circle Your Section

8-9:50 am 10-11:50 am noon-1:50pm

 

Notes:

    1. Be brief.
    2. The answers you submit should be the result of your own individual work. This should not be a collaborative activity.
    3. Refer to the course syllabus under "General Policies Regarding Graded Material" for important notes regarding problem sets. Reminder, as stated in syllabus: SUBMISSIONS NOT HANDEDTO COURSE STAFF (E.G. SLIPPED UNDER DOOR, PLACED IN MAILBOX) WILL AUTOMATICALLY BE MARKED LATE.
    4. If after working on the problems, you feel you may need some help, please don’t hesitate to see the instructor or TA. Instructor office hours are 10-11:30 MW, and TAs will conduct the problem sessions on Friday, Sept 11th where you can seek their help
    5. Make sure the pages are stapled together before handing it in.

 

----------------------------------Do not write below this line-----------------------------------------

 

1

2

3

Total

10

25

15

50*

*Note: all homeworks will be normalized and equally weighted.

 

TA Signature :___________________________________

 

 

  1. (10 points) [Processes]

    2. A) (2 pts) What is multiprogramming ?

     

     

     

     

    B) (6 points) State how the following operating system concepts are used to support multiprogramming ?

     

    Processes & Threads:_____________________________________________

     

    ________________________________________________________________

     

    Virtual memory: __________________________________________________

     

    _________________________________________________________________

     

    Mailbox: _________________________________________________________

     

    _________________________________________________________________

     

     

    C) (2 pts) What issues arise from the need to support multi-user environments and interactive (time-sharing) environments ?

     

     

     

     

     

     

     

     

     

     

     

  2. [Scheduling] (25 points)

 

A) (6 pts) Define:

 

CPU-burst cycle and I/O burst cycle: _________________________________

 

____________________________________________________________________

 

Preemptive scheduling: ________________________________________________

 

____________________________________________________________________

 

Non-preemptive scheduling: __________________________________________

 

____________________________________________________________________

 

 

 

  1. (4 points) How is the CPU utilization criterion different from the throughput criterion ? How is turnaround time different from waiting time ?

 

Utilization vs Throughput : _______________________________________________

 

_______________________________________________________________________

 

Turnaround vs waiting time :______________________________________________

 

_______________________________________________________________________

 

 

 

 

 

  1. (15 points) 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 have arrived in the order P1, P2, P3, P4, P5, all at time 0.

 

  1. (10 out of 16 pts) Draw four Gantt charts (see Silbershatz and Galvin chap 5, pg 129 (5th edition) or pg 137 (4th edition)) illustrating the execution of these processes using FCFS, SJF, a nonpremptive priority scheduling, and RR (quantum = 1) scheduling. For the priority scheduling, assume that a smaller priority number implies a higher priority.

    2.  

     

     

     

     

     

  2. (4 out of 15 pts) What is the waiting time of each process for each of the scheduling algorithms of part a ?

    3.  

    FCFS: _________________________________________________________________

     

    SJF: _________________________________________________________________

     

    Priority: _______________________________________________________________

     

    RR: _________________________________________________________________

     

     

  3. (1 pt) Which of the schedules in part a results in the minimum average waiting time (over all processes)?

 

_____________________________________________________________________

 

 

 

  1. [File Systems] (15 points)
  1. (5 points) Discuss at least three issues each which arise in supporting a tree-structured and acyclic-graph structured directories.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

B) (6 points) Discuss the pros and cons of linked-allocation of file blocks and how MS-DOS implements a linked-allocation structure, the File Allocation Table (FAT).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

C) (4 points) How would one a) allocate a free block to a file in DOS, and b) access a random block efficiently in DOS using the FAT ?