CS1550 Final exam sample Questions/ Study guide
These questions are intended to cover the kind of questions that may be asked about the material we covered. It is not intended as a comprehensive review, and is not representative of the final exam length.
I/O Questions
I can fill my backpack with about 20 HDs, each holding 1TB of data. If I can ride my bike from Sennott Square to the Cathedral of Learning in 3 minutes … what is the bandwidth of my backpack on my bike?
Why are SSDs preferred for laptops over hard drives? What are the trade-offs?
What changes are needed in the OS file system to optimize the use of SSDs that are not needed for Hard Drives?
Why must disk sectors vary in physical length (not storage capacity)
What is sector interleaving? And why was it invented? Is it still needed?
A disk has 200 cylinders. The head is currently over cylinder 20 heading outwards (towards higher numbered cylinders). A time t=0 we have a queue of requests for blocks on different cylinders: 25, 36, 28, 124, 56, 18, 178, 236. List the order in which the cylinders will be visited using:
• SCAN
• C-Look
• If we assume moving X cylinders required X units of time, then how long will it take to visit all cylinders using SSTF
Disk scheduling is important since it tries to decrease
a. the seek time b. the polling time
c. the rotational delay d. the transfer time
Contiguous file systems suffer from similar problems as (in mem mgmt)
a. static partitions b. dynamic partitions
c. paging d. none of the above
Aging is one of the techniques through which starvation is avoided in disks. FALSE
Aging in disks interacts is implemented when aging in CPU scheduling is implemented (ie, they’re dependent on each other). FALSE
Q: list the three main delays in getting data from disk, in increasing average delays (or increasing importance, since the more delay, the more important it is)
A: transfer delay, rotational delay, seek delay.
Q: What does the acronym DMA stand for? Describe what is the advantage of a system that has a DMA over a system that has no DMA
A: Direct Memory Access: in a system with DMA, the CPU can run applications without being involved in the transfer of data from a device to main memory.
Q: If all subcomponents of a system use the bus to get data from memory and the CPU needs data from memory to run the application, why does using a DMA allow for higher performance?
A: after a chunk of memory was read (say 4KB) into cache, the CPU will not read anything from memory until a cache miss was detected.
Q: Describe the organ-pipe distribution and mention why it is a good tool increase the performance of disks.
A: This block allocation strategy places the most used blocks of data close together in order to reduce the seek time, which is the highest delay in disk performance. The organ-pipe distribution uses a histogram and allowing the most used blocks of data to be in the same track (say track n/2), the next most used blocks in the next tracks (to the right n/2-1 and to then to the left n/2+1), then n/2+2, n/2-2, …
Q: what is the sequence of software layers that are traversed from the time a user needs to read a disk block until the time the data is available to the user (from library call to the return from the library call). among the layers are:
a) libraries, b) page replacement algorithms. c) ISRs, d) Device-independent OS software, e) data placement algorithms, f) de-framentation software, g) device drivers, h) controllers, i) device itself
A: libraries Device-independent OS software device drivers controller device ISR device drivers Device-independent OS software libraries.
Q: Let there be the following requests for data blocks in tracks number 100, 175, 51, 133, 8, 140, 73, and 77 and let the head position be in track number 63. What is the number of tracks that will be traversed with the following disk scheduling algorithms (answer only those that make sense):
a) FIFO A: 646 tracks
b) LIFO A: 623 tracks
c) LRU
d) second chance
A: c) and d) are page replacement algorithms, not disk scheduling
e) SCAN A: 238 tracks
f) C-Look A: 322 tracks
Q: what is and what is the main shortcomings of the SSTF disk scheduling algorithm?
A: shortest seek time first algorithm looks at the queue of requests and gives highest priority to the request with the shortest seek time (that is, closest track to the current position of the read-write head). it may starve some requests when requests are arriving dynamically
File System Questions
An example disk has 500-byte sectors, and a total capacity of 100MB. All tracks have 100 sectors. It spins at 6000 rpm, and a complete track can be read in 2 revolutions.
• How many tracks are on this disk?
• How fast can data be read off the disk surface (give an upper limit)?
• If we use a file-system with 4-sectors per block, how many bits are needed for a sector pointer?
• Given your answer to part c), and assuming file names can be up to 200 characters long, then how many direct pointers can be held in a single i-node, if an i-node is exactly 1 file-system block in size?
If we use a contiguous file allocation, can we read the entire contents of a file faster/slower than if we use index-nodes? Faster, given that we don’t have to read the i-node for the file, AND usually contiguous allocations are on the same track (minimizes seek delay/time)
If files are all exactly 10KB in size, and we use 4KB file system blocks, what is the percentage of disk space lost to internal fragmentation. 2/12
In a log-structured file system, when do you expect a file to be moved on disk (i.e. moved from one set of sectors to a new set of sectors)?
In a log-structured file system, what happens when a file needs to grow (i.e. more disk blocks)? Does the the file system copy the entire file?
Intelliseek is a smart algorithm to minimize _____. It also minimizes ______.
What is a good reason to use SSDs as cache for hard drives?
What is a bad reason to use SSDs as cache for memory?
What is a bad reason to use SSDs as main memory?
More IO systems
• [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.
• [3 pts] What is the sequence of events that happen at the completion of an IO operation? Start at the device.
Device device controller interrupt handler device driver operating system (unblock process) user process resumes
In the following questions, mark (a) TRUE or (b) FALSE
• [2 pts] All IO interrupts can be masked by the system (i.e., IO devices can be prevented from interrupting the CPU). TRUE
• An interrupt controller (PIC) arbitrates among interrupts. If an interrupt is being handled:
• [2 pts] Higher priority interrupts are only able to be executed after the current interrupt is done. FALSE
• [2 pts] Interrupts at the same priority are able execute immediately. FALSE
• [2 pts] Interleaving is done in order to accommodate different densities in the disk inner/outer tracks. FALSE.
• [2 pts] Copy on write is a mechanism implemented in the OS for fast writing of pages from memory onto disk. FALSE.
• Directories are typically organized as lists, but can also be organized as trees, usually for faster access. TRUE
SHORT-ANSWER QUESTIONS
• [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.
More Disk allocation/management and file systems:
In the following questions, mark (a) TRUE or (b) FALSE
• [2 pts] The interrupt service routine is the part of the operating system that handles DMAs. FALSE.
• [2 pts] Disk blocks can always be relocated (like the organ pipe distribution or other dynamic rearrangement of data) at any time with acceptable overhead, since they are small blocks of data. FALSE. It depends on the number of disk blocks being moved.
• [2 pts] RAIDs allow for both fault tolerance (due to redundancy) and fast access to data on disks, compared with a single disk. TRUE.
SHORT ANSWERS
• [4 pts] Give an example where the organ pipe distribution of data increases the seek delays when compared with FIFO data placement algorithms. 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.
• [3 pts] The temporal overhead of log-based file systems (LFS) is mainly due to:
Having to do compaction and garbage collection when the disk is full (regardless of the utilization of the disk)
LONG ANSWER
• [10 pts] What is an extent and what is it used for?
• Calculate the expected access time for reading an entire 50 KB file, for a 5 MB disk, with 512B disk blocks, given the following:
• Indexed allocation
• Indexed allocation, if the bitmap is not stored on this disk.
• Continuous allocation
• [10 pts] Let there be a user whose main file system usage is constantly (a) listening to MP3s (legal, of course!), (b) browsing the web, and (c) sending/receiving emails. Every message and every webpage (all files) get cached in the local disk. Cached files for web browsing are deleted periodically (every T time units).
• Create two designs for this user’s file system (the best one you can think of, and another one);
• describe what type of file system structure, the type of file allocation strategy, and the disk scheduling algorithm you would use.
• Compare your two designs showing advantages of each design (hopefully your “best” design will have more advantages than your “other” design!)
Dedicate some buffers for caching the MP3 tracks and prefetch them. Rearrangment of disk blocks to allow for whole tracks to be dedicated to MP3s is a good idea. Index allocation due to the frequency of request that are not sequential reads/writes (like the web and email requests). Disk scheduling should be any SCAN or LOOK or elevator algorithms. Just no FIFO.
Bonus points for people who say that they’ll have two queues and will put the MP3 requests in higher-priority queue.
Alternative design: anything goes 🙂
Security Questions (not for spring 2020 final exam)
Describe the “write-up” philosophy for security, and give a short rationale for it.
Give the formula for the maximum number of attempts for a brute force password attack (ie, trying to guess the password of a user). State your assumptions.
Give an example of covert channels. Give another example of covert channels.
Give an example of steganography. Give another example of steganography.
Public-key cryptography can be used to confidentially exchange information between two parties. Describe how this would be done.
How does PGP (pretty good privacy) work?
What is a one-way hash? Name two well-known algorithms for producing one-way hashes … and state the size of the resulting hash produced by each (is it a fixed size?).
What are ways to slow down hackers that are trying to log in through bots without knowing the password a priori?