Checklist - Final

Here is a general outline of the key concepts (arranged by topic) that you should know for the Final.

The exam will have the following format:

  1. Definitions: Briefly define terms using one or two sentences.

  2. Long Answers:

    • Virtualization

      • Virtual Memory

    • Concurrency

      • Threads

    • Persistence

      • File System

The exam is completely offline. This means there will not be any need for a computer. Furthermore, the test is closed book, closed notes, but open mind.

Furthermore, the exam is also comprehensive. This means there may be questions from the first part of the semester as well. Refer to the Midterm Checklist for possible topics and questions.

Representative, but not Exhaustive

This check list is meant to be representative, rather than exhaustive (ie. there may be questions that show up on the exam that are not shown below).

Terms

Memory

Address Spaces

  1. What is an address space?

  2. What is virtual memory?

  3. How do we allocate memory?

  4. What are some common memory errors?

Free-Space Management

  1. Who needs to keep track of memory?

  2. What data structures do we use to keep track of memory?

  3. What are some strategies for managing memory?

Segmentation

  1. What are the problems with base and bounds?

  2. How does segmentation address these problems?

  3. How do we translate a virtual address to a physical address?

Paging

  1. How does paging address the problems in segmentation?

  2. What exactly is a page? page frame? page table?

  3. How do we translate a virtual address to a physical address?

TLB, Multi-Level Page Tables

  1. What problem do TLBs address and how do they solve it?

  2. What problem do multi-level page tables address and how do they solve it?

Swapping

  1. How does the operating system provide the illusion of infinite virtual memory?

  2. How does the operating system handle page faults?

  3. What exactly is thrashing?

Filesystems

I/O Devices

  1. What is the challenge of persistence?

  2. How does the operating system mediate data transfers between the CPU and disk storage?

  3. What are the advantages and disadvantages of hard disks versus solid state drives?

RAID

  1. What problems does RAID address?

  2. What different types of RAID are there and what are the advantages and disadvantages of each?

File Systems

  1. How is a typical Unix file system organized?

  2. What exactly is an inode?

  3. How are blocks allocated?

  4. Why does the OS use up all your RAM?

FFS, LFS

  1. What problem does FFS solve and how does it solve it?

  2. What problem does LFS solve and how does it solve it?

Consistency and Integrity

  1. What is the problem of crash consistency and how do file systems deal with it?

  2. What is the problem of data integrity and how do file systems deal with it?

Sample Questions

  1. Given a virtual memory system with the following properties:

    • 14-bit Virtual Address
    • 16-bit Physical Address

    • 64 byte Pages

    Sketch all the data structures needed to support a multi-level paged virtual memory system. Be sure to include all the tables in memory, and clearly indicate the total size of each table, the number of entries in each table, the size of each entry, and the number of bits in each field.

  2. Consider a multi-indexed file system with a 32-bit block address, 4KB block size, and an inode structure with 4 direct pointers and one indirect pointer:

    • What is the largest disk this file system can use?
    • What is the largest file that this file system could store?
    • Assuming a disk of 128GB, how big is the free block bitmap?

    • How many data blocks are required to store 18474 bytes?

  3. It's Christmas time and Santa is making his list of naughty and nice kids 1. Having taken operating systems and actually paid attention (perhaps even going to class a few times), he decides to use his mad concurrency skills to parallelize the construction of this list. This means he orders each of his many elves to monitor different children 2 and then put them on the appropriate list. To do this, they have the following API:

    /* Child structure */
typedef struct Child;
struct Child {
    char  *name;
    Child *next;
};

/* Santa's List structure */
typedef struct SantasList SantasList;
struct SantasList {
    Child *nice_children;
    Child *naughty_children;
};

/* Santa's List functions */

SantasList  *   santaslist_create();

bool            santaslist_add_nice(SantasList *sl, const char *name);
bool            santaslist_add_naughty(SantasList *sl, const char *name);

    Each elf is given a list of children to check and then must call santaslist_add_naughty or santaslit_add_nice on each child depending on the conduct of the subject in question. These functions should add the specified child to their respective sets. If a child is already in the opposite set, then the method should return false to indicate a conflict and refrain from adding the child to the set.

    Since Santa is supes busy, he has decided to outsource 3 the implementation of this system to you. Therefore, you need to implement santaslist_create, santaslist_add_nice, and santaslist_add_naughty such that it behaves as described above and is free of race conditions, deadlocks, and starvation. Failure to do so may mean you will get some coal in your stockings this year 4...

  1. Possibly those who actually showed up to class this semester and those who didn't... J/K. Maybe. <3. ↩

  2. Sounds like Google NSA $&%NO CARRIER ↩

  3. He also got a business degree. ↩

  4. It's ok. At least it will be clean coal. Promise. ↩