Exam 1

Section I

  1. Consider the following set of processes, with the length of the CPU-burst time given in milliseconds:

Process

Burst Time

Priority

P1

8

3

P2

1

1

P3

2

3

P4

1

4

P5

7

2

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

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

    2. Gantt diagram FCFS:

    P1

    P2

    P3

    P4

    P5

    Gantt diagram SJF:

    P2

    P4

    P3

    P5

    P1

    Gantt diagram non-preemtive priority:

    P2

    P5

    P1

    P3

    P4

    Gantt diagram RR:

    P1

    P2

    P3

    P4

    P5

    P1

    P3

    P5

    P1

    P5

    P1

    P5

    P1

    P5

    P1

    P5

    P1

    P5

    P1

     

  2. What is the turnaround time of each process for each of the scheduling algorithms in part a?

    3. Turnaround times:

    FCFS

    SJF

    Priority

    RR

    P1

    8

    19

    16

    19

    P2

    9

    1

    1

    2

    P3

    11

    4

    18

    7

    P4

    12

    2

    19

    4

    P5

    19

    11

    8

    18

     

  3. What is the waiting time of each process for each of the scheduling algorithms in part a?

    4. Waiting times:

    FCFS

    SJF

    Priority

    RR

    P1

    0

    11

    8

    11

    P2

    8

    0

    0

    1

    P3

    9

    2

    16

    5

    P4

    11

    1

    18

    3

    P5

    12

    4

    1

    11
  4. Which of the schedules in part a. results in the minimal average waiting time (over all processes)?

FCFS

SJF

Priority

RR

Average time

8.0

3.6

8.6

6.2

The schedule with the minimum average waiting time is:

SJF (3.6)

Section II

  1. Discuss the cache mechanism. Try to address at least the following issues:
  1. Describe the cache mechanism.
  2. When are caches useful? Explain.
  3. What problems do they solve? Explain.
  4. What problems do they cause? Explain.
  5. If a cache can be made as large as the device it is caching for (for instance, a cache as large as a disk) why not do so and eliminate the device?

Answer for question 2:

  1. Describe the cache mechanism.

    2. The cache mechanism is a high speed buffer placed in-between two types of memory with different speed characteristics. Examples of cache: processor cache (in-between registers and RAM), disk cache (in-between RAM and disk), etc. Every time a piece of information is required from the slow memory, this piece of information will be stored in the cache memory as well. The idea is that next time the same piece of information will be needed, it will be available in cache and access to the slower memory will not be necessary.

     

  2. Why are caches useful? Explain.

Caches are useful because they can eliminate the need for access to a slower memory device and substitute that with an access to the high speed buffer which is the cache itself.

Caches are useful in practice because programs exhibit "locality" properties. In other words, when an instruction or data is needed, there is a good probability that another piece of information situated in the same memory area will be needed in the near future (keep in mind that most program instructions are executed sequentially i.e. one after another).

 

  1. What problems do they solve? Explain.

    2. Caches allow a system formed with two types of memory (a slow, less expensive one and a fast, more expensive one) to exhibit performances which combine the good characteristics of the two types of memory. In other words, a system with cache will exibit a speed close to the speed of the faster device at a cost close to the cost of the less expensive one.

     

  2. What problems do they cause? Explain.

    3. Coherency and consistency. The same piece of information can be stored in different places at the same time (disk, cache, memory, for instance). Care needs to be taken to make sure that when the information is changed in one place, the change is propagated through the system. More difficulties arise in a multiprocessor environment when many processors could be using the same information at the same time.

     

  3. If a cache can be made as large as the device it is caching for (for instance, a cache as large as a disk) why not do so and eliminate the device?

The device cannot be eliminated because the cache is volatile and expensive.

The main advantage of the cache is that it offers high speed access at low cost per byte. If we substitute the low cost device with high speed, high cost cache, this advantage is lost.

 

Solve ONE problem of your choice between 3 (bounded buffer) and 4 (sleeping barber). One problem is compulsory. If you solve BOTH correctly, you obtain extra credit.

  1. Write a solution for the bounded buffer problem using counting semaphores. The bounded buffer problem involves two processes: a producer and a consumer. The two processes use a finite size buffer to communicate with each other. The producer puts (writes) the items in the buffer; the consumer extracts (reads) them from the same buffer. Assume the buffer has a capacity of N items.
  2. The sleeping barber problem. A barber shop consists of a waiting room with n chairs, and the barber room containing the barber chair. If there are no customers to be served, the barber goes to sleep. If a customer enters the barbershop and all chairs are occupied, then the customer leaves the shop. If the barber is busy but chairs are available, then the customer sits in one of the free chairs. If the barber is asleep, the customer wakes up the barber. Write a program to coordinate the barber and the customers.

 

Solution (bounded buffer):

Shared resources:

object item, buffer[N]

int in, out

semaphore full = 0, empty = n, mutex=1

Pseudo-code:

Producer:

repeat

produce next item

wait( empty )

wait( mutex )

buffer[ in ] = next item

index = in +1 mod n

signal( mutex )

signal( full )

until false

Consumer:

repeat

wait( full )

wait( mutex )

read buffer[ out ]

out = out + 1 mod n

signal( mutex )

signal( empty )

until false

Solution (sleeping barber):

Shared resources:

object chair[ N ],

int customer_counter = 0

semaphore mutex = 1, barber_asleep = 0

Pseudo-code:

Barber:

repeat

wait( barber_asleep ) /* wait if no customers */

wait( mutex ) /* wait if someone is modifying customer_counter */

customer_counter = customer_counter - 1 /* decrement the # of waiting people */

signal( mutex ) /* allow other people to modify customer_counter */

shave customer

until false

Customer

repeat

wait( mutex ) /* wait if someone is modifying customer_counter */

if( customer_counter == n ) then

signal(mutex)

exit

else

sit in chair[ customer_counter +1 mod d ] /* take a sit */

signal( mutex ) /* allow other people to modify customer_counter */

signal( barber_asleep ) /* wake up barber if sleeping */

until false

 

Section III - Multiple choice. Circle the correct answer. There is just one correct answer. If you circle more than one, you will not get any credit for that particular question.

1) A multiuser operating system is an operating system that:

  1. can run several programs at the same time
  2. can accommodate in memory several active processes at the same time
  3. can be used by several users at the same time
  4. can be used by several users at different moments in time
  5. needs the presence of several users to function properly

 

2) A multitasking operating system is an operating system that:

  1. is run on a machine which has several processors
  2. can accommodate in memory several active processes at the same time
  3. can be used by several users at the same time
  4. can be used by several users at different moments in time
  5. needs the presence of several users to function properly

 

3) A time sharing operating system is an operating system that:

  1. can accommodate in memory several active processes at the same time
  2. shares the CPU time between processes using equal time quanta
  3. shares the CPU time between processes using a priority based scheduling system
  4. shares the CPU time between processes using a batch algorithm
  5. shares the CPU time between processes using a random distribution

 

 

 

 

4) The portability of an operating system means that:

  1. the programs which run on the given operating system and some given hardware platform can be run easily on a different operating system on the same hardware platform
  2. the programs which run on the given operating system and some given hardware platform can be run easily on a different operating system on a different hardware platform
  3. the operating system itself can be run easily (after re-compilation) on a different hardware platform
  4. the given operating system can be carried without difficulty from one location to another
  5. the operating system can be used to carry the hardware from one location to another

 

5) A multiuser operating system has to be also:

  1. multitasking
  2. time-sharing
  3. portable
  4. multitasking and portable
  5. multitasking and time-sharing

 

6) A multitasking system has to be:

  1. time-sharing (in the sense of using equal quanta to distribute the CPU time among different processes)
  2. time-sharing (in the sense of using some mechanism for distributing the CPU time among different processes)
  3. portable
  4. run on a multi-processor hardware platform
  5. none of the above

 

 

7) When talking about an operating system, the "kernel" is:

  1. the part which deals with the user interface
  2. the central part, which offers the basic functionality of the operating system
  3. the part which deals with peripheral devices
  4. the central processing unit of the computer
  5. none of the above

 

8) What is the relationship between files and directories:

  1. a file can contain one or more directories and no files
  2. a file can contain one of more other files and no directories
  3. a directory can contain one or more directories and no files
  4. a directory can contain one or more files and directories
  5. a directory can contain one or more files and no directories

 

 

9) An operating system is:

  1. a collection of programs which allow the user(s) to utilize the hardware resources of the computer
  2. a hardware sub-system which groups together those hardware parts of the computer which are essential its functioning
  3. a collection of programs which can be used by programmers through calls from their programs
  4. a specific type of hardware
  5. a collection of programs which deal with the management of the processes which run on a computer

 

10) What are the similarities between a network of personal computers and a mini-computer using a multiuser operating system:

  1. both allow many users to use the same CPU
  2. both allow many users to share the same files if so desired
  3. 1 and 2 at the same time
  4. there are no similarities
  5. there are similarities but they are not mentioned above

 

11) What are the differences between a network of personal computers and a mini-computer using a multiuser operating system:

  1. in a network of personal computers each user runs their programs on the same CPU whereas in a mini-computer each program is run on a different CPU
  2. in a network of personal computers each user runs their programs on different CPU’s whereas in a mini-computer each program is run on the same CPU
  3. a network of personal computers can accommodate more users than a minicomputer using a multiuser operating system
  4. a minicomputer using a multiuser operating system can accommodate more users that a network of personal computers
  5. none of the above

 

Grading:

Problem 1: 100 points

Problem 2: 100 points

Problem 3: 100 points

Problem 4: 100 points

Multiple choice (16 questions): 100 points

Final grade: (P1+P2+P3+P4+P5)/4

Maximum obtainable (if you solve both problem 3 and 4): 125%