All quizzes

All quizzes

Quiz 01

Suppose a single-core system is running three processes, A and B and C. Then the following sequence of events occur in the following order:

  1. Initially, process A is running
  2. Process A starts waiting for input from the keyboard
  3. Process B computes an image and displays it on the screen
  4. Process B computes a second image and displays it on the screen
  5. Process C runs part of its long computation
  6. Process A retrieves its input from the keyboard
  7. Process A causes Process B to be terminated (killed)
  8. Process A starts waiting for keyboard input again
  9. Process C performs the second part of its computation

Question 1 (1 points): (see above) During this sequence, what is the minimum number of process context switches that must occur? (Write your answer a a base-10 integer.)

Answer:

Question 2 (1 points): (see above) In a Unix-like operating system (with a monolithic kernel design), which of the following operations (from the sequence above) most likely would require starting a system call?
Select all that apply

  1. Process B computes an image and displays it on the screen

  2. Process C runs part of its long computation

  3. the OS detects input for process A and runs process A

  4. Process A causes process B to be terminated (killed)

Question 3 (1 points): Suppose an xv6 process has an invalid value for its stack pointer register while it is running in user mode. What are expected consequence of this?
Select all that apply

  1. when an exception (such as a timer interrupt) next occurs, the xv6 kernel will crash while trying to save the user registers to the stack pointed to by that invalid pointer

  2. if the process is running in user mode and tries to access memory around that where the stack pointer points, the xv6 kernel will be run and kill the application

  3. if the xv6 kernel context switches away from that process, it will not be able to context switch back to it because of the invalid stack pointer

Question 4 (1 points): When an exception occurs, processors will usually _____. (Include all types of exceptions, including what some sources call interrupts, traps, faults, etc.)
Select all that apply

  1. wait for the currently executing function to finish executing before running the exception handler

  2. use a lookup table to determine the location of the exception handler based on the kind of exception

  3. switch from user to kernel mode (if the exception occured while the processor was in user mode)

Quiz 02

Question 1 (1 points): Consider the following C code that uses the POSIX API:

write(STDOUT_FILENO, "A", 1);
pid_t pid = fork();
write(STDOUT_FILENO, "B", 1);
if (pid == 0) {
    write(STDOUT_FILENO, "C", 1);
    exit(0);
} else if (pid > 0) {
    write(STDOUT_FILENO, "D", 1);
    waitpid(pid, NULL, 0);
    write(STDOUT_FILENO, "E", 1);
}

Ignore any minor syntax errors above, assume all appropriate headers are included and that none of fork(), write(), and waitpid() fail.

Two possible outputs of the above code are "ABDBCE" and "ABCBDE". Write another.

Answer:
Comments:

Grader reply: your comment is not actually true (no change in grade)

Question 2 (1 points): Immediately after a call to fork(), what is true?
Select all that apply

  1. the values of local variables (except perhaps the return value of fork()) in the parent and child process are the same

  2. if the child process modifies a value stored on its heap, the parent can read the modified value

  3. the parent and child process have the same files open

  4. the child process is most likely running code from a different executable than the parent process

Comments:

Grader reply: your comment does not change which answer is correct (no change in grade)

Question 3 (1 points): Consider the following Unix-style shell command

./A B > C

The following is some partial C code using the POSIX API that would execute that command:

const char *args[10] = {"./A", "B", NULL, NULL};
pid_t pid = fork();
if (pid < 0) {
    handleError();
} else if (pid > 0) {
    waitpid(pid, NULL, 0);
} else {

    ______________________

    ______________________

    execv("./A", args);
}

Ignore any minor syntax errors above, missing error handling, and assume all appropriate headers are included.

Which of the following would be best to place in the blanks above to complete the code? (Ignore minor syntax errors and missing error handling.)

  1. args[2] = "C";

  2. int fd = open("C", O_WRONLY | O_CREAT | O_TRUNC);
    dup2(fd, STDOUT_FILENO);
    close(fd);

  3. int fd = open("C", O_WRONLY | O_CREAT | O_TRUNC);
    dup2(STDOUT_FILENO, fd);
    close(STDOUT_FILENO);

  4. int fd = open("C", O_WRONLY | O_CREAT | O_TRUNC);
    dup2(fd, STDIN_FILENO);
    close(fd);

  5. int fd = open("C", O_RDONLY);
    dup2(fd, STDIN_FILENO);
    close(fd);

  6. int fd = open("C", O_RDONLY);
    dup2(fd, STDOUT_FILENO);
    close(fd);

For the following questions, consider the following Unix-style shell pipeline:

./A | ./B | ./C

When this is run, the commands ./A, ./B, and ./C are run in parallel, the output of ./A becomes the input to ./B, and the output of ./B becomes the input to ./C.

Assume that the shell uses fork() to create new processes and pipe() to allow the new processses to receive other process's output as input.

Question 4 (1 points): (see above) When executing the above shell pipeline, how many times should the shell call fork() or an equivalent function? (Write your answer as a base-10 number like "15".)

Answer:

Question 5 (1 points): (see above) When executing the above shell pipeline, how many times should the shell call pipe() or an equivalent function? (Write your answer as a base-10 number like "15".)

Answer:

Quiz 03

Question 1 (1 points): In a Unix-like system, which of the following are attributes of a thread as opposed to a process?
Select all that apply

  1. whether file descriptor 1 (which represents standard output) is open

  2. the value of the register most commonly used to hold function return values

  3. the value of a global variable

  4. the location of the top of the heap

Question 2 (1 points): Which of the following changes to xv6's scheduler would be likely to lower overhead?
Select all that apply

  1. only calling yield() on every other timer interrupt instead of on every timer interrupt

  2. running the thread/process-selection code in the thread being switched away from instead of using a dedicated scheduler thread

  3. scanning the process/thread list for the runnable thread that has been run least recently (and adding code to track when threads were last run) instead of selecting the next process/thread on the list

Question 3 (1 points): A first-come first-served scheduler will often be better than a round-robin scheduler at providing which of the following?
Select all that apply

  1. high portion of compute time used for application computations

  2. low variance in the wait times experienced by each of the threads being scheduled

Consider the following schedule:

Question 4 (1 points): (see above) What is the total turnaround time experienced by thread B between time 0 and 11? (Write your answer as a base-10 number like "15".)

One source of confusion on this question was mixing up "waiting for I/O" with "wait time". In the context of CPU scheduling, "wait time" refers to time that a thread could be run on the CPU but is not — so time spent waiting for I/O would not be included.

Answer:

Question 5 (1 points): (see above) What is the total turnaround time experienced by thread C between time 0 and 11? (Write your answer as a base-10 number like "15".)

Answer:

Question 6 (1 points): Without preemption, shortest job first does not minimize mean turnaround time. In fact, in some corner cases, it fails to even achieve the minimum mean turnaround time possible without preemption (and on a single core). One reason for this is that the shortest job first does not consider schedules that leave the processor idle in order to wait for a short job. Which of the following are examples of such scenarios?
Select all that apply

  1. thread A becomes runnable at time 0, requires 5 units of time; thread B at time 1 requiring 2 units of time

  2. thread A becomes runnable at time 0, requires 5 units of time; thread B at time 2 requiring 2 units of time

  3. thread A becomes runnable at time 0, requires 5 units of time; thread B at time 1 requiring 4 units of time

  4. thread A becomes runnable at time 0, requires 10 units of time; thread B at time 5 requiring 9 unit of time

Quiz 04

Suppose a system uses a (preemptive) multi-level feedback queue scheduler to decide when threads get access to a single core. This scheduler divides threads into five priorities:

And the scheduler increases the priority of threads (if possible) whenever they are not preempted and do not use their entire time slice and decreases the priority of a thread whenever it uses its entire time slice and still requires more computation.

This system is running four threads, each of which have the following CPU usage patterns which are repeated indefinitely:

For the following questions, assume context switch and other scheduling overheads are neglibile and all threads have been running for a while.

Question 1 (1 points): (see above) Thread B1 will have priority

  1. 0

  2. 1 or 0

  3. 1

  4. 1 or 2

  5. 2

  6. 2 or 3

  7. 3

  8. 3 or 4

  9. 4

  10. none of the above

Question 2 (1 points): (see above) When thread C completes a disk I/O, it is possible that it will need to wait for other threads to perform computations before it will be allowed to start performing its 8.5 milliseconds of computation.

Which of the following is the maximum amount of time that it might need to wait to start its computation? If the true answer is on a boundary (e.g. 1.1ms) then we will accept either of the two answers that touch the boundary as correct (e.g. both "less than 1.1 ms" and "between 1.1 ms and 1.8 ms" for 1.1ms).

  1. less than 1.1 ms

  2. between 1.1 ms and 1.8 ms

  3. between 1.8 ms and 2.5 ms

  4. between 2.5 ms and 3.5 ms

  5. between 3.5 ms and 6 ms

  6. between 6 ms and 11 ms

  7. more than 11 ms

Question 3 (1 points): An alternative to the multi-level feedback queue style of designs for approximating SRTF is to try to record the length of CPU bursts, and use the average of recent CPU burst times to make a scheduling decisions.

In order to perform the task of a recording the length of CPU bursts, an operating system can time how long a process runs each time it is scheduled. This will result in a sequence of timings, one for each time the thread is scheduled on a core. The length of each CPU burst (suitable for approximating SRTF) is equal to _____

  1. the length of exactly one of the timings

  2. the sum of these timings, starting from some point when the thread was preempted and going until it next was preempted

  3. the sum of these timings, starting from some point when the thread was preempted and going until it next ceased to be runnable

  4. the sum of these timings, starting from some point when the thread became runnable and going until it next ceased to be runnable

  5. the sum of these timings, starting from some point when the thread become runnable and going until it is next preempted

Question 4 (1 points): A scheduler that approximates SRTF, like a multi-level feedback queue design, will tend to favor interactive programs that perform short CPU bursts. Linux's Completely Fair Scheduler sometimes does so, but since it has a different scheduling goal, it often wil not. In which of the following scenarios is CFS likely to result in much worse performance for the interactive thread than an MLFQ-like scheduler that approximates SRTF?

(Assume every thread has the same weight in CFS. Ignore CFS features we did not discuss in class, like handling multiple cores.)
Select all that apply

  1. running one interactive thread with short CPU bursts that, if running alone, would use very little CPU time and one very CPU-intensive thread that never does I/O

  2. running one interactive thread with short CPU bursts that, if running alone, would use very little CPU time and one non-interactive thread with much longer CPU bursts that performs disk I/O frequently

  3. running one interactive thread with frequent short CPU bursts that, if running alone, would use most of the available CPU time, and one very CPU-intensive thread that never does I/O

  4. running one interactive thread with short CPU bursts and a very large number of CPU-intensive threads that never do I/O

Question 5 (1 points): Consider the following C code that uses the POSIX threading API:

pthread_t a, b;
struct point { int x, y; };
void *bar(void *arg) {
    struct point *p = (struct point *) arg;
    printf("%d\n", p->x);
}
void *foo(void *arg) {
    struct point *initial = (struct point *) arg;
    struct point new;
    new.x = initial->x; new.y = initial->y;
    pthread_create(&b, NULL, bar, (void*) &new);
    pthread_join(b, NULL);
}
int main(void) {
    struct point *main_pt = malloc(sizeof(struct point));
    main_pt->x = 100; main_pt->y = 120;
    pthread_create(&a, NULL, foo, main_pt);
    pthread_join(a, NULL);
    free(main_pt);
}

Ignore any minor syntax errors above, assume all appropriate headers are included and that the pthread functions do not fail.

When this code is run p->x in bar most likely will access _____?

  1. a value stored in the heap

  2. a value stored on thread a's stack

  3. a value stored on thread b's stack

  4. a value stored in a global variable

  5. a value stored in a register in thread b

  6. a value stored in a register in thread a

Quiz 05

Consider a multicore system where each core has its own cache. Consistency between these caches is maintained using a shared bus and a cache coherency protocol where each cache block is either in a modified, shared, or invalid state like we discussed in lecture. The implementation of this protocol tries to maximize efficiency by:

On this system, cache blocks are 256 bytes, so addresses 0x00 through 0xFF are in the one cache block, as are 0x100 through 0x1FF, 0x200 through 0x2FF, etc.

Suppose all cores initially have empty caches and perform single-byte reads and writes as follows, in this order:

Assume at no point are cache blocks evicted from the cache other than due to invalidations to ensure consistency with other cores.

Question 1 (1 points): (see above) What is the final state of the cache block containing 0x4020 on core 1?

  1. modified

  2. shared

  3. invalid

Question 2 (1 points): (see above) What is the final state of the cache block containing 0x5000 on core 1?

  1. modified

  2. shared

  3. invalid

Question 3 (1 points): Suppose two threads A and B coordinate using a spinlock implemented based on atomic exchange like we dicussed in lecture. Assume, unlike xv6's spinlocks, these threads do not disable interrupts when acquiring the spinlock.

Both threads are running on a single-core system that uses a round-robin scheduler with a 20 millisecond time quantum. Thread A acquires the spinlock, then needs to do about 50 milliseconds of computation, then will release the spinlock and terminate. About 1 millisecond after thread A acquires the spinlock, thread B tries and waits to acquire the spinlock. Assuming thread A and B are the only runnable threads on the system (and never need to wait for I/O), how long will it be between when thread A acquires the spinlock and when it releases it?

  1. about 50 milliseconds

  2. about 70 milliseconds

  3. about 90 milliseconds

  4. about 100 milliseconds

  5. about 110 milliseconds

  6. about 130 milliseconds

  7. about 150 milliseonds

  8. A will never release the spinlock

Question 4 (1 points): In lecture, we discussed implementing a mutex that does not consume a lot of CPU running a waiting loop by using a queue of waiting threads and a spinlock. This mutex implementation may _____.
Select all that apply

  1. make a previously runnable thread not runnable from the mutex lock operation

  2. return from the mutex lock operation after locking and not unlocking the spinlock

  3. need to wait briefly to acquire the spinlock (by running a loop that repeatedly checks if the spinlock is free) in order to complete the mutex unlock operation

Question 5 (1 points): Consider the following incomplete C code that uses the POSIX threading API:

pthread_mutex_t lock;
pthread_cond_t cv; // condition variable
int values[2];
int have_values[2] = {0, 0};

void SetValue(int index, int new_value) {
    pthread_mutex_lock(&lock);
    values[index] = new_value;
    have_values[index] = 1;

    if (___________________________________) {
        pthread_cond_broadcast(&cv);
    }
    pthread_mutex_unlock(&lock);
}

void WaitForAndGetBothValues(int *values_copy) {
    pthread_mutex_lock(&lock);
    while (!have_values[0] || !have_values[1]) {
        pthread_cond_wait(&cv, &lock);
    }
    values_copy[0] = values[0];
    values_copy[1] = values[1];
    pthread_mutex_unlock(&lock);
}

Ignore any minor syntax errors above and assume all condition variables, locks, etc. are appropriately initialized before any of the above code is run.

The WaitForAndGetBothValues function is intended to wait for SetValue to be called with both index 0 and index 1, then return the resulting contents of the values array (by copying it into an array located using the supplied pointer). Which of the following would be best to place in the blank above to make WaitForAndGetBothValues behave correctly?

  1. have_values[1 - index]

  2. !have_values[0] || !have_values[1]

  3. cv == false

  4. cv == true

  5. pthread_cond_wait(&cv, &lock) == 0

  6. pthread_mutex_lock(&lock) != 0

Quiz 06

Question 1 (1 points): Consider the following code that uses semaphores:

sem_t a, b;
int x = 0;

void foo() {
    sem_wait(&a);
    write(STDOUT_FILENO, "A");
    x = x + 1;
    sem_post(&a);
    write(STDOUT_FILENO, "B");
    sem_wait(&b);
    write(STDOUT_FILENO, "C");
}

void bar() {
    sem_wait(&a);
    while (x > 1) {
        write(STDOUT_FILENO, "D");
        sem_post(&b);
        x = x - 1;
        write(STDOUT_FILENO, "E");
    }
    sem_post(&a);
}

Suppose the a semaphore is initialized to 1 and the b are semaphores is initialized to 0 by code not shown, and no code other than the initialization code and the code above uses these semaphores or changes the value x. Which of the following are possible outputs from multiple threads calling foo() and bar() multiple times?
Select all that apply

  1. ABDEC

  2. DABCE

  3. ABDABECDEC

  4. ABABDEDECC

  5. AABBDCEDCE

Suppose we have a multithreaded system for handling a ticket vending service. When dealing with the last few remaining tickets, this service attempts to offer each ticket to a user and wait until they complete the purchase of the ticket or decline to purchase it. While this is happening, another user can be waiting for a ticket to become available or for all tickets to be sold out.

Suppose, to implement this, the service provides the following functions:

so the code that prompts a user for their decision looks something like:

if (WaitForNextTicket()) {
    printf("Purchase ticket? ");
    if (ReadInputFromUser() == YES) {
        BuyTicket();
    } else {
        DeclineTicket();
    } 
} else {
    printf("Tickets are sold out\n");
}

Question 2 (1 points): (see above) Suppose these functions are implemented using mutexes and condition variables. The WaitForNextTicket() function would most likely call pthread_cond_wait ____________.

  1. in a loop for as long as there are unsold tickets

  2. in a loop for as long as all unsold tickets are awaiting a user's decision to purchase or decline it

  3. in a loop for as long as at least one ticket is awaiting a user's decision to purchase or decline it

  4. once (without a loop), but only if all unsold tickets are awaiting a user's decision to purchase or decline it

  5. once (without a loop), but only if at least one ticket is awaiting a user's decision to purchase or decline it

  6. once (without a loop), but only if there are unsold tickets

Question 3 (1 points): (see above) Suppose these functions are implemented using POSIX semaphores. Of the choices listed below, it is most likely that the WaitForNextTicket() function would call sem_wait on a semaphore whose value represents ______.

  1. the total number of tickets available for purchase and not reserved

  2. the total number of tickets either available for purchase or currently reserved for purchase (but not bought or declined)

  3. the total number of tickets currently reserved for purchase (but not bought or declined)

  4. the total number of tickets ever reserved for purchased, regardless of whether eventually bought or declined

  5. the total number of tickets already bought

Consider a multithreaded system for processing college applications that stores most of its data in memory. It is written in C++ and uses the following structs:

struct Student {
    pthread_mutex_t lock;
    string name;
    Application* current_application;
    ...
};

struct Application {
    pthread_mutex_t lock;
    Student *student;
    AcademicYear *year;
    string status; /* one of pending, accepted, admitted, rejected, withdrawn */
    ...
};

struct AcademicYear {
    pthread_mutex_t lock;
    set<Application*> pending, admitted, rejected, withdrawn;
};

and has the following functions relevant to the questions below:

bool WithdrawPendingStudent(Student *student) {
    pthread_mutex_lock(&student->lock);
    Application *app = student->current_application;
    pthread_mutex_lock(&app->lock);
    bool result;
    if (app->status == "pending") {
        pthread_mutex_lock(&app->year);
        app->status = "withdraw";
        app->year->pending.erase(app);
        app->year->withdrawn.erase(app);
        pthread_mutex_unlock(&app->year);
        result = true;
    } else {
        result = false;
    }
    pthread_mutex_unlock(&app->lock);
    pthread_mutex_unlock(&student->lock);
    return result;
}

bool AdmitFirstKPending(AcademicYear *year, int K) {
    pthread_mutex_lock(&year->lock);
    for (int i = 0; i < K; ++i) {
        Application *app = FindHighestRanked(&year->pending);
        year->admitted.insert(app);
        year->pending.erase(app);
        pthread_mutex_lock(&app->lock);
        app->status = "admitted";
        pthread_mutex_unlock(&app->lock);
    }
    pthread_mutex_unlock(&year->lock);
}

(Please ignore minor syntax errors, etc. in the above, assume all appropriate headers are included, etc.)

Question 4 (1 points): (see above) Two simultaneous calls to WithdrawPendingStudent() and AdmitFirstKPending() sometimes deadlock. When this occur, the thread calling WithdrawPendingStudent() can be holding the lock in a _____ while the thread calling AdmitFirstKPending() is trying to acquire the same lock.
Select all that apply

  1. AcademicYear struct

  2. Application struct

  3. Student struct

Question 5 (1 points): (see above) Two simulatenous calls to WithdrawPendingStudent() and AdmitFirstKPending() sometimes deadlock. When this occur, the thread calling AdmitFirstKPending() can be holding the lock in a _____ while the thread calling WithdrawPendingStudent() is trying to acquire the same lock.

  1. AcademicYear struct

  2. Application struct

  3. Student struct

Quiz 07

Suppose an x86 system which uses the same page table layout as xv6 (two-level page tables, 4KB pages, 32-bit virtal addresses, 4B page table entries) where:

Question 1 (1 points): (see above) The first-level page table ("page directory") entry for virtual address 0x4443 is at what physical address? Write your answer as a hexadecimal number like 0xAC888; if not enough information is provided write unknown.

Answer:

Question 2 (1 points): (see above) The second-level page table entry for virtual address 0x4443 is at what physical address? Write your answer as a hexadecimal number like 0xAC888; if not enough information is provided write unknown.

Answer:

Question 3 (1 points): (see above) The byte stored at virtual address 0x4443 is located at what physical address? Write your answer as a hexadecimal number like 0xAC888; if not enough information is provided write unknown.

Answer:

Question 4 (1 points): Suppose wanted to make a system call in xv6 with the following prototype:

int cross_process_copy(char *source_address, int dest_pid, char *dest_address)

which would copy one byte from virtual address source_address in the current process to virtual address dest_address in the destination process dest_pid. After retreiving the arguments for this system call, one potential implementation strategy would look like the following:

char *real_source_address = convert_source_address(source_address);
char *real_dest_address = convert_dest_address(dest_pid, dest_address);

*real_dest_address = *real_source_address;

To make this work, the convert_dest_address function should:

  1. return dest_address without modification

  2. return the sum of the virtual address of dest_pid's page table and dest_address

  3. return the sum of the physical address of dest_pid's page table and dest_address

  4. return the sum of dest_address and the start of the kernel virtual memory region (KERNBASE) (the operation performed by P2V(dest_address))

  5. use dest_pid's page table to convert dest_address to a physical address, then return that physical address

  6. use the current page table to convert dest_address to a physical address, then return that physical address

  7. use dest_pid's page table to convert dest_address to a physical address, then return the sum of that phyiscal address and the start of the kernel virtual memory region (KERNBASE) (the operation performed by P2V(that physical address))

  8. use the current page table to convert dest_address to a physical address, then return the sum of that phyiscal address and the start of the kernel virtual memory region (KERNBASE) (the operation performed by P2V(that physical address))

Question 5 (1 points): Suppose an operating system does not allocate memory for programs or load a program's data from disk until it attempts to use each page of it.

Assume the operating system is using a page table layout like xv6 (two-level page tables, 4KB pages, 32-bit virtal addresses, 4B page table entries).

Suppose a program accesses all of an 8192-byte global array for the first time. When this occurs, page faults may occur to allocate memory for the array.

How many page faults are required may depend on what addresses were allocated to the array (for example, whether the array starts in the middle of a page) and whether memory around the array was already accessed previously.

What numbers of page faults are possible?

  1. only 1

  2. only 2

  3. only 3

  4. 0 or 1 or 2 or 3

  5. 0 or 1 or 2

  6. 1 or 2 or 3

  7. 2 or 3

  8. 1 or 2

Quiz 08

Consider the following C code:

int fd1 = open("one.data", O_RDONLY);
if (fd1 < 0) handle_error();
char *p = mmap(NULL, 8192, PROT_READ, MAP_SHARED, fd1, 0);
if (p == (char*) MAP_FAILED) handle_error();
int fd2 = open("one.data", O_RDWR);
if (fd2 < 0) handle_error();
char *q = mmap(NULL, 8192, PROT_READ | PROT_WRITE, MAP_SHARED, fd2, 0);
if (q == (char*) MAP_FAILED) handle_error();
*q = 'a';
printf("%c", *p);

Assume all required headers are included and ignore minor syntax errors above and assume open() and mmap() do not fail (so handle_error() is not reached).

Assume:

Question 1 (1 points): (see above) Immediately after the code above runs, which of the following statements are true?
Select all that apply

  1. *p and *q contain the same value (regardless of the initial contents of one.data)

  2. the physical pages assigned to *p and *q are the same

  3. the virtual addresses assigned to *p and *q have the same page offset

  4. opening one.data and writing to it can change the value of *p

Question 2 (1 points): (see above) Immediately after the code above runs, which of the following operations are likely to trigger a page or protection fault for a virtual address assigned to the file one.data?
Select all that apply

  1. printf("%c", p[4096]);

  2. printf("%c", *q);

  3. q[4096] = 'a';

  4. *q = 'b';

  5. *p = 'b';

Question 3 (1 points): Suppose three processes A, B, and C are running. Processes A and B share the same executable foo.exe, and the code from the executable mapped into their address space. Process C is running with a different executable and tries to use a lot of space on its heap. In order to satisfy process C's requirement for more memory, the operating system chooses to use space currently used for part of the machine code in foo.exe. This space was loaded into memory since it was first used by process A. However, process B most recently accessed the machine code in question.

As part of allocating the data for C, the operating system should ______.
Select all that apply

  1. edit some of the page table entries for process A

  2. edit some of the page table entries for process B

  3. edit some of the page table entries for process C

  4. write back changes to this space to foo.exe

Quiz 09

Suppose a system implements virtual memory with 5 physical pages used to satisfy a program's memory needs. To keep things simple, the physical pages are only used for the program's memory and not to cache file data, etc.

It is running two processes A and B, and each of those processes is assigned three virtual pages: for process A, A1, A2 and A3; and for process B, B1, B2, and B3.

Process A executes the following access pattern:

and process B executes the following access pattern:

Question 1 (1 points): (see above) Suppose the two processes are run so their accesses are interleaved, so the overall access pattern is:

  • A1, B1, A2, B3, A3, B1, A1, B2, A3, B3, A2, B3

Assuming all physical pages are initially empty, with an LRU replacement policy how many page replacements will occur? (Loading data into an physical page, regarldess of whether it was empty or not, is a page replacement.) Write your answer as a base-10 number.

Answer:

Question 2 (1 points): (see above) Suppose the two processes are run one after the other, so the overall access pattern is:

  • A1, A2, A3, A1, A3, A2, B1, B3, B1, B2, B3, B3

Assuming all physical pages are initially empty, with an LRU replacement policy how many page replacements will occur? (Loading data into an physical page, regarldess of whether it was empty or not, is a page replacement.) Write your answer as a base-10 number.

Answer:

Question 3 (1 points): In lecture we discussed an approximation of LRU called SEQ that:

  • seperated physical pages into an ordered active list and an ordered inactive list
  • placed just-replaced physical pages on the top of the active list
  • pages on the active list are not monitored for accesses
  • when the inactive list gets too small, takes a page from the bottom of the active list and places on the inactive list
  • when a page on the inactive list is accessed, places that page on the top of the active list
  • selects physical pages to replace from the bottom of the inactive list

Which of the following is true about this scheme?
Select all that apply

  1. decreasing the size of the inactive list is likely to increase the overhead of detecting accesses to pages

  2. decreasing the size of the inactive list from many pages to one page is likely to make the scheme approximate LRU better

  3. increasing the size of the inactive list from about one tenth of all physical pages to all but a couple of physical pages is likely to make the scheme approximate LRU better (possibly at the cost of a higher overhead)

Question 4 (1 points): In some circumstances, readahead can dramatically increase the number of page cache misses (and therefore required amount of (re)loading data from disk). Suppose this is true even though the pages which are read ahead are, in fact, used before they are replaced.

Which of the follow are true about this scenario where readahead causes bad performance?
Select all that apply

  1. if the operating system's readahead implementation loaded more pages at a time, this would likely decrease the number of page cache misses

  2. if the operating system's readahead implementation loaded fewer pages at a time, this would likely decrease the number of page cache misses

  3. a significant number of the virtual pages replaced as part of the readahead were probably accessed before the readahead pages

Question 5 (1 points): Suppose a process takes input from the keyboard on a xv6-like operating system. As part of obtaining input from the keyboard controller, the operating system needs to use a control register on the device controller to determine whether there is input. In which of the following scenarios is code that accesses the keyboard controller's control registers likely to run?
Select all that apply

  1. from an device interrupt handler that interrupts the process that requires keyboard input

  2. from an device interrupt handler that interrupts a process that does not require keyboard input

  3. from the read system call implementation (and not during a interrupt triggered by the device, regardless of whether that can interrupt a system call)

Quiz 10

Question 1 (1 points): Suppose a network interface device uses direct memory access (DMA). It provides the following registers, each of which has corresponding memory address through which the operating system can set them:

  • a control register which is 1 if receiving input is enabled, 0 otherwise
  • a register indicating the current size of the input buffer
  • a register indicating the address of the input buffer
  • a register indicating the amount of the input buffer which is currently used for data
  • and some additional registers not listed

(Assume no IOMMU is in use. If you do not know what an IOMMU is, then it won't affect your answer.)

In order receive input from the network using this device, it would be best for the operating system to set the register indicating the address of the input buffer to:

  1. a kernel virtual address corresponding to the operating system's buffer for network data

  2. a physical address corresponding to the operating system's buffer for network data

  3. a user virtual address corresponding to the current read() call trying to read network input

  4. the address of the exception handler that handles input from this device

For these questions, consider a FAT-like filesystem with:

Question 2 (1 points): (see above) Ignoring space in the FAT itself and the header (BPB), how many clusters would be used (completely or partially) to store a FAT filesystem whose root directory contains 100 directories and each of those directories contains one 1000-byte text file? Write your answer as a base-10 number of clusters (like "500")

Answer:

Question 3 (1 points): (see above) In the scenario described in the previous question, how many FAT entries would contain a value representing a cluster number? Write your answer as a base-10 number of clusters (like "500").

Answer:

Question 4 (1 points): Consider the following strategies for assigning clusters to a large file on a FAT filesystem. Assume the operating system assigning clusters knows the number of clusters that must be assigned in advance and that this operating system always keeps a copy of the file allocation table in memory for performance.

Which of the following strategies would likely result in best performance when reading the file from a hard drive?

  1. choose the available clusters with the lowest numbers (closest on the disk to the location of the FAT)

  2. choose the available clusters with the highest numbers (furthest on the disk to the location of the FAT)

  3. choose a set of available clusters that are contiguously numbered

  4. choose a set of clusters that use as many cylinders as possible

  5. choose a set of available clusters that are as close in number to the cluster containing the directroy entry for the file, even if this means having large gaps between the chosen cluster numbers

Consider an xv6-like filesystem with:

Question 5 (1 points): (see above) To store a directory with two 99.5KB files (where KB = 1024 bytes), how many blocks are used (outside of inodes, free block maps, etc.)? Include any blocks allocated to hold block pointers (outside of inodes) and space required for the directory.

Write your answer as a base-10 number (like "500").

Answer:

Quiz 11

Suppose a inode-based filesystem uses redo-logging to recover from failures.

As part of truncating a file from a large size to a smaller size it needs to write:

The filesystem performs this truncation operation atomically, meaning that on a failure, after reboot, either the file will be truncated or will have its original size.

Question 1 (1 points): (see above) What is a valid order for the filesystem to perform the above operations during normal operation?

Write your answer as a sequence of letters. For example, if you think it would be valid for each of the operations above occur exactly once and in the order written above, write "ABCDEFG".

Answer:

Question 2 (1 points): We discussed the idea of "block groups" (like implemented in the Berkeley Fast File System) as a mechanism for keeping related data and metadata physically close on a hard drive.

In the Berkeley FFS scheme, each directory and the files it contains are assigned to a block group. This makes some assumptions about the typical access patterns for files.

For which of the following access patterns are many long seeks likely to be required (assuming data is not cached) when using the block group scheme we described in lecture?
Select all that apply

  1. reading and writing files in many subdirectories, where each subdirectory contains exactly one file, of a single directory

  2. loading an application from /usr/bin along with many small libraries which are all contained in /usr/lib.

  3. reading C source files and writing object files in a directory checked out from a version control system as part of compiling a program

Consider an inode-based filesystem that supports fragments for small files.

In this filesystem, each inode contains (among other fields): * a boolean which is true if the first direct block represent an extent and not a normal block * 12 direct block pointers * 1 indirect block pointer * 1 double-indirect block pointer * 1 triple-indirect block pointer

The filesystem uses 4KB blocks with 1KB fragments and directory entries that take 64 bytes.

Assume that the filesystem only uses fragments for files that fit within a single fragment.

For this question, 1KB = 1024 bytes and 1MB = 1024KB.

Question 3 (1 points): (see above) Suppose the filesystem is storing a directory with one thousand files where each of those files is 768 bytes. How many blocks will the filesystem use outside of inodes, free block maps, superblocks, etc.? Include space required for file data, directory entries and blocks of block pointers (outside of inodes). Write your answer as a base-10 number. (Assume the filesystem uses fragments in the most efficient way possible.)

Answer:

Question 4 (1 points): (see above) Suppose the filesystem is storing a directory with 10 subdirectories, where each subdirectory contains a 10MB file. How many blocks will the filesystem use outside of inodes, free block maps, superblocks, etc.? Include space required for file data, directory entries and blocks of block pointers (outside of inodes). Write your answer as a base-10 number. (Assume the filesystem uses fragments in the most efficient way possible.)

Answer:

Question 5 (1 points): Suppose one uses the client/server communication model we discussed in lecture in system with two clients A and Band one server S.

Suppose we want implement a way to send a message from a client A to another client B. To be most consistent with the client/server model, this would be implemented by ______.

  1. having client A connect to the server and send its message and then having client B connect to the server and ask for the message and have the server reply with that message

  2. having client A become the server and then having client B connect to the client A to receive the message

  3. having client B become the server and then having client A connect to the client B to receive the message

  4. having client A connect to the server and send its message, then have the server contact client B and forward the message

Quiz 12

Suppose we wanted to allow someone to read files remotely using RPC. To do this, we take the simple solution of exposing the following POSIX file I/O calls as RPC calls:

Question 1 (1 points): (see above) To convert the read() call above into an RPC call, the resuling RPC call would most likely
Select all that apply

  1. send the address contained in the pointer buffer to the server when the call is made (before invoking the server's implementation of read)

  2. send the contents of buffer from the client to the server when the call is made (before invoking the server's implementation of read)

  3. send the contents of buffer from the server to the client when the call is made (after invoking the server's implementation of read)

Question 2 (1 points): (see above) Which of the following statements about how this scheme deals with failures are true?
Select all that apply

  1. if the server can't open a file, then it will appear to the client like the file exists but is empty instead

  2. if the server crashes without saving information about file descriptors, then a client that is in the middle of reading a file will not be able to continue when the server is restarted

  3. if a client crashes without saving information about file descriptors, then the server is unlikely to have enough information to free resources for file descriptors

  4. if a client crashes while reading a file and then tries to open and read the file again after rebooting, it may sometimes read the wrong file contents (during the second read, after rebooting)

Question 3 (1 points): Suppose an RPC system attempts to deal with errors by making sure that every message sending an RPC call or the return value of an RPC call receives an acknowledgment. If it does not, the RPC system retries sending that message until either it receives that acknowledgment or a certain amount of time has passed (in which case it signals an error to the calling program, if possible). In this scheme, if a client does not receive the return value of an RPC call after a certain amount of time, it also signals an error to the calling program.

Suppose network failures involving messages being lost or reoredered can occur and machine failures can occur according to fail-stop model. Which of the following are possible?
Select all that apply

  1. sending from a client an RPC that changes something on the server but having it appear to fail on the client

  2. sending from a client an RPC that fails to reach the server but having it appear to work on the client

  3. having an RPC appear to be processed correctly on the server but fail on the client

  4. having an RPC appear from the server not to return the result to the client but actually return the result on the client

Question 4 (1 points): Consider a system using two-phase commit that distributes a database across two worker machines A and B and uses a single coordinator machine C.

Suppose after preparing a transaction with machines A and B, machine C receives a vote to commit from machine A and machine B. Then, before machine C can act on that result, machine A goes down for a long time.

When machine A comes back up, what would be most appropriate for it to do first?

  1. make the changes that are part of the transaction that it previously voted to commit, then tell machine C that it did so

  2. resend its to vote to commit to machine C and wait for a reply

  3. send a message to machine B saying that the transaction is committed, then commit the transaction

  4. send a vote to abort to machine C

Quiz 13

Question 1 (1 points): Suppose we want to provide the ability to run commands on a remote server using a stateless server. With support from servers, which of the following features could we provide that would be consistent with the stateless design?
Select all that apply

  1. the ability to run two commands at a time

  2. a "change directory" operation that affects which directory the next command from a particular user runs in, regardless of what client machine they connect from

  3. a "change directory" operation that affects which directory the next command from a particular user runs in, but only if they use the same client machine to run that next command

Suppose an RPC call takes 1000 microseconds to complete plus an additional microsecond for every kilobyte of data transferred in the RPC call plus the time requires to run the corresponding RPC function on the server.

Question 2 (1 points): (see above) Suppose this RPC system is used by NFSv2. A client application to open a 2048KB file and read the last 1024KB of it 128KB at time and then closes it. Assume the client does not perform any caching of file data. The client already has the file ID for the directory, but is missing one for the file itself. Ignoring the time required to run the RPC functions on the server that lookup file data (and so just including the RPC overhead), about how much time is required for this operation in microseconds?

(Assume the client does not need to check the attributes of the file as part of opening it.)

Answer:

Question 3 (1 points): When programs run with special priviliges on behalf of other users (like set-user-ID programs), a major concern is time-to-check-to-time-of-use vulnerabilities. One common example of these is when a program checks if the user on whose behalf if it is running is allowed to access some file specified via a path, and then, later, it actually access the file, without verifying that the path referred to the same resource that was checked earlier.

What are some examples of operating system support that could be added to POSIX-like systems that would be helpful for avoiding these problems? (In the options, file mode bits refers to the very limited access control list POSIX supports via chmod.)

  1. a new version of the open() system call that takes a user ID to check against access control lists and file mode bits (and uses that user ID in addition to the user ID the current process is running as)

  2. tracking different user IDs for filesystem accesses and other priviliged operations (like accessing devices) and allowing a set-user-ID program to be marked as only changing one of these

  3. a system call for checking, given the path to a file, whether a particular user can access it

Consider a virtual machine implemented using trap-and-emulate without special hardware support for virtualization.

Suppose a program is running in the virtual machine and executes a system call to read input from the keyboard. The guest OS, while handling this system call, switches to another program and runs it in user mode. Eventually, the hypervisor detects keyboard input. As a result, it decides to simulate an interrupt for the keyboard. Then, the guess OS reads a control register from the keyboard controller. Then, the guest OS switches the original program and runs it in user-mode.

Question 4 (1 points): (see above) During the process described above, which of the above operations are likely involve in an exception (of any kind, including interrupts, traps, etc.) on the host machine (that is, an exception handled by the hypervisor)?
Select all that apply

  1. the program executing a system call

  2. the hypervisor simulating the keyboard interrupt for the guest OS

  3. the guest OS switching to another program and running it in user-mode

  4. the guest OS reading a control register from the keyboard ocntroller

Question 5 (1 points): (see above) If the hypervisor is implemented using shadow page tables, which of the above operations are likely involve changing which shadow page table is active (or clearing/reconstructing a large portion of the shadow page table)?
Select all that apply

  1. the program executing a system call

  2. the hypervisor simulating the keyboard interrupt for the guest OS

  3. the guest OS switching to another program and running it in user-mode

  4. the guest OS reading a control register from the [emulated] keyboard controller