Study Guide: OS Exam II

Exams are closed book. You can bring one written cheat sheet. 90 minutes in class.

Topics:

  • Tanenbaum Chapters 3,4,5,9

  • Programming with pointer arithmetic; Working with binary files and formats.

  • Memory: Strategies for loading processes into memory, TLB, virtual memory, paging algorithms

  • Files: File system features, such as backups, consistency, and journaling. Methods for storing files/directories and managing free space (inodes, FAT tables, etc)

  • I/O: I/O software layers, drivers, disks, keyboard/mouse input, windows systems

  • Security: Terminology, buffer exploits, basic cryptography, malware, defenses

Tanenbaum

  • Chapter 3: 4, 5, 6, 7, 11, 15, 17, 20, 28, 30, 33, 36, 38, 47

  • Chapter 4: 20, 21, 24, 28, 30, 40, 41

  • Chapter 5: 5, 10, 13, 14, 16

  • Chapter 9: 1, 6, 7, 8, 9, 19, 28, 29, 38, 39, 40, 49, 50

Additional practice

Programming with pointers

  1. For each of the following variables, say whether its a pointer or not

    • char buffer[128];

    • char* a = NULL;

    • const char* message = "hello";

    • char a;

    • struct mystery* m = malloc(sizeof(struct mystery));

    • struct mystery** m = malloc(sizeof(struct mystery*)*10);

    • argv[0] where argv is a list of command line arguments passed to main

  2. In the following code, indicate which casts from void* are safe.

#include <stdio.h>

int main()
{
  void* generic = NULL;
  int a = 3;
  double b = 4.5;
  generic = &a;
  generic = &b;

  printf("test %f\n", *generic);
  double* double_ptr = (double *) generic;
  printf("test %f\n", *double_ptr);

  int* int_ptr = (int *) generic;
  printf("test %d\n", *int_ptr);

  generic = &a;

  double* double_ptr = (double *) generic;
  printf("test %f\n", *double_ptr);

  int* int_ptr = (int *) generic;
  printf("test %d\n", *int_ptr);

  return 0;
}

  1. Draw the stack for the following code.

int main()
{
  char vals[3] = {'h','I','\0'};
  char* valptr = vals;
  char v1 = vals[2];
  char* v1ptr = valptr + 2;
  char v2 = *v1ptr;
  printf("%c %c\n", v1, v2);
  // Draw stack here
  for (int i = 0; i < 3; i++) {
    printf("%c\n", vals[i]);
  }
  for (char* ptr = vals; ptr < vals+3; ptr++) {
    printf("%p %c\n", ptr, *ptr);
  }
}

  1. Draw the stack diagram for the following code

struct chunk {
  int size;
  struct chunk *next;
};
int main() {
  int size = sizeof(int) * 5;
  void *memory = malloc(size + sizeof(struct chunk));
  if (memory == NULL) {
    return 1;
  }
  struct chunk *cnk = (struct chunk*) memory;
  cnk->size = size;
  void* data = (void*) (cnk + 1);
  int* array = (int*) data;
  for (int i = 0; i < 5; i++) {
    array[i] = i;
  }

  1. Suppose the address of x is 0x4c568000. For each of the following expressions, give the new address of x;

    • int* x = &a; x++;

    • `char* x = &c; x-- *

struct m {
    int q;
    char buff[4];
};
struct m* x = &data;
x+=2;

  1. Write code that reads in a binary file with the following specification:

    • The first 4 bytes is an integer that contains the size of the file

    • The second 16 bytes is a character field containing the Author

    • The next three values are unsigned integers that contain a month, day, and year

    • The remaining N bytes store textural data, terminated with the null character.

Memory

  1. Describe the levels of the memory hierarchy.

  2. Name 3 types of secondary storage.

  3. Name 3 types of primary storage.

  4. How do primary storage and secondary storage differ in terms of their characteristics?

  5. Give two disadvantages of a simple process memory model in which the entire process is loaded contiguously in memory?

  6. What is virtual memory?

  7. List two advantages of decoupling the process address space from the machine’s physical memory.

  8. Suppose we are using a 10K blocksize. Give the bitmap that represents the free blocks in memory.

    memory

  9. Suppose we are using a 10K blocksize. Give the linked list that represents the free blocks in memory. Assume each node in the linked list contains the process ID, or H if it a hole, a start location, a size, and a pointer to the next record.

    memory

  10. Fill in the following figure with the bitmap and linked list that corresponds to the given memory block.

    memory free

  11. Suppose we have processes in memory as follows. Suppose a new process requests 15K, which hole should we use if we were using a strategy of best fit, worst fit, and first fit?

    memory

  12. Suppose we are using bitmaps to manage free space for a 1 GB disk. How big must the bitmap be if we use 4 KB blocks? What about if we use 16 KB blocks? What is the disadvantage of using larger blocks?

  13. Suppose we are using linked lists to manage free space for a 1 GB disk. How much additional space do we need if we use 4 KB blocks? What about if we use 16 KB blocks?

  14. What is the memory mapping unit (MMU)?

  15. What is a page? What is a page frame?

  16. What is paging? What is a page fault?

  17. Suppose we have the following specifications: 16-bit addresses, 32 KB of physical memory, and 4KB page sizes.

    • What is the possible range of virtual addresses?

    • How many pages do we have?

    • How many page frames do we have?

  18. Compute physical addresses for the virtual addresses using the commands below.

    paging

  19. Suppose we have 4 KB pages 16-bit addresses. Also suppose our page table looks as follows. Convert the address 0x2004.

    paging 2

  20. What is the translation lookaside buffer? What is its purpose?

  21. Suppose we have 32-bit addresses, 4 KB page sizes, and the a two-level page table. The first 10 bits are an index into the first page table. The next 10 bits are an index into the second page table. Compute the indices into the page tables and offset for the following addresses:

    • 0x00403004

    • 0x00c0500a

  22. What is the advantage of multi-level page tables? What about inverted page tables?

  23. What would the optimal page replacement algorithm be in a perfect world?

  24. In the NRU algorithm, list the 4 categories of pages.

  25. Suppose we execute the following sequence of instructions.

    mov 0x0, reg
mov $0x19, 0x2000
clock interrupt
mov reg, 0x90a3
mov 0x5014, reg

    • Suppose we have 16 pages of virtual memory and 8 pages of physical memory (4 KB page sizes). Which frames will each instruction reference?

    • How will the R and M flags change if all are set the 0 to start?

    • What NRU class is each page in after executing these instructions.

    • What page would be removed by the NRU algorithm?

    • What page would be removed by the FIFO algorithm?

    • What page would be removed by the Second chance algorithm?

    • What page would be removed by the clock algorithm?

    • Suppose we are using LRU. What would the aged values be for each page?

  26. What is the primary limitation of the NFU algorithm?

  27. What is the primary limitation of the FIFO algorithm?

  28. What is the primary limitation of the NRU algorithm?

  29. What is demand paging and why is it efficient?

  30. What is thrashing?

  31. What is the working set?

  32. What does the function w(k,t) represent? Why is w(k,t) monotonically nondecreasing?

  33. Suppose we are using the working set page replacement algorithm. tau = 800 and the current virtual time is 2204.

    Page

    Time of Last use

    R Bit

    M Bit

    7

    2084

    1

    1

    6

    2003

    1

    1

    5

    1980

    1

    0

    4

    1213

    0

    0

    3

    2014

    1

    1

    2

    2020

    1

    1

    1

    2032

    1

    1

    0

    1620

    0

    1

    • Which pages are in the current working set?

    • Which pages would be removed from the page table?

    • Which pages would have its time of last use updated?

    • Suppose we are using the WSClock algorithm and the starting page is page 3. What page will be replaced?

    • Suppose we are using the WSClock algorithm and the starting page is page 3. How will the table change on a clock interrupt?

    • Suppose we are using the WSClock algorithm and the starting page is page 3. How will the table change on a clock interrupt?

Files

  1. What is a file?

  2. What is a file system?

  3. Give some examples of file attributes?

  4. Give two different designs for storing file attributes in a file system.

  5. Give two possible designs for managing free space within a file system.

  6. How does the block size for files possibly affect fragmentation?

  7. What is the root directory? the current working directory?

  8. What is the difference between absolute and relative paths?

  9. Give a possible file system design for a system that has a single-level directory system.

    1. Explain how multiple users might be supported in a single-level file system.

  10. What is a symbolic link?

  11. Describe a possible file system design that supports symbolic links.

  12. Describe the process of booting a computer.

  13. What is the Master Boot Record (MBR)?

  14. What is a partition?

  15. Define internal versus external fragmentation.

  16. List 4 goals of file system design.

  17. Consider the following set of files: A has 2 blocks. B has 5 blocks. C has 1 block. Assume they are stored on a system with 4 KB block sizes. Draw how we would store the files

    1. using contiguous allocation

    2. using linked lists having nodes stored with each block

    3. using a file allocation table (FAT)

    4. using inodes

  18. Consider the following series of commands. Assume the starting current working directory is root. Draw the corresponding file system hierarchy.

$ mkdir B
$ cd B
$ mkdir A
$ touch 6.txt

  1. If we were using inodes, how many inodes would we need to represent the above file system?

  2. Suppose directories store the contents of the directory. Each entry of the table contains the following information: inode id, name (8 bytes), extension (3 bytes), and flags (4 bytes). The least significant bit of flags is 0 for files and 1 for directories. The most significant bit is 1 for a non-empty entry and 0 for an empty entry.

    • Define a struct type that represents the entries inside a directory. Make sure that all data types are properly byte-aligned.

    • Write pseudocode that tests whether a directory entry is valid of not.

    • Write pseudocode that tests whether a directory entry corresponds to a file or directory.

    • Draw the contents of directory B as a table.

    • Describe how you would redesign the directory entries in order to support variable-sized filenames.

      1. Suppose we are using inodes. Describe the steps needed to lookup the file with path /usr/ast/mbox

      2. Suppose we are using FAT. Describe the steps needed to lookup the file with path /usr/ast/mbox

      3. Suppose we are using inodes. Describe the steps needed to lookup the file with path ../ast/mbox

      4. Consider a hierarchical file system. What three things need to happen when a file is deleted?

      5. If a crash occurs while deleting a file, how might the system become in an inconsistent state?

      6. Explain how journaling can help a file system recover from crashes.

      7. Why do journaling systems rely on indempotent actions?

      8. When using disks, why are bigger blocksizes more efficient?

      9. Suppose we are analyzing a disk system for time and size efficiency. The blocksize is 1 MB and the file is 64 KB.

  3. If the disk uses 1 MB per track, has a combined seek and delay time of 9 ms, and a rotation time of 8.33 ms / MB, how much time is needed to fetch the file? (Recall the time = seek + delay + rotation * (k/1MB), where k is the number of bytes).

  4. How much space is wasted?

    1. Suppose we are analyzing a disk system for time and size efficiency. The blocksize is 1 KB and the file is 64 KB.

  5. If the disk uses 1 MB per track, has a combined seek and delay time of 9 ms, and a rotation time of 8.33 ms / MB, how much time is needed to fetch the file? (Recall the time = seek + delay + rotation * (k/1MB), where k is the number of bytes).

  6. How much space is wasted?

    1. What is the difference between soft and hard caps in quota systems.

    2. Why might a quota system be necessary in a multiuser system?

    3. List three challenges of creating a good backup system.

    4. How does an incremental backup work?

    5. List two methods for making backups faster.

    6. What is the difference between a physical and logical dump?

    7. List three limitations of physical dumps.

    8. List the steps needed to created a logical dump.

    9. List the steps needed to restore a logical dump.

    10. How can inodes be checked for inconsistencies?

    11. How can directories be checked for inconsistencies?

    12. Suppose we have an inode based file system for which we are checking for inconsistencies. Is the following system consistent?

      Blocks in use

      1

      1

      0

      1

      1

      0

      Free blocks

      0

      0

      1

      0

      0

      1

    13. Suppose we have an inode based file system for which we are checking for inconsistencies. Is the following system consistent?

      Blocks in use

      1

      0

      0

      2

      1

      0

      Free blocks

      0

      1

      1

      0

      0

      1

    14. Suppose we have an inode based file system for which we are checking for inconsistencies. Is the following system consistent?

      Blocks in use

      1

      0

      0

      1

      1

      0

      Free blocks

      0

      2

      1

      0

      0

      1

    15. Suppose we have an inode based file system for which we are checking for inconsistencies. Is the following system consistent?

      Blocks in use

      1

      0

      0

      1

      1

      0

      Free blocks

      0

      0

      1

      0

      0

      1

    16. A file contains a link count of two. What does this mean?

    17. A file contains a link count of three, but it is only listed in two directories. What problems might result due to this inconsistency?

    18. A file contains a link count of one, but it is listed in two directories. What problems might results due to this inconsistency?

    19. List three features that improve disk read/write performance.

    20. What is a write-through cache?

    21. Suppose we are using caching for a file system in order to increase its performance. What is the risk of writing file blocks infrequently back to disk?

    22. Suppose we are using caching for a file system in order to increase its performance. What is the risk of writing inode blocks infrequently back to disk?

    23. Suppose we are using caching for a file system in order to increase its performance. What is the drawback of writing data back to disk too frequently?

    24. Describe how block read-ahead works.

    25. What is file system defragmentation? When should we use it?

    26. Suppose we have an inode file system with the following properties:

      • Blocksize: 16 bytes

      • 10 direct blocks

      • 4 indirect blocks

      • 1 double-indirect block

      • 1 triple-indirect block

      • Block ids are 4-byte integers

      • sizeof(indode) = 128 bytes

  7. How many block IDS can we store in an indirect block?

  8. What is the max file size we can store using direct blocks?

  9. What is the max file size we can store using indirect blocks?

  10. What is the max file size we can store using double-indirect blocks?

  11. What is the max file size we can store using triple-indirect blocks?

  12. Suppose we have 300 byte file. Sketch a picture of how these blocks would be stored in an inode.

    1. Suppose we are using a FAT for a file system that contains one directory (/) which contains two files: A.txt and B.txt.

      • All directories fit inside a 1 KB block.

      • Suppose the root directory is at block 0

      • Suppose A.txt uses blocks 2, 6, 7

      • Suppose B.txt uses blocks 3, 4, 8

      • Draw the contents of the first 10 FAT entries

      • Draw the contents of the root directory block. Assume the blocks stores the file names and FAT table IDs.

    2. Consider the CP/M file system which stored all files under a single directory. Sketch a program that would format a disk capable of holding 100 files.

      CPM

    3. Suppose a FAT table has 64 entries and the blocksize is 4 KB. What is the maximum number of bytes we can store? What is the maximum possible number of files?

    4. How does the ext2 system initialize files to avoid external fragmentation?

    5. How does the ext2 system arrange blocks to try to improve performance?

IO

  1. Give an example of a block device

  2. Give an example of a character device

  3. What is the difference between block and character devices?

  4. Name the five I/O software layers found in UNIX systems.

  5. Why is I/O organized into layers, e.g. what is the advantage of this approach?

  6. Name the two components of device controllers

  7. Name two types of registers that typically come with hardware devices.

  8. Name two approaches for communicating with devices from the OS.

  9. What is an I/O port?

  10. What is an I/O space?

  11. What is the advantage of using memory-mapped I/O over supporting separate spaces for memory and devices?

  12. What are some challenges/disadvantages of using memory-mapped I/O?

  13. How does the OS communicate with devices when using a separate space for memory and devices?

  14. How does the OS communicate with devices when using memory-mapped I/O?

  15. What is the purpose of Direct Memory Access (DMA)?

  16. In the following diagram, show how the CPU can use a DMA controller to read data from disk storage. (Answer: Fig 5-4 in Tanenbaum)

    DMA

  17. List four steps that happen when an interrupt occurs due to a device event.

  18. List three approaches to I/O handling

  19. Suppose we want to read N bytes from a device. Briefly describe how the following code accomplishes this. What approach is the code taking to event handling?

for (i=0; i<N; i++) {
  while (*status != READY) ;
  *data = buffer[i];
}

  1. What is a device driver?

  2. What is the goal of the device-independent software layer?

  3. Name three different techniques that enable different devices to be accessed in a similar way.

  4. What is buffering? How does buffering relate to I/O?

  5. What is spooling? Give an example of a device that performs spooling.

  6. Consider the five layers of the I/O system. What is the primary functions of the

    • user process layer?

    • device-independent software layer?

    • device drivers?

    • interrupt handlers?

    • hardware?

  7. Why is device independence an important principle of I/O programming?

  8. Why is handling errors as close to the hardware as possible a principle of I/O Programming?

  9. Give an example of how hardware can handle errors without notifying the user.

  10. Give an example of a hardware error that requires reporting an error to the user.

  11. Give an example of how names are used to provide device-independence on UNIX systems.

  12. What is the difference between synchronous and asynchronous transfers of data.

  13. What is the difference between sharable and dedicated devices? Give an example of each.

  14. Give five examples of user-triggered events that are common in graphical user interfaces.

  15. Give five examples of widgets that are common in graphical user interfaces.

Security

  1. In the context of security,

    • what is a vulnerability?

    • what is an exploit?

    • what is a malware?

  2. Describe how a buffer overflow vulnerability can be used as an exploit to call a function.

  3. List three OS/compiler features that make buffer overflow exploits more difficult.

  4. Name three categories of security threats.

  5. Give an example of an application that requires integrity and availability, but not confidentiality.

  6. What is cryptography?

  7. What is software hardening?

  8. What is the difference between a trusted system and a secure system?

  9. What is the principle of least authority?

  10. What is a protection domain?

  11. In the context of protection domains, give an example of an object, a domain, and a right.

  12. Consider the following protection domain.

    ProtectionDomain

    • Represent the protection domains above as protection matrix

    • Represent the protection domains above using an Access Control List

    • Represent the protection domains above using Capabilities. Assume each user is running a single process with the same file needs as the diagram.

    • Why aren’t protection matrices used for storing protection rights?

  13. In the domain of cryptography, what is authentication?

  14. What is Kerckhoff’s Principle?

  15. What major limitation of secret-key cryptography does public-key cryptography solve?

  16. What property does secret-key cryptography have?

  17. What property does public-key cryptography have?

  18. What property does one-way function cryptography have?

  19. Secure Hash Algorithms are an example of one type of cryptographic function?

  20. How does a signature block work for digitally-signed documents?

  21. What is the purpose of a certificate authority? E.g. what problem do they solve?

  22. List 3 basic principles of identity authentication.

  23. Describe how passwords can be stored securely within a system file.

  24. Describe how a leaked password file could be used to break into other systems, even if the password file is encrypted.

  25. What is meant by security through obscurity?

  26. Suppose a system takes stores 8 character passwords. Assume that the password is not a dictionary and contains lowercase letters and digits. How many passwords would we need to test if we use brute force to guess the password. How many passwords would we need to test if we store these passwords with 12 bits of salt. Suppose a 1000 passwords can be tested in 1 second. How long will it take to break this system using brute force?

  27. Give three examples of insider attacks.

  28. What is a botnet?

  29. What is a trojan horse?

  30. What is a drive-by-download?

  31. What is ransomware?

  32. Name five different types of viruses.

  33. Describe how the Morris worm worked.

  34. Why did the Morris worm sometimes bring down computers so they could not be used at all?

  35. What is a rootkit?

  36. Give an example of a rootkit.

  37. What is spyware?

  38. Give some examples of how spyware might modify your computer.

  39. Give 4 examples of defenses against malware.

  40. Sketch code that implements an overwrite virus on a machine in which permissions are not setup correctly for user accounts.