All quizzes (key)

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

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

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.

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

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.)

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

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

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

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

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 _____

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

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 _____?

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?

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

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?

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

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:

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?

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

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

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

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

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:

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?

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

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 ______.

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

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?

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

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.)