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
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?
Suppose we are writing a multithreaded program which sometimes needs to retrieve data over the network from a single remote machine. To avoid overloading that machine, we want to make sure at most ten threads are retrieving data from the machine at a time.
Question 3: (see above) (see scenario above) To do this we can use a counting (that is, non-binary) semaphore, where we initialize the semaphore to _________, use the ____ operation before each thread starts retrieving data, and use the _____ operation after each thread finishes retrieving data.
Question 4: (see above) (see scenario above) To do this we can use a mutex lock, condition variable, and a counter variable tracking the number of threads currently retreving data that is only accessed while holding the mutex. In this case, threads would call Wait on the condition variable ______.
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?
Suppose we have a multithreaded chat server which has a data structure to represent each user, which contains the list of messages they recently sent and the list of messages they recently received. Each user's data structure has its own lock. A naive attempt to implementing sending a message from one user to another first locks the sending user, then the receiving user, then updates the two message lists, then unlocks each of the locks. This naive strategy can cause deadlocks.
Question 3: (see above) When might a deadlock occur because of the locks described above?
Select all that apply
Question 4: (see above) What alternatives would avoid these deadlocks?
Select all that apply
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:
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
Suppose a very simple hard disk controller exposes a buffer and several control registers via fixed (physical) memory addresses:
1 will start a read and writing the value 2 will start a writeThe disk will trigger an interrupt whenever the value of the status register changes from "reading" or "writing" to "idle".
Question 2: (see above) A process running on a POSIX-like system makes read call on the device file for the hard disk controller.
The hard disk's device driver's implementation of the read operation will,
assuming the disk is currently idle,
update the register indicating the sector number to read to, then write 1
to the control register to start a read. After this,
what would make the most sense for the device driver's read implementation do next?
Question 3: (see above) If we modified this disk controller's interface to support direct memory access, the most likely change would be
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:
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:
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