4003-440-02 Operating Systems I
Selected Exercises

Module 1. OS Structures
Module 2. Process Management
Module 3. Thread Programming
Module 4. Thread Coordination
Module 5. Concurrent Design Issues
Module 6. Process Programming
Module 7. CPU Scheduling
Module 8. Memory Management
Module 9. Memory Allocation
Module 10. File Systems and Disks
Module 11. Parallel and Distributed Systems

Module 1. OS Structures

Required reading

• Module 1 Lecture Notes
• Silberschatz, Chapters 1, 2
• Article: "Can we make operating systems reliable and secure?"

Exercises

1. A computer has a CPU, one level of cache memory, and a main memory. The cache size is 1 megabyte (1 megabyte = 2²⁰ bytes). The cache is organized into cache lines of 32 bytes. It takes 10 nanoseconds (1 nanosecond = 10^-9 seconds) to transfer one byte of data from the cache. The main memory size is 256 megabytes. It takes 100 nanoseconds to transfer one byte of data from the main memory. The computer executes a 2-megabyte program that contains absolutely no branch instructions, just straight-line code. Furthermore, the program uses only the CPU registers and does not read or write any data in memory. When the program starts, the cache is empty.
    
   1. What is the cache hit ratio for this program?
       
   2. How much time does it take to transfer all the program instructions from memory to the CPU?
       
   3. Suppose the cache memory is eliminated and the CPU is connected directly to the main memory. Now how much time does it take to transfer all the program instructions from memory to the CPU?
       
   4. A cache memory is supposed to speed up program execution. Did it in this example? If not, why not?
       
2. Every job in a certain computer system executes as follows. The job does computations with no I/O for 100 microseconds (1 microsecond = 10^-6 seconds). The job then does an I/O operation and must wait 1 millisecond (1 millisecond = 10^-3 seconds) for the I/O to complete before proceeding. The job does 1,000 iterations of this computation-I/O cycle, then it stops.
    
   1. The computer's operating system does not support multiprogramming. How long does it take to run one job? two jobs? five jobs? (All jobs enter the system at the same time. Ignore any overhead apart from the job execution time.)
       
   2. The computer's operating system supports multiprogramming. How long does it take to run one job? two jobs? five jobs? (All jobs enter the system at the same time. Ignore any overhead apart from the job execution time.)
       
   3. In the multiprogrammed operating system, how many jobs are needed to ensure the CPU is never idle waiting for I/O to finish?
       
   4. Explain why multiprogramming is A Good Thing.
       
3. In a certain computer it takes 500 nanoseconds (1 nanosecond = 10^-9 seconds) to do a hardware context switch in response to an interrupt or to return from an interrupt. The computer's timer triggers an interrupt 100 times a second. The operating system's timer interrupt handler routine takes 20 microseconds (1 microsecond = 10^-6 seconds) to execute. What fraction of the time does the system spend dealing with timer interrupts?

Solutions (password required)

Module 2. Process Management

Required reading

• Module 2 Lecture Notes
• Silberschatz, Chapters 3, 4

Exercises

1. Silberschatz, Chapter 3, Exercise 3.9.
    
2. Silberschatz, Chapter 3, Exercise 3.10.
    
3. Silberschatz, Chapter 3, Exercise 3.13.
    
4. A command interpreter program or shell, such as csh or bash, runs each command in its own separate process. Normally, after the user types a command, the command prompt will not be displayed until after the command has run. However, if the user ends a command with an ampersand (&), the command prompt will be displayed immediately. On a Unix system, which system calls does the shell have to do to run a command? What does the shell have to do differently if the user ends a command with &?
    
5. Every process in a certain computer system executes as follows. The process does computations with no I/O for 100 microseconds (1 microsecond = 10^-6 seconds). The process then does an I/O operation and must wait 1 millisecond (1 millisecond = 10^-3 seconds) for the I/O to complete before proceeding. Each process repeats this computation-I/O cycle forever. There are 20 processes in the system. The operating system's scheduler works as follows. When the scheduler needs to run a different process, the scheduler takes the process at the front of the ready queue. When a process becomes ready to execute, the scheduler places the process at the end of the ready queue. After the system has run for a while, how many processes will be in the ready queue? In the I/O wait queue? What fraction of the time will a process spend in each of the process states? (All processes start at the same time. Ignore any overhead apart from the process execution time.)
    
6. Silberschatz, Chapter 4, Exercise 4.9.
    
7. Silberschatz, Chapter 4, Exercise 4.10.
    
8. Silberschatz, Chapter 4, Exercise 4.11.
    
9. Silberschatz, Chapter 4, Exercise 4.13.
    
10. A certain program uses a thread pool. When the program tells the thread pool to run a task in a separate thread, the thread pool reuses an existing idle thread if possible, otherwise the thread pool creates and uses a new thread. Once a thread has finished running a task, the thread goes back into the thread pool as an idle thread. The program runs 50 tasks in sequence. Each task starts 50 milliseconds (1 millisecond = 10^-3 seconds) after the previous task started. Each task finishes 1 second after it starts. After all the tasks have finished, how many idle threads will be sitting in the thread pool? (Ignore any overhead apart from the task execution time.)

Solutions (password required)

Module 3. Thread Programming

Required reading

• Module 3 Lecture Notes

Exercises

In Java, a thread can be programmed either as a subclass of class Thread or as a class that implements interface Runnable. Give reasons one might prefer to use each technique.
 
1. A Java program has four threads. Each thread prints the message "Hello, world from thread <i>!" on the standard output, where "<i>" is replaced by the thread number (1-4). Write three different versions of this program, using three different techniques to create and run the threads.
    
2. Professor K assigned the previous program for course credit. The professor's goal is to automate grading the student's projects by doing a diff between the program's output and the correct output (stored in a file). If there are no differences, the project gets a 100, otherwise the project gets a 0. Will Professor K be able to achieve this goal? Explain why or why not.

Solutions (password required)

Module 4. Thread Coordination

Required reading

• Module 4 Lecture Notes
• Silberschatz, Chapter 6

Exercises

1. Silberschatz, Chapter 6, Practice Exercise 6.2.
    
2. Silberschatz, Chapter 6, Exercise 6.17.
    
3. Silberschatz, Chapter 6, Exercise 6.18.
    
4. Silberschatz, Chapter 6, Exercise 6.25.
    
5. Silberschatz, Chapter 6, Exercise 6.28. (Write a pseudocode monitor.)
    
6. Silberschatz, Chapter 6, Exercise 6.29. (Write a pseudocode monitor.)
    
7. Silberschatz, Chapter 6, Exercise 6.32. (Write a pseudocode monitor.)
    
8. Silberschatz, Chapter 6, Programming Problem 6.39. (Write a pseudocode program.)
    
9. The Java Virtual Machine guarantees that reading the value of an int variable is an atomic operation and assigning a value to an int variable is an atomic operation. Consider this class:

   public class SharedInteger
       {
       private int value;
   
       public synchronized int get()
           {
           return value;
           }
   
       public synchronized void set
           (int value)
           {
           this.value = value;
           }
   
       public synchronized void add
           (int value)
           {
           this.value = this.value + value;
           }
       }
   

   In order for a SharedInteger object to be used by multiple threads, is it necessary for every one of the above methods to be synchronized? Which methods have to be synchronized and which methods need not be synchronized? Explain why. What would be the advantage of having certain methods unsynchronized (if that is possible)?
    
10. Curiously, the Java Virtual Machine does not guarantee that reading or assigning a long or double variable is an atomic operation. Why is that? (Hint: Think about the size of such a variable compared to the word size of the typical CPU.)

Solutions (password required)

Module 5. Concurrent Design Issues

Required reading

• Module 5 Lecture Notes
• Silberschatz, Chapter 7

Exercises

1. Silberschatz, Chapter 7, Practice Exercise 7.3.
    
2. Silberschatz, Chapter 7, Exercise 7.10.
    
3. Silberschatz, Chapter 7, Exercise 7.11.
    
4. Silberschatz, Chapter 7, Exercise 7.15.
    
5. Silberschatz, Chapter 7, Exercise 7.17.
    
6. Silberschatz, Chapter 7, Exercise 7.20.
    
7. Silberschatz, Chapter 7, Exercise 7.21.
    
   Questions 8-9. An old-fashioned data center has four computers sharing six magnetic tape drives. The data center is running four applications concurrently, one application on each computer. Each application requires exclusive use of certain tape drives. Each application acquires its tape drives in the order given below.
   • Application A -- Tape drives 1, 3, 4
   • Application B -- Tape drives 4, 2
   • Application C -- Tape drives 3, 5
   • Application D -- Tape drives 6, 2, 1
   If a tape drive is not available, the application waits until the tape drive is available, then the application acquires the tape drive and proceeds. Once the application has acquired all its tape drives, the application performs a computation using the data stored on the tapes, then the application releases all its tape drives.
    
8. Is it possible for the data center to get into a deadlock? If so, give a sequence of events that leads to a deadlock. If not, explain why a deadlock is impossible.
    
9. If the data center can get into a deadlock, describe how would you change the applications to make deadlock impossible. If the data center cannot get into a deadlock, describe how would you change the applications to make a deadlock possible.

Solutions (password required)

Module 6. Process Programming

Required reading

• Module 6 Lecture Notes

Exercises

1. The user types the following command to the shell:

       cat file | tr -s -c '[:alpha:]' '[\n*]' | tr '[:upper:]' '[:lower:]' | sort -u | wc -l
   

   The shell runs each individual command in its own process. How many calls to pipe(), fork(), and exec() must occur?
    
2. Here's one way the shell could run the commands. The shell forks a process, and the new process execs the first command (cat). The shell forks another process, and the new process execs the second command (tr). And so on, until all the commands are running. Draw a diagram showing each process including the shell, with an arrow pointing from each process to its parent.
    
3. In Question 2, what has to happen to prevent the shell from going on to the next user command until all the commands have finished?
    
4. Here's another way the shell could run the commands. The shell forks a process, and the new process execs the first command (cat). The shell forks another process, and the new process execs a new shell with a command line argument telling the new shell to run the rest of the user's command except for cat. And so on, until all the commands are running. Draw a diagram showing each process including the shell, with an arrow pointing from each process to its parent.
    
5. In Question 4, what has to happen to prevent the shell from going on to the next user command until all the commands have finished?
    
6. If you were writing the shell program, which approach would you use? Explain why.
    
7. Describe what the command in Question 1 does.

Solutions (password required)

Module 7. CPU Scheduling

Required reading

• Module 7 Lecture Notes
• Silberschatz, Chapter 5

Exercises

1. Silberschatz, Chapter 5, Practice Exercise 5.1.
    
2. Silberschatz, Chapter 5, Practice Exercise 5.3.
    
3. Silberschatz, Chapter 5, Exercise 5.9.
    
4. Silberschatz, Chapter 5, Exercise 5.11.
    
5. Silberschatz, Chapter 5, Exercise 5.12.
    
6. Silberschatz, Chapter 5, Exercise 5.13.
    
7. Silberschatz, Chapter 5, Exercise 5.15.
    
8. Silberschatz, Chapter 5, Exercise 5.16.
    
9. Silberschatz, Chapter 5, Exercise 5.19.
    
10. Silberschatz, Chapter 5, Exercise 5.20.
     
11. Silberschatz, Chapter 5, Exercise 5.21.

Solutions (password required)

Module 8. Memory Management

Required reading

• Module 8 Lecture Notes
• Memory Trace Analysis
• Silberschatz, Chapters 8, 9

Exercises

1. Silberschatz, Chapter 8, Practice Exercise 8.4.
    
2. Silberschatz, Chapter 8, Practice Exercise 8.6.
    
3. Silberschatz, Chapter 8, Exercise 8.11.
    
4. Silberschatz, Chapter 8, Exercise 8.12.
    
5. Silberschatz, Chapter 8, Exercise 8.14.
    
6. Silberschatz, Chapter 8, Exercise 8.15.
    
7. Silberschatz, Chapter 8, Exercise 8.16.
    
8. Silberschatz, Chapter 8, Exercise 8.17.
    
9. Silberschatz, Chapter 8, Exercise 8.18.
    
10. Silberschatz, Chapter 8, Exercise 8.19.
     
11. Silberschatz, Chapter 8, Exercise 8.20.
     
12. Silberschatz, Chapter 8, Exercise 8.21.
     
13. Silberschatz, Chapter 8, Exercise 8.23.
     
14. Silberschatz, Chapter 8, Exercise 8.24.
     
15. Silberschatz, Chapter 8, Exercise 8.25.
     
16. A certain computer uses paging. Addresses are 32 bits long, and each page contains 1,024 addresses. The page table contains the following entries (all numbers are in decimal):
     

    Page #		Page Frame #
    0		22
    1		7
    2		32
    3		17
    4		51
    5		53
    6		41
    7		57
    . . .		. . .

    
    What is the physical address corresponding to each of the following logical addresses? Give the addresses in decimal.
     
    1. 1107
    2. 906
    3. 4870
    4. 7191
    5. 6601
        
    What is the logical address corresponding to each of the following physical addresses? Give the addresses in decimal.
     
    6. 33214
    7. 22824
    8. 8020
    9. 52609
    10. 42490
         
17. Silberschatz, Chapter 9, Practice Exercise 9.7.
     
18. Silberschatz, Chapter 9, Practice Exercise 9.8.
     
19. Silberschatz, Chapter 9, Exercise 9.15.
     
20. Silberschatz, Chapter 9, Exercise 9.20.
     
21. Silberschatz, Chapter 9, Exercise 9.21.
     
22. Silberschatz, Chapter 9, Exercise 9.23.
     
23. Silberschatz, Chapter 9, Exercise 9.29.
     
24. Silberschatz, Chapter 9, Exercise 9.32.
     
25. Silberschatz, Chapter 9, Exercise 9.33.
     
26. Silberschatz, Chapter 9, Exercise 9.34.
     
27. Consider the sequence of page references in Figure 9.20 (page 389). The operating system uses demand paged virtual memory and allocates at most 4 page frames to each process. Give the number of page faults and the page miss ratio for each of the following page replacement algorithms. Also state which page replacement algorithm (other than OPT) gives the best performance.
     
    1. OPT.
    2. LRU.
    3. FIFO.
    4. Second chance.

Solutions (password required)

Module 9. Memory Allocation

Required reading

• Module 9 Lecture Notes
• Heaps and Garbage Collection
• Silberschatz, Chapter 9, Section 9.8

Exercises

1. Silberschatz, Chapter 9, Exercise 9.36.

Solutions (password required)

Module 10. File Systems and Disks

Required reading

• Module 10 Lecture Notes
• Silberschatz, Chapters 10, 11, 12

Exercises

1. A computer uses the Linux ext2 filesystem with 1,024-byte disk blocks. For each of the following file sizes, state how many disk blocks are needed for the file's contents, state how many disk blocks are needed to hold indirect pointers (not counting the inode), and state the overhead fraction for the indirect pointers.
    
   1. 10,464 bytes.
   2. 98,765 bytes.
   3. 220,057,435 bytes.
       
2. Silberschatz, Chapter 12, Exercise 12.16.
    
3. Silberschatz, Chapter 12, Exercise 12.17.
    
4. Silberschatz, Chapter 12, Exercise 12.18.
    
5. Silberschatz, Chapter 12, Exercise 12.33.
    
6. Silberschatz, Chapter 12, Exercise 12.35.

Solutions (password required)

Module 11. Parallel and Distributed Systems

Required reading

• Module 11 Lecture Notes
• Silberschatz, Chapters 16, 18

Exercises

1. You have made the following measurements of running time T (msec) versus number of processors K for a certain parallel program solving a problem with a fixed problem size N:

   K      T
   1  14000
   2   7560
   3   5413
   4   4340
   

   1. What fraction of this program's total running time must be performed sequentially?

   2. What would the program's running time be for K = 5 processors?

   3. What are the program's speedup and efficiency for K = 1, 2, 3, 4, and 5 processors?

   4. What is the maximum speedup you can expect from this program as K increases while holding N fixed?

2. A weather prediction program divides a three-dimensional region of the Earth's surface and atmosphere measuring 1 kilometer (width) × 1 kilometer (length) × 1 kilometer (height) into a 1000×1000×1000 grid of cells, each cell representing a cube 1 meter on a side. The program simulates a time span of 24 hours; the program divides this time span into 1440 time steps, each time step representing 1 minute. The program takes 1 hour to run on a single processor. The program is now to be run on a 16-processor parallel computer while still calculating the same three-dimensional region for the same total (simulated) time span.

   1. Under ideal conditions, what would the grid cell size, time step size, and total running time be if strong scaling is used?

   2. Under ideal conditions, what would the grid cell size, time step size, and total running time be if weak scaling is used?

   3. Which would give a more accurate weather prediction, strong scaling or weak scaling? Explain.

3. The above weather prediction program (with the original grid) is run on an SMP parallel computer with 16×10⁹ bytes of memory available to store the grid. Each grid cell requires 8 bytes of data.

   1. How much memory does the program require to store the whole grid?

   2. You want to increase the number of cells in the grid from 1000×1000×1000 to N×N×N. How large can the grid dimension N become on this SMP parallel computer?

   3. You want to increase the number of cells in the grid from 1000×1000×1000 to 4000×4000×4000, and run the program on a cluster parallel computer in which each node has 16×10⁹ bytes of memory available to store the grid. How many nodes must there be in the cluster?

4. A certain GPU parallel program with a certain input data set is run on a previous-generation NVIDIA Tesla C2075 accelerator with 448 cores. The identical program with the identical input data set is then run on a next-generation NVIDIA Tesla K20 accelerator with 2496 cores.

   1. What kind of scaling is this? Explain.

   2. The K20 cores are 3 times faster than the C2075 cores. All else being equal, what would the program's speedup be running on the K20 as compared to running on the C2075?

5. The DES block cipher uses a 56-bit key. A brute force attack on DES requires performing the encryption function 2⁵⁶ times. The world's fastest supercomputer, the Sequoia computer at the Lawrence Livermore National Laboratory, Livermore, CA, USA, has 1572864 cores. Assume that one core can perform the encryption function in one microsecond (1×10⁻⁶ seconds). Assume an ideal speedup. How long will it take the Sequoia computer to perform the brute force attack on DES?

6. Twelve nodes have joined a peer-to-peer system that uses the Chord distributed hash table. The system uses hash values in the range 0-127. The node names and the node identifier hash values are:

   A     B     C     D     E     F     G     H     I     J     K     L
   103   80    100   20    17    5     72    71    121   70    35    50
   

   1. Draw a picture of the Chord ring, showing each node A through L in its proper position on the ring.

   2. Give the finger table for node L.

   3. A key X is added to the distributed hash table. The hash of X is 122. On which node (A through L) will X be stored?

   4. A user tells node D to do a query for key X. To which node(s) will the query be forwarded?

7. A very large database is split into chunks, and the chunks are stored separately on the nodes of a cluster. Each chunk has a numerical ID. For purposes of integrity checking, we want to compute the digest of the database using the SHA-1 hash function. The hash function takes an input of any size and outputs a fixed-size 160-bit digest. We want to compute the database's digest using a tree hash:
   

   The digest of each database chunk is computed; these digests are all concatenated together, in ascending order of the chunk IDs; the digest of the concatenation is computed; and that is the digest of the whole database. We want to use map-reduce to compute the database digest.

   1. Describe what the mapper input(s) are, describe what the mapper computation does, and describe what the mapper output(s) are.

   2. Describe what the reducer input(s) are, describe what the reducer computation does, and describe what the reducer output(s) are.

   3. Justify why we want to use map-reduce to compute the database digest.

Solutions (password required)

Operating Systems I • 4003-440-02 • Winter Quarter 2012

Course Page

Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706

Home Page

Copyright © 2013 Alan Kaminsky. All rights reserved. Last updated 13-Feb-2013. Please send comments to ark­@­cs.rit.edu.