CS 162 Operating Systems and System Programming
Fall 2020 Midterm 1
INSTRUCTIONS
This is your exam. Complete it either at exam.cs61a.org or, if that doesn’t work, by emailing course staff with your solutions before the exam deadline.
Copyright By PowCoder代写 加微信 powcoder
This exam is intended for the student with email address
For questions with circular bubbles, you should select exactly one choice. # You must choose either this option
# Or this one, but not both!
For questions with square checkboxes, you may select multiple choices. 2 You could select this choice.
2 You could select this one too!
You may start your exam now. Your exam is due at
Exam generated for
regarding the exam questions or answers in any capacity.
If there is something in a question that you believe is open to interpretation, please make a private post on Piazza asking for clarification. We will issue an announcement if we believe your question merits one.
We will overlook minor syntax errors in grading coding questions. You do not have to add necessary #include statements. For coding questions, the number of blank lines you see is a suggested guideline, but is not a strict minimum or maximum. There will be no limit on the length of your answer/solution.
Student ID
Please read the following honor code: “I understand that this is a closed book exam. I hereby promise that the answers that I give on the following exam are exclusively my own. I understand that I am allowed to use one 8.5×11, double-sided, handwritten cheat-sheet of my own making, but otherwise promise not to consult other people, physical resources (e.g. textbooks), or internet sources in constructing my answers.” Type your full name below to acknowledge that you’ve read and agreed to this statement.
1. (22 points) True/False
Please EXPLAIN your answer in TWO SENTENCES OR LESS (Answers longer than this may not get
credit!). Also, answers without any explanation GET NO CREDIT! a) (2 points)
1 Given any two threads A and B, thread A is always able to read data from thread B’s stack. True
# False 2 Explain.
b) (2 points)
1 Given any two threads A and B, thread A is always able to read data from thread B’s heap.
True # False
Threads of the same process share an address space. (It was clarified during the exam that thread A and B belong to the same process.)
Exam generated for
c) (2 points)
1 A pointer will point to the same (virtual) memory address before and after a successful call to fork().
True # False
2 Explain.
d) (2 points)
1 A system call is a function linked into a user-mode program that executes a “transition to kernel
mode” instruction, then begins to execute arbitrary code with kernel privileges. # True
False 2 Explain.
e) (2 points)
1 A system call allows a process to execute certain instructions in the kernel’s code in user mode.
# True False
2 Explain.
f) (2 points)
1 Without system calls, user programs cannot intentionally transfer control from a user program to the
kernel. # True False
Threads of the same process share an address space. (It was clarified during the exam that thread A and B belong to the same process.)
fork() creates an exact copy of the process address space.
System calls utilize a single atomic operation to both (1) make a transition from user-mode to kernel-mode and (2) begin executing one of a small number of pre-determined handlers in kernel space.
System calls run predefined kernel system call handlers in kernel mode: the instructions are run in kernel mode.
Exam generated for
g) (2 points)
1 Without interrupts, the kernel cannot intentionally transfer control from a user program to the kernel.
True # False
2 Explain.
h) (2 points)
User programs could intentionally trap to transfer control to the kernel via an excep- tion. (Comment: some students put pthread_yield()/yield(), but pthread_yield() calls sched_yield(), which is a syscall in Linux)
One advantage of matching every user-level thread with a kernel thread is that the resulting user- level thread can execute arbitrary instructions in kernel mode simply by using a message channel to communicate with the kernel thread.
# True False
The kernel would have to wait for user programs to voluntarily transfer control to the kernel.
The presence of the kernel-thread/stack means that the corresponding user-mode thread can sleep in the kernel during I/O operations without blocking other threads.
i) (2 points)
1 Every user-level thread must have a unique kernel-level thread in order to facilitate multithreading
(and allow concurrency). # True
False 2 Explain.
j) (2 points)
1 After a thread is put on the queue for a condition variable, the thread will eventually get to run until
completion. # True
It is possible for user-level threads to be multiplexed at user-level by a user-level library.
Exam generated for
k) (2 points)
1 Itispossibletocreateacriticalsectionwithoutdisablinginterruptsandwithoutanylocks,semaphores,
or condition variables. True
# False 2 Explain.
l) (2 points)
1 Spinlocks–threads that spin in a loop until the lock is released–always perform worse than traditional
blocking locks. # True
False 2 Explain.
m) (2 points)
1 To create a critical section in a uniprocessor, the user can just disable interrupts to avoid being
preempted. # True
False 2 Explain.
n) (2 points)
1 Because cond_wait() releases the condition variable lock in its implementation, after the thread is
woken up, the thread is explicitly responsible for calling lock_acquire. # True
The thread may never get woken up if other threads crash/hang. Also the condition can always be false.
Atomic operations like compare&swap and test&set are implemented in hardware.
In some cases, spinlocks can waste fewer cycles than putting a thread to sleep and waking them up. For example, if the time taken to acquire a lock is shorter than the time taken to put a thread to sleep and wake it up.
The user cannot disable interrupts: the kernel has to do so.
Exam generated for
o) (2 points)
1 When using PintOS lists, a struct can only have one list_elem.
# True False
2 Explain.
p) (2 points)
1 In PintOS, every user program will eventually call the exit syscall (assuming that the kernel does not
kill the program due to a fault). True
# False 2 Explain.
q) (2 points)
1 Since PintOS doesn’t have a fork syscall, the exec syscall implicitly spawns a new child process.
True # False
2 Explain.
r) (2 points)
1 In PintOS, if open is called twice on the same file in the process (without anything else happening in between), the two file descriptors can be used interchangeably (similar to what would happen if dup() was used to generate the second file descriptor).
# True False
cond_wait() reacquires the lock before returning.
The struct thread in Pintos has two list_elems, allelem and elem.
When main returns to _start, it issues an exit syscall.
In process_execute, a new thread is created for the child.
Exam generated for
s) (2 points)
1 In PintOS, the kernel stack can grow dynamically to handle deeply recursive computations.
# True False
2 Explain.
t) (2 points)
1 In PintOS, both user and kernel virtual memory is per process.
# True False
2 Explain.
u) (2 points)
1 In PintOS, when accessing an unmapped user virtual address, a user thread will page fault while a
kernel thread will not. # True
False 2 Explain.
v) (2 points)
Say two processes on the same machine open the same file, and that there are no race conditions or errors in doing so – that is, open returns a valid file descriptor to both processes. If either process makes a call to remove this file from the filesystem, the other process cannot write to its file descriptor any longer.
# True False
Each open should return a new file descriptor that must be closed independently and do not share the same position.
The kernel stack must fit on a 4KiB page and cannot grow dynamically.
Kernel virtual memory is global.
A kernel will still page fault when accessing an unmapped user virtual address.
Exam generated for
w) (2 points)
No – the file will be available to other processes that have the file open. From the man pages: If the removed name was the last link to a file and no processes have the file open, the
file is deleted and the space it was using is made available for reuse. If the name was
the last link to a file, but any processes still have the file open, the file will remain in existence until the last file descriptor referring to it is closed.
Assume test.txt doesn’t already exist.
char buf[BUFSIZE];
memset(buf, ‘a’, 100);
int fd = open(“test.txt”, O_CREAT|O_RDWR);
lseek(fd, BUFSIZE, SEEK_SET);
lseek(fd, 0, SEEK_SET);
read(fd, buf, BUFSIZE);
Afterwards, buf will contain BUFSIZE a characters. True
# False Explain.
read will return 0 since the file is empty.
x) (2 points)
1 After calling exec, a process can read from and write to the same file descriptors that the original
process had open, even though the original process’s address space has been replaced. True
# False 2 Explain.
y) (2 points)
1 Calling pipe on an array like int fds[2]; creates a read and write stream that local processes can use for unidirectional IPC. Under the hood, a pipe is implemented as a buffer in user space where the read end sits at the 0th index of the pipe and the write end sits at the 1st index of the pipe.
# True False
exec does not destroy the process’s file descriptor table.
Exam generated for
z) (2 points)
When using sockets, the server process spins on a while (true) loop, awaiting new connections. When a connection arrives, the request is dequeued, the server calls accept and creates a new socketed connection, which returns a descriptor referencing the socket that the server process uses to service the client’s future requests. Both the server and the client have the responsibility of closing their socket descriptors.
# True False
pipe creates two file descriptors, and pipes are a buffer in kernel space.
The server process does no such spinning. It hangs on the call to accept, which has already been called by the time a request gets dequeued from the request queue.
aa) (2 points)
1 Each client hardware device (with a unique IP address), can have many individual sockets connected
to the same server/port combination, such that the server can differentiate between them. True
# False 2 Explain.
2. (16 points) Multiple Choice
Each connection’s 5-tuple allows this.
Exam generated for
#include
#include
int main() {
for (int i = 0; i < 3; i++) {
return 0; }
20 21 2 3 4 5 6 7 28
Every iteration of the loop has a call to fork() in every running instance of this process.
Least successful case: fork() when i=0 fails. fork() when i=1 succeeds, and then one of the two calls to fork() when i=2 succeed. There are 2 successful fork calls (creating 2 new processes) out of 4 fork calls total.
Most successful case: Every individual call to fork succeeds, so the number of processes duplicates every iteration. 1+2+4=7 out of 7 calls to fork() are successful, for a total of 7 new processes.
Exam generated for
#include
#include
int main() {
for (int i = 0; i < 3; i++) {
return 0; }
20 21 22 23 4 5 6 7 28
Every iteration of the loop has a call to fork() in every running instance of this process.
Least successful case: fork() when i=0 fails. fork() when i=1 succeeds, and then one of the two calls to fork() when i=2 succeed. There are 2 successful fork calls (creating 2 new processes) out of 4 fork calls total.
Most successful case: Every individual call to fork succeeds, so the number of processes duplicates every iteration. 1+2+4=7 out of 7 calls to fork() are successful, for a total of 7 new processes.
c) (2 pt) Which of the following need to be saved and restored on a context switch between two threads in the same process?
Computational registers (integer and floating point) 2 Page-table root pointer
2 Buffered data in streams opened with fopen
2 Contents of the file descriptor table
Stack pointer register
Each thread has its own registers and stack, so we need to restore the computation registers and the stack pointer register. Threads in the same process share an address space and file descriptor table, so we do not need to save the page-table root pointer or the fd table. Buffered data is already in memory, so we do not need to save or restore that, either.
Exam generated for
d) (2 pt) Which of the following are valid ways for two threads in the same process to communicate? Reading/writing to a memory address in one thread’s stack
Reading/writing to a memory address in the process’s heap
2 Reading/writing to the same location in one thread’s kernel’s stack Reading/writing to an open FILE*
Reading/writing to a pipe
Reading/writing to sockets
Each process has its own address space and threads within the same process share that address space, though user programs may not access the kernel stack. Files, pipes, and sockets are all handled by the kernel.
e) (2 pt) Which of the following are valid ways for two threads in different processes to communicate? 2 Reading/writing to a memory address in one thread’s stack
2 Reading/writing to a memory address in the process’s heap
2 Reading/writing to the same location in one thread’s kernel’s stack
Reading/writing to an open FILE* Reading/writing to a pipe
Reading/writing to sockets
Each process has its own address space and threads within the same process share that address space, though user programs may not access the kernel stack. Files, pipes, and sockets are all handled by the kernel.
f) (2 pt) Which of the following are atomic operations? 2x -= 100
test&set
cond_wait
2 process_execute (from Project 1!) 2 pthread_mutex_init
test&set is an atomic instruction implemented in hardware. cond_wait atomically releases a lock/acquires a lock.
Exam generated for
g) (2 pt) Which of the following are true about condition variables? Allows for waiting in a critical section
2 Are commutative just like semaphores
2 Are sometimes subjected to spurious wakeup when dealing with Hoare semantics Avoids busy waiting
Condition variables avoid busy waiting by allowing for the behavior of waiting inside of a critical section. Semaphores are commutative (you can sema_down() before sema_up()), while condition variables are not (you cannot cond_signal() before cond_wait()). In Hoarse semantics, control is transferred to the awoken thread immediately, forgoing spurious wakeups where the wait condition has not been satisfied.
h) (2 pt) Which of the following are false about condition variables?
2 Allows for waiting in a critical section
Are commutative just like semaphores
Are sometimes subjected to spurious wakeup when dealing with Hoare semantics 2 Avoids busy waiting
Condition variables avoid busy waiting by allowing for the behavior of waiting inside of a critical section. Semaphores are commutative (you can sema_down() before sema_up()), while condition variables are not (you cannot cond_signal() before cond_wait()). In Hoarse semantics, control is transferred to the awoken thread immediately, forgoing spurious wakeups where the wait condition has not been satisfied.
i) (2 pt) When setting up the user stack in PintOS, which of the following properties must be satisfied? Select all that apply.
The stack starts at the very top of the user virtual address space, in the page just below the virtual address PHYS_BASE.
2 The stack pointer, esp, must be aligned to a 16-byte boundary after pushing the return address.
2 The order of words (ex: /bin/ls -l foo bar) must be in the same order as they were inputted on
the top of the stack.
The value of the return address doesn’t have to be any specific value.
j) (2 pt) The kernel in PintOS must verify pointers before accessing user memory. Which of the following must be true about a valid pointer? Select all that apply.
The pointer is located in mapped virtual memory. 2 The pointer is located above PHYS_BASE.
2 The pointer can be a null pointer.
2 None of the Above
Null pointers are not valid. Pointers above PHYS_BASE aren’t valid either, because user programs are not allowed to access kernel memory.
Exam generated for
k) (2 pt) In Project 1 you had to implement the wait syscall. A common implementation was to create some shared struct with a reference count, or ref_cnt, that was discussed in section. What are some of the properties of this ref_cnt? Select all that apply.
2 The ref_cnt can grow and shrink depending on the number of children a parent thread can have.
The ref_cnt must be synchronized with some sort of lock as different threads can concurrently read
and write to it.
The ref_cnt could start at 2, to represent the starting relationship from the parent and from the child.
2 None of the Above
ref_cnt does not track how many children a thread has. The other options are true.
l) (3 pt) Assume all calls to read(), write(), and fork() succeed. Suppose that montymole.txt was
empty before running this block of code. The following code was run:
int main(int argc, char** argv) {
int fd1 = open(“montymole.txt”, O_WRONLY);
int fd2 = open(“montymole.txt”, O_WRONLY);
write(fd1, “mole”, 4);
write(fd2, “whack”, 5);
write(fd2, “mole”, 4);
write(fd1, “mole”, 4);
write(fd1, “mole”, 4);
close(fd1);
close(fd2);
Which of the following could be the content of “montymole.txt”?
whacmolemole
2 whacmolek
2 molewhackmolemolemole 2 whackmolemole
In this problem, the two calls to open() create two open file descriptions, which have independent file offsets. Going through each write call, the file looks like: mole -> whack -> whackmole -> whacmolee -> whacmolemole
Exam generated for
empty before running this block of code. The following code was run:
void new_thread(void* arg) {
int* fd = (int*) arg;
write(*fd, “whackwhackmole”, 14);
int main(int argc, char** argv) {
int fd1 = open(“montymole.txt”, O_WRONLY);
pthread monty_mole;
pthread_create(&monty_mole, NULL, new_thread,(void*) &fd1);
write(fd1, “mole”, 4);
close(fd1);
Which of the following could be the content of “montymole.txt”?
molewhackwhackmole whackwhackmolemole 2 molewhackwhackwhack 2 molewhack
2 whackwhackmole
In this problem, both the main thread and the created thread write to the same fd, so both threads share
a file offset. Their writes will append to the file instead of overwriting the file.
n) (3 pt) Assume all calls to read(), write(), and fork() succeed. Suppose that montymole.txt was empty before running this block of code. The fol
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com