All quizzes

Question 1: In xv6, which of the following information is part of the process control block, represented in xv6 as struct proc?
Select all that apply

Question 2: On a typical implementation of POSIX, using read() to read one byte from a file descriptor with a call like:

    read(fd, buffer, 1);

where the file descriptor is opened to a file on a hard disk will:

Question 3: Consider the following POSIX C program:

#include <unistd.h>
int main(void) {
    int i = 0;
    for (i = 0; i < 2; ++i) {
        pid_t p = fork();
        printf("%d", i);
    }
    return 0; 
}

Which of the following is a possible output of this program?
Select all that apply

Question 4: After a successful call to execv
Select all that apply

Question 1: Linux's Completely Fair Scheduler adjusts timeslices based on the number of processes that are running. When there are a large number of processes running, this adjustment is likely to improve
Select all that apply

Question 2: On a system which implements threads in the kernel, creating a thread requires allocating
Select all that apply

Question 3: Consider the following function:

node *head = NULL;
void prepend(int new_value) {
    node *new_head = new node;
    new_head->value = new_value;
    new_head->next = head;
    head = new_head;
}

When running prepend simulatenously from multiple threads we find that one of the prepended values is not on the linked list head. What most likely happened?

Question 4: Consider the following pthreads code:

int global = 100;
void *print_id(void *argument) {
    int value = (int*) argument;
    printf("value=%d; global=%d\n", value, global);
    return NULL;
}

int main() {
    pthread_t threads[2];
    ++global;
    for (int i = 0; i < 2; ++i) {
        pthread_create(&threads[i], NULL, print_id, (void *) i);
    }
    for (int i = 0; i < 2; ++i) {
        pthread_join(threads[i], NULL);
    }
    return 0;
}

Assume that reading from and writing to an int or void * is atomic and that within each thread, operations (such as loads and stores) are executed in the order they are written in the C code (that is, not reordered by the processor or compiler). Which of the following would be possible outputs of this program?
Select all that apply

Question 1: In lecture we discussed a cache coherency mechanism where

• each processor has its own cache
• these caches and memory are all connected via a shared bus
• each block in each cache is in either a Modified, Shared, or Invalid state.

Which of the following is true about such a system?
Select all that apply

Question 2: We discussed a strategy to implement a "mutex" lock that puts waiting threads to sleep, allowing other threads to use the CPU, that internally used a spinlock (a lock that "spins" in an infinite loop checking the status of the lock). Which of the following was true about this spinlock?

Question 1: Suppose we have a system where one thread runs a function HandleChange(old_value, new_value) every time other threads use the SetValue function to change a shared value from old_value to new_value with the following code using a mutex and condition variable:

int value;
bool value_changed;
pthread_mutex_t lock;
pthread_cond_t change_happened;
void WaitForAndHandleChanges() {
    pthread_mutex_lock(&lock);
    while (true) {
        int old_value = value;
        while (!value_changed) {
            pthread_cond_wait(&change_happened, &lock);
        }
        HandleChange(old_value, value);
        value_changed = false;
    }
}
void SetValue(int new_value) {
    pthread_mutex_lock(&lock);
    value = new_value;
    value_changed = true;
    pthread_cond_signal(&change_happened);
    pthread_mutex_lock(&unlock);
}

After using this code, we find that sometimes HandleChange() is run too few times when SetValue() is called twice in a row from different threads.

How can we modify the above code to make sure HandleChange() is run once each time SetValue() is called?

Question 2: In lecture, we discussed a version of reader/writer locks that favored readers. This had the disadvantage of starving writers. Suppose we wanted to implement a policy that favored readers until the waiting writers have been waiting for too much time. To implement this policy, what strategy could we use?

Question 1: Before it starts any programs, xv6 sets up its page table so that 224MB starting at virtual address 0x80000000 corresponds to physical byte addresses starting with 0. (MB = 1024 * 1024 bytes.) It does this using 4K pages. How much space is requires for page tables where only these pages are valid? (Assume it uses 4K pages and the page table format used by xv6.)

Question 2: The sbrk() system call has commonly been used to implement malloc(). On an OS like xv6 where this is true, for each program that is using malloc() the kernel must keep track of which of the following?
Select all that apply

Question 3: A page fault will occur when a process tries to access a virtual address whose page table entry is invalid (on x86, has the "present" flag set to 0). If the operating system determines that the memory access should be allowed to despite it not having a valid page table entry, it will most likely:

Question 4: Suppose a Unix-like operating system uses 4K pages and the 32-bit x86 page table scheme we discussed in class. A process is running on this OS where in its page table: * virtual addresses 0x1000 through 0x9FFF (9 pages) are valid and writable and used to hold code and global variables * virtual addresses 0x10000 through 0x10FFF (1 page) are valid and writable and used for the heap, and * virtual addresses 0x7FFF0000 through 0x7FFFFFFF (16 pages) are valid and writable and used for the main thread's stack, and * every other virtual address is invalid (To simplify these questions, we will ignore any kernel-only page table entries.)

This process invokes the fork() system call, then the child process modifies addresses 0x7FFFEFF8 through 0x7FFFF016 on its stack.

If the system uses copy-on-write to implement fork(), excluding pages that hold page tables and kernel data structures, how many new physical pages will be allocated as a result of the call to fork() and subsequent modification of the child process's stack?

Question 1: Linux, and most operating systems which use memory to cache data on disk, maintains a mapping from physical pages to page table entries that reference this page. What is true about this mapping?
Select all that apply

Question 2: Suppose a process runs the following code on a Unix-like operating system:

    int fd = open("/tmp/file.dat", O_RDWR);
    char *data = mmap(NULL, 8 * 1024, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);

The calls to open and mmap succeed and mmap returns 0x999000, which is the address of the first byte of virtual page 0x999. Pages on this system are 4096 bytes.

Which of the following is definitely true?
Select all that apply

Question 3: Suppose we are using a system which uses the "second chance" replacement policy which has the following list of physical pages with the following "referenced" (or "accessed") bit values, starting with the most recently added page:

• physical page 4 (referenced)
• physical page 3 (referenced)
• physical page 1 (not referenced)
• physical page 2 (referenced)

Suppose the program accesses an unloaded virtual page A. Immediately after this, it accesses another unloaded virtual page B. To load each of these virtual pages, the OS replaces the contents of one of the physical page on its list. Which pages will be chosen?

Question 4: Suppose a program maps one page of a file from disk to its address space using mmap with MAP_SHARED and PROT_WRITE (so copy-on-write is not used and the mapping is writeable). The program first reads from the mapping, then writes to it repeatedly. What is true about writing to this mapping?
Select all that apply

Question 1: When performing readahead, an operating system detects that a program accessed consecutive locations in a file. Based on this, it predicts that the program will read future locations in the file and reads this data into memory before the program is likely to access them.

Which of the following statements about readahead are true?
Select all that apply

Question 4: In the FAT filesystem, creating a new file A in a directory D potentially involves updating which the following?
Select all that apply

Question 1: Suppose a inode-based filesystem running requires 8B for each block number, uses 2048B blocks and stores 10 direct pointers in its inode, one indirect pointer, and one double-indirect pointer. How large a file can this filesystem support? (MB = 2 to the 20 bytes below)

Question 2: An inode-based filesystem with block groups (also known as cylinder groups) improves performance by
Select all that apply

Question 3: In lecture, we discussed RAID 5, which divides data up among multiple disks, but allows failures to be tolerated by also storing "parity" information --- the result for XORing data from other disks together. Suppose we have a RAID 5 system which stores 8 sectors (A1, A2, B1, B2, C1, C2, D1, D2) where the parity information is scattered among multiple disks like as follows:

Disk 1	A1	B1	Cp = C1 XOR C2	D1
Disk 2	A2	Bp = B1 XOR B2	C1	D2
Disk 3	Ap = A1 XOR A2	B2	C2	Dp = D1 XOR D2

In this scheme with three disks as pictured, above, if all data from disk 3 is lost, recovering the value of the lost sectors B2 and C2 will reading how many sectors?

Question 4: Suppose an inode-based filesystem moves a file from an old to a new directory by taking the following steps in the following order:

• overwrite the old directory's entry for the file with an "unused" entry
• if the new directory requires more space to store the directory entry, update its inode to point to an extra data block
• write the new directory's entry for the file
• write to the free block map for the extra directory data block, if any
• update the new and old directory's inode to change modification times

What are possible outcomes if the system is interrupted and unexpectedly shuts down in the middle of this process? (You may assume that each step listed above completes entirely or not at all.)
Select all that apply

Question 1: Consider an xv6-like inode-based filesystem that uses redo-logging. Suppose this filesystem does not want to report a file deletion operation as complete until the deletion will persist even if the machine loses power. To delete a file, the filesystem will overwrite the directory entry for the file with one labelled as "unused", update the free block list, and update the file inode (to mark it as free) and directory inode (to change its modification time). It should return from the file deletion system call after

Question 2: When overwriting 3 blocks of data in a 10 block file on a filesystem that does copy-on-write snapshots, the filesystem will
Select all that apply

Question 3: Port numbers
Select all that apply

Question 4: In POSIX sockets, a server socket
Select all that apply

Question 1: Consider two phase commit with a coordinate machine C and two worker machines A and B. Suppose after both A and B send their 'agree-to-commit' messages to C, then after C tries to send its 'global-commit' message to A and B, it discovers that B has lost power and cannot receive the 'global-commit' message. What should C do while machine B remains down?

Question 2: We described two-phase commit in terms of the worker and coordinator nodes operating according to a state machine. In order to recover properly from failures, as it transitions from one state to another, each worker machine writes ___________ to its log __________ it sends the messages (such as votes on transactions) triggered by that transition.

Question 3: Suppose one wanted to:

• allow processes running for a list of users to write data to a file, but only if they are writing ASCII data to the file, and
• disallow any other users (except maybe the system administrator) from modifying the file

Which of the following access control mechanisms could enforce these restrictions?
Select all that apply

Question 4: In a capability-based system, to give a process access to files in a directory, but only to read it, one would most likely