All quizzes

Suppose a single-core xv6 system is running two programs. Program A is processing a large input file, doing some time-consuming computation, then writing an output file. Before this data processing finished, the user typed in some input for Program B. Eventually, xv6 starts running Program B instead of Program A, even though Program A is not finished.

Suppose a single-core system is running three processes A, B, and C.

Process A becomes ready to run (after finishing some previous I/O) at time 0, and process B becomes ready to run at time 2, and process C becomes ready to run at time 5. The operating system runs the programs until they start waiting for their next I/O operation using the following schedule:

• program A runs from time 0 to 3
• program B runs from time 3 to 5
• program C runs from time 5 to 7
• program A runs from time 7 to 10
• program B runs from time 10 to 12

For these questions, assume the time spent context switching, etc. are negligible.

Consider the following C program that uses the POSIX API:

pthread_mutex_t lock;
int global = 100;

struct ThreadData { int *pointer; };
struct ThreadData a_data, b_data;

void *thread_function(void *argument) {
    ThreadData *data = (struct ThreadData*) argument;
    int *pointer = data->pointer;
    pthread_mutex_lock(&lock);
    *pointer = global + *pointer;  /* <--- here */
    global += 10;
    pthread_mutex_unlock(&lock);
    return NULL;
}

int main() {
    pthread_t a, b;
    int value1 = 1, value2 = 2;
    a_data.pointer = &value1;
    b_data.pointer = &value2;
    pthread_mutex_init(&lock, NULL);
    pthread_create(&a, NULL, thread_function, (void*) &a_data);
    pthread_create(&b, NULL, thread_function, (void*) &b_data);
    pthread_join(&a, NULL);
    pthread_mutex_lock(&lock);
    printf("%d %d %d", global, value1, value2);
    pthread_mutex_unlock(&lock);
    pthread_join(&b, NULL);
    return 0;
}

Assume none of the calls to pthread_create, pthread_join, pthread_mutex_lock, or printf fail (and ignore minor syntax errors, missing #includes, etc.)

Consider the modified/shared/invalid cache coherency protocol we discussed in lecture running on a system with three processors A, B, and C, each of which have their own caches with 64 byte cache blocks. (With 64 byte cache blocks, addresses 0x0 through 0x3F are in the same cache block, as are 0x40 through 0x7F, and are 0x80 through 0xBF, and so on.)

Assume that when it is necessary to write a modified cache block to memory, the processor writes the value but keeps its cache block in the shared state when possible. Also assume that values are not evicted from caches due to lack of capacity

The caches are initially empty, and the processors perform the following accesses to the following addresses in this order:

• Processor A reads from address 0x100
• Processor A reads from address 0x200
• Processor A writes to address 0x200
• Processor B reads from address 0x100
• Processor B reads from address 0x200
• Processor C writes to address 0x108
• Processor A reads from address 0x100

A multithreaded batch processing program sometimes produces a very large number of messages. In attempt to limit the amount of messages the user sees, the program transfers all the messages to a dedicated "message displayer" thread, which only displays at most one message per second. When a data processing thread wants to display a message, it waits until its message is displayed before proceeding with its processing.

To facilitate this, the program uses a monitor with relevant variables and data structures declared as follows:

struct MessageInfo {
    const char *message;
    pthread_cond_t cv;
    MessageInfo *next;
    bool displayed;
};

pthread_mutex_t lock;
pthread_cond_t new_message_cv;
MessageInfo *head; MessageInfo *tail;

And once the "message displayer" thread decides to show a message, it uses code like the following (which is called with the mutex locked):

void ShowNextMessage() {
    MessageInfo *info = head;
    head = info->next;
    std::cout << info->message << std::endl;
    info->displayed = true;
    pthread_cond_signal(&info->cv);
}

(Please ignore minor syntax errors, etc. in the code above and assume all values are initialized appropriately.)

_______ ( ______________________________ ) {

    pthread_cond_wait(&info->cv, &lock);

}

pthread_mutex_lock(&lock);
while (head == NULL) {
    pthread_cond_wait(&new_message_cv, &lock);
    ShowNextMessage();
}
pthread_mutex_unlock(&lock);

A multithreaded batch processing program sometimes produces a very large number of messages. In attempt to limit the amount of messages the user sees, the program attempts to allow at most one message to be sent per second. When a thread generates a message and it cannot be shown to the user immediately, it waits until it can display the message before proceeding.

The program implements this using two counting semaphores. One semaphore, called the "prepare-to-send" semaphore, is used to indicate to a dedicated timekeeping thread that a data processing thread is ready to send a message to a user. When this timekeeping thread processes that indication, it indicates to the data processing thread that it can show the message, then waits one second, then starts checking for another data processing thread that wishes to send a message. The other semaphore, called the "ready-to-send" semaphore, is how the timekeeping thread indicates to a data processing thread that it can show a messsage.

An online encyclopedia keeps track of articles, which are grouped into categories. To do this, it keeps data structures in memory representing both the articles and categories:

struct Article {
    pthread_mutex_t lock;
    Category* category;
    ...
};

struct Category {
    pthread_mutex_t lock;
    vector<Article*> articles;
    ...
};

The online encyclopedia implementation is multithreaded sometimes experiences deadlock when simulatenously performing some combinations of the following operations on Articles and Categories:

• merge(category A, category B): move all articles from category B into A, leaving category A empty
  1. acquiring the lock for category A
  2. acquiring the lock for category B
  3. iterating over the articles in the category A, and for each article, acquiring the article's lock, changing its category pointer, and then releasing its lock
  4. adding the contents of category A's articles vector the category B's vector
  5. clearing category A's articles vector
  6. releasing the lock for each category
• move(article X, category B): move an article from whatever category it is in now to cateogry B
  1. acquiring the lock on article X
  2. acquiring the lock on article X's original category
  3. removing it from the orginal category's vector
  4. relasing the lock on the original category
  5. setting article X's category to category B
  6. acquiring the lock on category B
  7. adding it from the category B's vector
  8. releasing the lock on category B
  9. releasing the lock on article X

32-bit x86 as configured by xv6 uses a two-level page table with a 32-bit virtual addresses, 4096 byte pages, and 4-byte page table entries stored in 4096 byte page tables (for each level).

For the purposes of these questions, a first-level page table is one pointed to directly by the page table base pointer (CR3 on x86), which on x86 is also called a page directory. The second-level page table is one pointed to by an page table entry in the first-level page table.

Consider the following POSIX C code that uses mmap:

int fd1 = open("test1.dat", O_RDWR);
char *ptr1 = mmap(0, 16384, PROT_READ | PROT_WRITE, MAP_SHARED, fd1, 0);
int fd2 = open("test2.dat", O_RDWR);
char *ptr2 = mmap(0, 16384, PROT_READ | PROT_WRITE, MAP_SHARED, fd2, 0);

for (int i = 1024; i < 6 * 1024; ++i) {
    ptr2[i] = ptr2[i] + 10;
    ptr1[i] = ptr2[i];
}

Assume this runs on a system where:

• pages are 4KB
• mmap with an offset argument of 0 always returns a pointer to the beginning of page
• copy-on-write is used to implement MAP_PRIVATE, and the copy-on-write implementation only copies pages when they are written to (it never tries to "guess" what will be written to)
• if a file on disk is modified using mmap, each page that is modified will (eventually) be written to the file on disk (even if only part of the page is actually modified)

For the following questions consider an application running on a system with virtual memory backed by 4 physical pages. Exactly one application is running and, initially, the all the physical pages are empty, and these physical pages are only used for this application's virtual memory.

The application that accesses its virtual memory pages (identified using letters like A, B, C, D, E, F, G, ...) in the following sequence:

• A, B, C, D, E, A, B, C, A, B, E, A, B, D, A, B, C

The questions below ask about page replacements.

For these questions, count replacing the contents of an empty OR non-empty physical page with data for a particular virtual page as a page replacement.

When operating systems perform readahead for their page cache, they try to take advantage of sequential access patterns by detecting when a program appears to be accessing data sequentially. Then, they cache the data that the program should access next (based on the prior sequential accesses) before the program first accesses it.

For non-file pages in its page cache (such as pages representing part of a process's stack or heap), the Linux kernel keeps a separate ordered accessed list and inactive list. Pages are initially added to the top of the active list. Pages are removed from the bottom of the active list and added to the top of the inactive list in order to keep the inactive list a certain size. If a page is accessed while on the inactive list, it is moved to the active list. Otherwise, pages are taken from the bottom of the inactive list to perform page replacements.

Suppose an operating system implements a page cache using this replacement policy where:

• exactly one program uses this page cache for its virtual pages and there are no other acesseses to the page cache
• the physical memory used for the page cache has 4 pages and is initially empty
• the inactive list always contains 2 pages: whenever a page is removed from the inactive list, the last page on the active list is immediatley added to the inactive list
• page replacement only occurs when a page is accessed by the program (there is no readahead, etc.)

Suppose one has an inode-based filesystem where:

• each inode contains a ten direct block pointers, an indirect block pointer, and a double-indirect block pointers
• each block is 2KB (1KB = 1024 bytes)
• block pointers are 4 bytes
• each directory entry is 64 bytes

Consider a inode-based filesystem. For each of these questions, consider the process of moving a subdirectory X from one parent directory A to another parent directory B, assuming that the filesystem needs to an additonal data block for the directory entry in directory B.

For these questions, ignore any changes to modification and creation times the filesystem may store in inodes and assume no additional data blocks need to be allocated to store block pointers.

Suppose two programs A and B running on separate machines are both accessing a file X on an NFSv3 server. They do the following operations in this order:

• A: open file X
• A: write "1" to byte 0 of file X
• B: open file X
• B: write "3" to byte 0 of file X
• B: write "4" to byte 1 of file X
• A: write "2" to byte 1 of file X
• A: read bytes 0-1 of file X [*****]
• B: close file X
• A: close file X
• B: open file X
• B: read bytes 0-1 of file X [+++++]
• B: close file X

Assume no operations overlap in time. For example, when A and B close the file the first time, the close for B, and everything required as a result of the close, completes entirely before the close for A starts.

For this question, virtual address refer to addresses the guest OS accesses when it is running; physical addresses refer the addresses produced by taking virtual addresses and translating them using the guest OS's page table, and machine address refer to the addresses on the underlying hardware used the implement the corresponding physical addresses.

Consider a hypervisor uses shadow page tables to implement virtual memory.