Student ID
Login (studentXXX)
Computer Science 162 . of California, Berkeley Midterm Exam
October 10, 2019
Copyright By PowCoder代写 加微信 powcoder
TA Name and Section Time
Name of Students to your Left and Right
Name of Students in Front of You and Behind You
This is a closed book exam with one 2-sided page of notes permitted. It is intended to be a 90 minute exam. You have 110 minutes to complete it. The number at the beginning of each question indicates the points for that question. Write all of your answers directly on this paper. Make your answers as concise as possible. If there is something in a question that you believe is open to interpretation, please raise your hand to request clarification. When told to open the exam, put your Student ID on every page and check that you have them all. The final page is for reference.
By my signature below, I swear that this exam is my own work. I have not obtained answers or partial answers from anyone. Furthermore, if I am taking the exam early, I promise not to discuss it with anyone prior to completion of the regular exam, and otherwise I have not discussed it with anyone who took the early alternate exam.
X _______________________________________
Grade Table (for instructor use only)
Question: 1 2 3 4 5 6 7 Total Points: 1 20 20 19 20 20 0 100 Score:
Midterm Exam – Page 2 of 27 Student ID:
1. (1 point) Write your Student ID on every page of the exam.
Midterm Exam – Page 3 of 27 Student ID:
2. (20 points) Operating System Concepts
Choose either True or False for the questions below. You do not need to provide justifications.
(a) (1 point) Dual-mode operation allows the kernel to access memory of user processes, but prevents user processes from accessing memory of the kernel.
√ True ⃝ False
(b) (1 point) A thread can be a part of multiple processes. ⃝ True
(c) (1 point) In Unix-based operating systems, a process can read and write a file without
opening it.
(d) (1 point) In Unix-based operating systems, a process can exit without first closing the files
it has been reading/writing.
√ True ⃝ False
(e) (1 point) Switching between threads belonging to different processes typically has higher overhead than switching between threads belonging to the same process.
√ True ⃝ False
(f) (1 point) A user program may enforce a critical section by disabling interrupts. ⃝ True
(g) (1 point) A TCP socket (i.e., socket of type SOCK_STREAM) provides reliable, bidirectional
communication between processes on different hosts.
√ True ⃝ False
(h) (1 point) A pipe (i.e., output of a single call to pipe()) provides reliable, bidirectional communication between processes on the same host.
⃝ True √ False
(i) (1 point) An operating system provides a specific set of services to user programs, regard- less of the programming language they are written in, through syscalls.
√ True ⃝ False
(j) (1 point) An appropriate way for the operating system and user programs to cooperate is to allow programs to read variables maintained by the kernel.
⃝ True √ False
Midterm Exam – Page 4 of 27 Student ID:
Choose either True or False for the questions below and provide an explanation.
(k) (2 points) A kernel interrupt handler is a thread. ⃝ True
Solution: An interrupt handler is not independently schedulable. Started in response to an interrupt, not a scheduling event, the handler runs to completion, unless pre- empted by a higher priority interrupt. It may cause threads to be scheduled.
(l) (2 points) Once a file is opened, its entire contents can always be read into memory with a single call to read, assuming the file’s contents fit in memory.
⃝ True √ False
Solution: It will sometimes be the case, but in general one cannot expect read to transfer the entire file or even fill the buffer. It can read only a portion and returns the amount that was read.
(m) (2 points) List the three most important attributes of a thread that the operating system must maintain when the thread is not running.
Solution: PC, Stack pointer, Register values
(n) (2 points) What is a process?
Solution: Executing instance of a program. Operating system’s virtual machine ab- straction. Operating system’s unit of isolation. Address space, one or more threads of control, system resources such as open file descriptors.
Midterm Exam – Page 5 of 27 Student ID:
(o) (2 points) List what causes the transition from user mode to kernel mode.
Solution: Interrupt, Trap / Exception / Fault, Syscall (which is a form of exception, an int instruction in x86)
What causes the transition from kernel mode to user mode?
Solution: The kernel executing a “return from interrupt” instruction.
Midterm Exam – Page 6 of 27 Student ID:
3. (20 points) Processes, Threads and Concurrency
(a) (1 point) The scheduler in an operating system (check the single best answer): ⃝ May run any thread
⃝ Runs the highest priority ready thread
√ Selects the next ready thread to run according to a policy
⃝ Selects the thread that just completed I/O
(b) (2 points) The Base and Bound register approach provides which of the following (check
all that apply):
√ Memory protection between processes
Memory sharing between processes
Expandable heap and stack
√ Protection of the kernel from user processes
(c) (2 points) The paged virtual address approach provides which of the following (check all that apply):
√ Memory protection between processes
√ Memory sharing between processes
√ Expandable heap and stack
√ Protection of the kernel from user processes
(d) (2 points) In your Project 1, Task 2, the Pintos exec syscall creates a child process and starts it running. What is the roughly equivalent sequence of syscalls (provided through the C system library, i.e., unistd.h) needed to achieve this functionality?
Solution: fork(); execv()/execvp(). Create the process and then it loads the new executable into its address space.
(e) (2 points) A common approach to ensuring that a resource is released only after all users of it are done is to include a reference count. For example, the object representing a parent process may need to persist until all its children have exited.
i. Why do we need to acquire a lock, or do an equivalent synchronization operation, before performing operations on this reference count?
Solution: Incrementing and decrementing of the reference count involves a read- modify-write. This operation needs to be atomic.
ii. Describe another situation that occurs in systems implementation, other than a par- ent/child wait structure, where a reference count is useful.
Solution: Multiple options. Common answer will be determining that all pro- cesses that had opened a file have closed it, either explicitly or implicitly through exit.
Midterm Exam – Page 7 of 27 Student ID:
(f) (2 points) A call to pthread_mutex_lock typically takes longer to return when there is contention for the mutex, than when the mutex is uncontended. Explain your answer.
√ True ⃝ False
Solution: Under low contention the lock is likely to be free. And if busy, it will likely have few waiters. Whatever spinning is utilized to implement the lock is likely to clear quickly.
(g) (2 points) For kernel threads, one can use atomic memory operations, like test&set, to implement a lock in a manner that does not spin-wait. Explain your answer.
⃝ True √ False
Solution: The testandset can be used as a guard to implement the critical section of the lock/unlock routine, but the guard itself may be busy when a thread attempts to entr because other threads are attempting to operate on (potentially other) locks and there is no means to suspend.
(h) (2 points) For this question, assume calls to the pthread library always succeed. void* worker(void* arg) {
printf(“%d”, (int) arg);
pthread_exit(NULL);
int main(int argc, char** argv) {
pthread_t tid[4];
for (i = 0; i != 4; i++) {
pthread_create(&tid[i], NULL, worker, (void*) (i + 1));
for (i = 0; i != 4; i++) {
pthread_join(tid[i], NULL);
printf(“%d”, 5);
Which of these statements about the above program are true? Check all that apply:
√ When the program is run, its output might be 21345.
When the program is run, its output might be 1235.
√ The four worker threads might exit in the same order that they were created. √ The four worker threads might exit in a different order than they were created. √ When the printf statement in main is reached, all four worker threads are
guaranteed to have called pthread_exit.
When the printf statement in main is reached, the operating system is guaran- teed to have fully reclaimed the resources associated with all four worker threads.
Midterm Exam – Page 8 of 27 Student ID:
(i) (2 points) Consider the following program:
void luffy() {
sema_down(&loguetown);
sema_up(&marineford);
sema_down(&skypeia);
printf(“L: I found the One Piece!”);
void blackbeard() {
sema_down(&skypeia);
sema_up(&skypeia);
sema_down(&loguetown);
printf(“B: The One Piece is mine!”);
void akainu() {
sema_down(&marineford);
sema_down(&loguetown);
sema_up(&skypeia);
printf(“A: I’ve secured the One Piece.”);
void main() {
thread_create(luffy);
thread_create(blackbeard);
thread_create(akainu);
i. Assume all semaphores are initialized to a value of one. Which of these lines could be printed? (check all that apply)
√ A: I’ve secured the One Piece. √ B: The One Piece is mine!
√ L: I found the One Piece!
√ (nothing is printed)
ii. Is it possible for multiple of these lines to be printed in a single run of the program? If Yes, explain which and how. If No, explain why not.
⃝ Yes √ No
Solution: loguetown is downed in every path, so only one can ever succeed. The other two will always hang.
Midterm Exam – Page 9 of 27 Student ID:
(j) (3 points) Implement strcpy from the C standard library. You may assume that src and dest point to allocated memory buffers large enough to store the string in src, including its null terminator (but not necessarily any larger), and that the two buffers do not overlap. You may use strlen, but not memcpy.
char* strcpy(char* dest, const char* src) {
for (i = 0; src[i] != ’\0’; i++) {
dest[i] = src[i];
dest[i] = ’\0’;
return dest;
Alternate Solution: Many possibilities, but they should not be more than about 8 lines.
char* strcpy(char* dest, const char* src) {
char* tgt = dest;
while (*src != ’\0’) {
*tgt++ = *src++;
*tgt = ’\0’;
return dest;
char* strcpy(char* dest, const char* src) {
for (i = 0; i <= strlen(src); i++) {
dest[i] = src[i];
return dest;
Explain why strcpy can be hazardous to use within the operating system.
Midterm Exam - Page 10 of 27 Student ID:
Solution: strcpy is hazardous because it does not ensure that the copy will not write past the end of the destination buffer. Safer versions, such as strlcpy, should be used instead.
Midterm Exam - Page 11 of 27 Student ID:
4. (19 points) Scheduling, Performance, and Deadlock (a) (10 points) Comparing schedulers
We are going to compare the behavior of four schedulers on a workload consisting of 4 tasks:
• Task A arrives at tick 0 and uses the CPU for 4 ticks.
• Task B arrives at tick 1 and uses the CPU for 7 ticks.
• Task C arrives at tick 2 and uses the CPU for 1 tick, issues I/O that takes 4 ticks, and then uses the CPU for 1 tick.
• TaskDarrivesattick3anddoes1tickCPU,1tickI/O,1CPU,1tickI/O,and1 tick CPU.
This workload is illustrated below as if each executes on its own dedicated CPU. 01234567
A a1 a2 a3 a4
b1 b2 b3 b4 b5 b6 b7 c1 - - - - c6 d1 - d3 - d5
You are to schedule these onto a single CPU. When one does I/O, another ready task can run on the CPU. When a task completes it I/O ticks, it is ready to run on the CPU. If two tasks finish I/O in the same tick, the one that started I/O first is treated as arriving first.
Consider four schedulers: first-come-first-serve (FCFS), preemptive round-robin with a quanta of 2 ticks (RR-2), shortest-remaining-time-first with quanta of 2 where only re- maining CPU time is considered, and completely fair scheduler (CFS) with a quanta of 2 where only the CPU time consumed is considered.
Below is a scratch area for you to keep track of what each scheduler runs when. We have filled in the FCFS scheduler for you. Note that D runs as soon as C blocks for I/O, and it gets to run again before C’s longer I/O finishes, after its I/O completes. We will not grade the grid, but it may help you work out the questions.
Midterm Exam - Page 12 of 27 Student ID:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 FCFS a1 a2 a3 a4 b1 b2 b3 b4 b5 b6 b7 c1 d1 - d3 - c6 d5
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 FCFS a1 a2 a3 a4 b1 b2 b3 b4 b5 b6 b7 c1 d1 - d3 - c6 d5
RR-2 a1a2b1b2c1a3a4d1b3b4c6d3b5b6d5b7 SRTF a1 a2 c1 a3 a4 d1 b1 b2 c6 d3 b3 b4 d5 b5 b6 b7 CFS a1 a2 b1 b2 c1 d1 a3 a4 d3 c6 d5 b3 b4 b5 b6 b7
Now, answer the following questions.
i. (1 point) All three preemptive schedulers completely mask the waits for I/O with CPU
activity, resulting in 100% utilization.
√ True ⃝ False
ii. (1 point) In all the schedules, B starts running before C. ⃝ True
iii. (1 point) In all three preemptive schedulers, B is the last to finish.
√ True ⃝ False
iv. (1 point) A has a smaller wait time (number of ticks where it is ready to run, but waiting) in SRTF than it has in the other three schedulers.
⃝ True √ False
v. (2 points) Which has the lowest average response time? (Response time of a task is defined as the number of ticks from its arrival to its completion.)
⃝FCFS ⃝RR √SRTF ⃝CFS
vi. (2 points) Which has the smallest range of response times? ⃝FCFS √RR ⃝SRTF √CFS
vii. (2 points) Which has the smallest range of wait times? ⃝FCFS √RR ⃝SRTF √CFS
Solution: Depending on how you break ties and whether you account for sleeper fairness, it’s possible to get either RR or CFS for the last two parts. So, we accepted both answers.
(b) (2 points) What is the difference between an open system and a closed system?
Midterm Exam - Page 13 of 27 Student ID:
Solution: An open system is one where requests are issued independently of their completion. A closed system is one where issuing subsequent requests depends on the completion of prior ones.
Give an example that behaves as a closed system.
Solution: There are many, but request-response protocols in general.
(c) (2 points) List the four conditions required for deadlock to happen.
Solution: The four conditions required for deadlock are: (1) bounded resources, (2) hold-and-wait, (3) no preemption, and (4) circular wait.
(d) (3 points) Each of the following three functions runs in a separate thread. Assume that the three threads are all created and ready to run.
mutex_t morph = INITIAL_FREE;
mutex_t levelup = INITIAL_FREE;
void Pikachu() {
lock(&morph);
lock(&levelup);
store some electricity
unlock(&levelup);
unlock(&morph);
void Celebi() {
lock(&morph);
lock(&levelup);
guard the ilex forest
unlock(&morph);
unlock(&levelup);
void Mew() {
lock(&levelup);
lock(&morph);
become invisible
unlock(&levelup);
unlock(&morph);
i. Describe an execution sequence that would result in deadlock.
Midterm Exam - Page 14 of 27 Student ID:
Solution: If Pikachu gets scheduled and acquires the morph lock, and then Mew gets schedule and acquires the levelup lock, then neither will be able to acquire the second lock.
ii. Does preemptive scheduling solve the problem?
Solution: No. The acquisition of the lock is not undone.
iii. Describe how you would fix the code so that deadlock would not occur.
Solution: Have all three acquire the locks in the same order.
(e) (2 points) If a thread reads a 10MB file with a transfer rate of 5MB/s with 100ms total overhead to start and complete the read, for how many 50ms quanta is the thread blocked?
2100 ms = 42 quanta 50 ms
If another thread was computing at a rate of 100 GFLOP/s, how many floating point operations could it get done in this time?
Solution: It does 1 billion FLOP on 10ms, for 5 billion in quanta. 210 Billion FLOPs during the I/O.
Midterm Exam - Page 15 of 27 Student ID:
5. (20 points) Operating System Implementation
Olaf, Kristoff, Anna, and Elsa are in a group for their CS 162 project, and they have just finished Project 1. Olaf, being an eager student, wants to extend Pintos by adding additional support for inter-process communication (IPC).
(a) (2 points) List two types of IPC that are implemented in Pintos as part of Project 1.
Solution: A solution that mentions any two of the following would receive full credit: exit codes, command line arguments, and file I/O. Mentioning wait and exec system calls was not enough to receive credit.
(b) (2 points) Kristoff suggests adding a pipe system call to Pintos. It would work the same way as in Linux; a pipe is created in the kernel, and the calling process obtains read and write file descriptors to access the pipe. Can Kristoff’s pipe system call be used for IPC in Pintos? If it can be used, explain how; if not, explain why not.
Solution: No, it cannot be used for IPC in Pintos. Because child processes do not inherit file descriptors in Pintos, there is no way for two different processes to obtain file descriptors for the same pipe.
(c) (16 points) Anna suggests providing IPC via a global key-value store. Each process can PUT a single key-value pair, if the key does not already exist, and can GET a value by looking it up by key. When a process exits, its key-value pair is removed from the key-value store.
Keys and values are strings, whose lengths can be up to MAX_KEY_LEN and MAX_VAL_LEN, respectively. You may assume these constants are reasonably small (e.g., less than 162). The empty string may not be used as a key.
You may wish to look at all parts of this question first, before starting to answer it.
Solution: A common solution was to put the posted key, as a char* or char array, in struct thread. Another common solution was to add a struct kv* field to struct thread. Our solution, which embeds struct kv into struct thread directly, does not have to ever call malloc, and therefore doesn’t have to deal with malloc failing (though we didn’t take off points for not handling that).
i. The group is trying to determine what new data structures they must add to Pintos to support this functionality. Help them finish their design by filling in the blank lines below in their new struct kv.
struct kv {
char key[ MAX_KEY_LEN + 1
char value[ MAX_VAL_LEN + 1
struct list_elem elem;
Midterm Exam - Page 16 of 27 Student ID:
ii. Determine how to extend struct thread to support Anna’s IPC functionality. You may not need to use all of the blank lines.
struct thread {
/* Pre-existing members (not shown) */
/* Add additional members on the lines below. */
struct kv keyvalue;
bool has_put;
unsigned magic;
iii. Determine what additional global variables must be added to syscall.c, and extend syscall_init to do any necessary initialization work. You may not need to use all of the blank lines.
/* This is used by the group’s Project 1 implementation. */
static struct lock fs_lock;
/* Add additional global variables on the lines below. */
static struct list kv_list;
static struct lock kv_lock;
void syscall_init(void) {
intr_register_int(0x30, 3, INTR_ON, syscall_handler, "syscall");
lock_init(&fs_lock);
/* Perform any necessary initialization work. */
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com