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 ?

     

    Supporting the illusion of multiple programs using a single CPU at once.

     

     

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

     

    Processes & Threads: A process is a program in execution. The OS switches CPU among multiple processes. Threads reduce the context switching overhead.

     

    Virtual memory: Virtual memory allows multiple processes to be resident in memory even if only a part of their address space is physically stored in memory

     

    Mailbox: Mailbox allows asynchronous communication between multiple processes, enabling processes to cooperate on tasks.

     

     

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

     

    Multi-user: protection and sharing issues

     

    Interactive: optimizing response times in addition to throughput

     

     

     

     

     

  2. [Scheduling] (25 points)

 

A) (6 pts) Define:

 

CPU-burst cycle and I/O burst cycle: Typical process execution proceeds as an alternating cycle of CPU bursts when it needs the CPU, and I/O bursts when it does I/O.

Preemptive scheduling: A process can be moved from CPU (running state) to ready state before the end of its current CPU burst.

Non-preemptive scheduling: A process which gets control of CPU (running state) releases it only when it finishes its CPU burst (moves to waiting state) or terminates.

 

 

 

  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 : Utilization measures CPU activity (both user and system tasks) whereas throughput measures number of only completed user tasks per second.

 

Turnaround vs waiting time : Turnaround time is the total time spent in system by a process (start to finish) while waiting time measures only time spent in the ready queue.

 

 

 

  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.  

     

    FCFS:

     

    0 10 11 13 14 19

    (P1) (P2) (P3) (P4) (P5)

    SJF:

    0 1 2 4 9 19

    (P2) (P4)(P3) (P5) (P1)

     

    nonpremptive priority:

    0 1 6 16 18 19

    (P2) (P5) (P1) (P3) (P4)

     

     

    RR:

     

     

    P1 P2 P3 P4 P5 P1 P3 P5 P1 P5 P1 P5 P1 P5 P1 P1 P1 P1 P1

     

     

     

     

     

     

  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: P1 = 0, P2 = 10, P3 = 11, P4 = 13, P5 = 10

     

    SJF: P1 = 9, P2 = 0, P3 = 2, P4 = 1, P5 = 4

     

    Priority: P1 = 6, P2 = 0, P3 = 16, P4 = 18, P5 = 1

     

    RR: P1 = 4+2+1+1+1 = 9; P2 = 1; P3 = 2+3 = 5; P4 = 3; P5 = 4+2+1+1+1 = 9

     

     

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

 

SJF.

 

 

  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.

 

  1. Directory names are longer => you need to allow relative as well as absolute path names.
  2. Need to specify search paths though environmental variables for locating files, programs etc
  3. Acyclic graph allows sharing of files between users. But it introduces problems of dangling pointers when files are deleted, and has multiple names for the same object.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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).

 

 

In a linked allocation, the file is a linked list of disk blocks (which may be scattered anywhere). The directory entry points to first and last blocks

Pros: - No external fragmentation

- No need to declare size of file

Cons: - Best only for sequential access. Random access may incur multiple

seeks and traversal through the linked list.

- Overhead for pointer in each block

- Reliability: pointers may be lost or damaged

 

 

FAT: File allocation Table of MS-DOS

 

 

 

 

 

 

 

 

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 ?

 

  1. To allocate a block, we find the first block which has a zero entry; move the EOF value there and point the previous EOF entry to this block.
  2. The FAT improves random access time, because you do the linked list traversal within the FAT itself, and only do one additional disk access to get the particular block.