NAME________________________________________� ��������������� e-mail (netid)_________________

Prelim 2,� 1:30 hours, Nov 30, 2000.� Please write e-mail address without �cornell.edu� on exam to receive your grade (exam and potential final grade) by e-mail.

 

Memory subsystem and virtual memory:

 

  1. [3 pts] The per process internal fragmentation of a paging system is, on average, equal to:

Half of the size of a page frame

 

  1. [3 pts] Which of the schemes below can be used with first-fit, next-fit, or best-fit algorithms:

Dynamic partitions and segmentation

 

  1. �[3 pts] Which the following memory allocation schemes have poor performance with respect to random reads and writes of files:

Linked

 

  1. Page replacement algorithms
    1. [5 pts] Explain why LRU is a good scheme.

In essence LRU always replaces the page referenced furthest in the past.� This scheme works well if the program adheres to the locality of reference i.e., the accesses tend to be more from the spatially and temporally nearby pages.� This algorithm is also the optimal strategy in reverse and if the past is a good indication of the future this algorithm should work well.� Further, the LRU algorithm does not suffer from Belady�s anamoly.

�

    1. [5 pts] What are the disadvantages of LRU (that is, why isn�t LRU cheap and/or efficient)?

The key disadvantage of LRU algorithm is that it needs a lot of book keeping on each memory access to be implemented exactly.�� After each access the time of the least recently used page must be tracked either using timestamps or counters.� This is highly inefficient and requires sophisticated hardware support.

 

  1. [7 pts] Consider a system with three page frames for user-level applications, and consider the following reference string: 5 6 9 3 5 6 3 6 9 4 3 9 6 4 9.� How many page faults will there be, when one considers FIFO, LRU, and the optimal page replacement algorithms?� The answers below include the initial page faults (those caused when the memory is empty).

If FIFO is used there will be 11 pagefaults.� The accesses would go like this.� 3 page faults initially to have 5, 6, 9 in memory.� Then 5 is replaced by 3, 6 by 5, 9 by 6.� No page faults on 3 and 6.� 3 is replaced by 9,� 5 by 4, and 6 by 3.� No page fault on 9.� 9 is replaced by 6.� No page fault on 4.� 4 is replaced by 9.� Total 11 pagefaults.

If LRU is used there will be 11 pagefaults.�� 3 pagefaults initially to have 5, 6, 9 in memory.� Then 5 is replaced by 3, 6 by 5, 9 by 6.� No page faults on 3 and 6.� 5 is replaced by 9, 3 by 4, and 6 by 3.� No page fault on 9.� 4 is replaced by 6, 3 by 4 and no page fault on 9.� Total 11 page faults.

If OPT is used there will be 7 pagefaults.� 3 pagefaults initially to have 5, 6, 9 in memory.� 9 is replaced by 3.� No page faults on 5, 6, 3, and 6.� 5 is replaced by 9, 6 by 4.� No page faults on 3 and 9.� 3 is replaced by 6.� No page faults on 4 and 9.� Total 7 page faults.

 

  1. Working sets:
    1. [5 pts] Define working set (WS) of a process (include the 2 parameters)

The working set of a process, W(D, t) is the set of pages accessed by the process from the current time t to D time units back.� Where D is a pre-defined amount of time usually measured in terms of virtual time (actual CPU time of� the process, number of instructions etc�)

 

    1. [5 pts] How does one use the WS model to deal with paging and page replacement?� It is a feasible solution?� If yes, explain why; if not, an alternative to WS.

Since the working set denotes the current locality of reference of the process, if we have a good estimate of D then it suffices to have the pages in the working set alone in the memory.� This way we can minimize page faults.� However, the difficulty comes in estimating the window D, which would give the correct locality of reference.� Further this window is dynamic and could vary through the execution of the process.� Alternate schemes such as page fault frequency manages the number of frames allocated to each process more efficiently.

 

 

IO systems

 

  1. [5 pts] Assume that a system has a DMA to perform the block transfers from disk to main memory.� Assume that the disk has finished transferring 1K words of data to the controller memory at time t=0. �At t=0 also, the CPU starts a process that will make sequential memory accesses every other bus cycle (that is, the CPU keeps the bus occupied 50% of the time to read a block of 1K words).� Assume that the memory bus is shared by the CPU, DMA, disk, and memory.� Also assume that only one word can be transferred at a time via the memory bus.� How would you design your system to maximize performance for this very particular case?

All memory accesses of the CPU goes through a cache.� In this case, all the cache needs to do is to pre-fetch 1K words of data upon the first memory access to that block of data.� Once the cache completes its pre-fetch operation, the bus can be granted to the DMA to complete its operation.�



  1. [3 pts] What is the sequence followed by a system when attempting to perform an IO operation?

User does system call � operating system � device controller and device � interrupt handler � operating system � user

 

In questions 9-11, mark (a) TRUE�� (b) FALSE��

  1. [2 pts] All interrupts can be masked by the system (i.e., all devices are prevented from interrupting the CPU). FALSE.� There is a NMI (non maskable interrupt that cannot be masked by the system.)

 

  1. [2 pts] Interrupt handling is efficient because Interrupt Service Routines do not use stacks to execute.� TRUE.

 

 

  1. [2 pts] Interrupt handler is not allowed to disable all interrupts, otherwise the process that was interrupted will never execute again and there will be a deadlock.� FALSE.� The interrupt handlers are allowed to disable interrupts and may in fact need to disable interrupts.� However, the interrupt handlers reside in device drivers or kernel and hence can be ensured to enable interrupts once they are done with their work.

 

 

 

Disk allocation/management and file systems:

In questions 13-17, mark (a) TRUE�� (b) FALSE��

 

  1. [2 pts] The file system is the part of the operating system that handles DMAs.� FALSE.

 

  1. [2 pts] Disk blocks can always be relocated with acceptable overhead, since they are small blocks of data.� FALSE.� It depends on the number of bad disk blocks.�

 

 

  1. [2 pts] RAIDs allow for both fault-tolerance (due to redundancy) and fast access to data on disks, compared with a single disk.� TRUE.

 

  1. [2 pts] Interleaving is done in order to accommodate different densities in the disk inner/outer tracks.� FALSE.

 

 

  1. [2 pts] The organ pipe distribution of data can increase the seek delays of data when compared with FIFO data placement algorithms.� TRUE.� There are specific instances such as when the head has to traverse back and forth from one end of the disk to another, when the organ pipe distribution may not be very good.

 

  1. [3 pts] The temporal overhead of log-based file systems (LFS) is mainly due to:

 

    1. Having to do compaction and garbage collection when the disk is full (regardless of the utilization of the disk)

 

In questions 19-22, let there be 2 sectors in a track and 4 tracks and a single surface in a disk.� Assume the following blocks are accessed by the file system; the notation is 1-digit for block number, and 1 digit for operation (Read, Write, or Append): 1A, 2A, 3A, 4A, 5A, 1R, 1W, 1R.� Assume that all these blocks are accessed for the same file, and that the file�s I-node is initially stored in track 0.� Assume also that all operations immediately go to disk (i.e., there is no buffering/cache in the system), that the head is at track 0, and that the disk is initially empty.� Also assume that the inode occupies the entire track 0 and that each block consists of one sector.� (Remember that for small files, the LFS rewrites the entire file contiguously upon each write (not append) to the disk.)

  1. [5 pts] In log-based file systems (LFS) and write-in-place (that is, �regular�) file systems, how many track movements will there be?� In your answer, if the head moves from track i to track j, it counts as (j-i) or (I-j), whatever is larger.� Formally, it would be (j-i) modulo n, where n is the number of tracks and modulo is the math operand, NOT the mod operation in computer languages.� For example, moving the head from track 4 to track 1 counts as 3 track movements.

25, 5

 

  1. [2 pts] What would the result be if there was a 5-block cache, and the cache replacement was done in a LRU manner?

3, 3

 

operations

1a

2a

3a

4a

5a

1r

1w

1r

total

 

LFS

1

 

1

 

1

2

18

2

25

18 because to write out the entire file, each block has to be read individually (since there is no buffering/cache)

In-place

1

 

1

 

1

2

 

 

5

 

 

 

 

 

 

 

 

 

 

 

 

LFS

1

 

1

 

1

�

�

�

3

Note that to write out the entire file, only 3 tracks are moved.� All ops are done in memory before writing the file.

In-place

1

 

1

 

1

�

 

 

3

 

 

  1. �[4 pts] What is the optimal file system structure for this particular set of accesses (mention the scheduling algorithm and the data placement algorithm you would use).

The key operations in this case are appends and then a few random access reads and writes.� We know that the indexed file system is pretty good for this case.� The linked system is OK as long as we assume that only block 1 is going to be accessed but if any other block is read or written, the linked system is futile.� The contiguous system is not good because of many append operations.� The best data placement would be organ pipe placement with the index block closest to the disk head in the middle and block 1 as close to the disk head as possible.�

 

Networking:

  1. In packet switched networks, the lowest three layers are the ones responsible for the routing of packets.� These layers are typically implemented in specialized nodes, called routers.� Typically, operating systems in routers are not general-purposed OSs, so that the parts of the OS that are not needed (e.g., the file systems) are not included, reducing the code size, complexity, and increasing efficiency.�

 

    1. [5 pts] What are the names of the lower three layers of the ISO protocol stack?� What is the processing that occurs in these lower three layers?��� If you do not know the three layers, you can ask a proctor (proctor will mark your exam saying s/he gave you this piece of the answer).

Physical layer:� Consists of the actual communication medium such as optic fibres, cable, etc�

Data Link Layer:� Takes care of getting the packets through the physical medium.� Also does error correction, flow control and manages media access or channel access.

Network Layer:� This layer is responsible for getting messages from one end machine to another end machine.� It has addresses associated with machines.� Does routing, and fragmentation (in case it has to split packets to go through� section of the route.)

 

    1. [5 pts] What type of hardware can the OS take advantage of, in order to make the processing in the lower three layers more efficient?� Include the changes you would make, if any, in the protocol, layers, organization, etc.

The lower three layers usually are implemented on a hardware called the network interface controller.� Having the NIC to have a processor in it makes it real smart and a number of operations such as error correction (CRC check), calculating routes, processing headers, etc� can be done in hardware.� Having a big cache to store the frequently used routing information also helps a lot.� Having DMA access between the memory and the NIC is very useful.� Physical media that can provide multicast abilities is also very useful.

 

In questions 22-25, mark (a) TRUE�� or��� (b) FALSE�� ��[2 pts each for questions 22-25]

 

Advantages

Disadvantages

Fully connected network

 

 

22. Most reliable TRUE

23. Highest communication costs FALSE

Bus-based network

 

 

24. Highest delays FALSE

25. One failure will cripple the network� TRUE