Blog

COMP 3511 Spring 2021 Midterm Exam Part I. Multiple Choices [30*1.5 points] [Introduction] 1. In a Von Neumann Architecture, a processing unit contains a/an _____ and processor registers. A. arithmetic logic unit (ALU) B. instruction register (IR) C. program counter (PC) D. all of the mentioned Answer: A Desc: see 1.24 2. Which of the following events will directly trigger an interrupt A) kernel code execution C) user code execution B) I/O job execution D) I/O job completion Answer: D Desc: see 1.26 [Operating System Structures] 1. The two separate modes of operation in operating system are_____. A. supervisor mode and system mode B. physical mode and logical mode C. user mode and kernel mode D. kernel mode and privileged mode Answer: C Desc: see 2.43 2. _____ provide an interface to the services provided by an operating system. A. Inter-process communications B. Remote procedure calls C. System calls D. User interfaces Answer: C Desc: see 2.14 3. Which of the following operating system structures is adopted by original UNIX A) layered structure B) microkernel C) monolithic structure D) modular approach (COMP3511)[2021](s)midterm~=pcidkjhk^_28633.pdf
downloaded by shhoaj from
http://petergao.net/ustpastpaper/down.php course=COMP3511&id=23 at
2022-02-11 10:54:23. Academic use within HKUST only. Answer: C Desc: see 2.41 4. The _____________ refers to the number of processes in the memory. A. program counter B. degree of multi-programming C. long-term scheduler D. CPU scheduler Answer: B Desc: see 3.14 5. Based on the Amdahl’s Law (speedup<=1/(S+(1-S)/N), where S is serial portion and N is the number of processing cores), what is the speedup gain for an application that is 30% serial and we run it on a machine with 7 processing cores A. 2 B. 2.5 C. 3 D. 3.5 Answer: B Desc: 1/(0.3+(1-0.3)/7) = 2.5 [Processes] 1. In operating system, each process has its own_____. A. address space B. local/global variables and open files C. pending alarms, signals and signal handlers D) all of the above Answer: D Desc: see 3.5 2. Which of the following sections of a process contains temporary data like function parameters, return addresses and local variables A. text section B. data section C. heap D. stack Answer: D Desc: see 3.5 3. Which of the following selects from among the processes that are in the ready queue to execute on the CPU A) Short-term scheduler B) Medium-term scheduler C) Long-term scheduler D) Context switcher Answer: A Desc: see 3.17 (COMP3511)[2021](s)midterm~=pcidkjhk^_28633.pdf downloaded by shhoaj from http://petergao.net/ustpastpaper/down.php course=COMP3511&id=23 at 2022-02-11 10:54:23. Academic use within HKUST only. 4. During process creation with fork(), which of the following is incorrect A. The child process can run concurrently with the parent. B. The child process can call wait() in order to finish earlier than the parent. C. The child process can call exec() in order to load a new program into it. D. The child can be an exact duplication of the parent. Answer: B Desc: see 3.28 5. Which of the following statement about the pipes is not true A. Named pipes allow bi-directional communication. B. Only the parent and child processes can use ordinary pipes for communication. C. Name pipes cease to exist after the communicating processes have finished. D. Reading and writing to ordinary pipes on both UNIX and Windows systems can be performed like ordinary file I/O. Answer: C Desc: see 3.56-3.57 6. Which of the following events might be able to force a process to leave the CPU A) make a fork system call B) make an I/O request C) interrupt D) all of the above Answer: D Desc: see 3.20 7. How many processes will be created by the following C code snippet (suppose all fork() are normal) (Hits: In C language, if State1 is true, “State1||State2” will directly return true without checking State2) A. 3 B. 4 C. 5 D. 6 Answer: C 8. How many processes will be created by the following C code snippet (suppose all fork() are normal) A. 3 if( fork() || fork() ) { fork(); } for( int i = 0; i < 3 ; ++i ){ if ( fork() == 0 ) fork(); } (COMP3511)[2021](s)midterm~=pcidkjhk^_28633.pdf downloaded by shhoaj from http://petergao.net/ustpastpaper/down.php course=COMP3511&id=23 at 2022-02-11 10:54:23. Academic use within HKUST only. B. 8 C. 27 D. 64 Answer: C [Threads] 1. Which of the following is not in the Thread Control Block (TCB) A. Execution state B. Scheduling information C. Pointer to enclosing process D. Process identifier Answer: D Desc: see 4.15 2. Which of the following refers to the capability to allow multiple tasks to make progress on the single processor A) parallelism B) concurrency C) data parallelism D) task parallelism Answer: B Desc: see 4.9 3. Which of the following is not true about multithreading models A. Many-to-one means many user-level threads are mapped to single kernel thread. B. One-to-one model provides more concurrency than many-to-one model. C. The many-to-many model is easy to implement in practice. D. Most operating systems now use one-to-one model. Answer: C Desc: see 4.20 – 4.25 4. Thread-local storage is data that ____. A. is not associated with any processes. B. has been modified by the thread, but not yet updated to the parent process. C. is generated by the thread independent of the thread’s process. D. is unique to each thread. Answer: D Desc: see 4.34 [CPU Scheduling] 1. CPU Scheduling decisions may take place in ______. A. Switches from running to waiting state B. Process terminates C. Switches from running to ready state D. all of the above. (COMP3511)[2021](s)midterm~=pcidkjhk^_28633.pdf downloaded by shhoaj from http://petergao.net/ustpastpaper/down.php course=COMP3511&id=23 at 2022-02-11 10:54:23. Academic use within HKUST only. Answer: D Desc: see 5.6 2. The main problem with a priority scheduling algorithm is _____. A. how to set the prority of a process B. some processes may never execute C. how to determine the length of the next CPU burst D. how to determine the length of the time quantum Answer: B Desc: see 5.24 3. For RR scheduling, when the time quantum q gets too large, it will degenerate to ______ A) SJF B) FCFS C) Shortest-remaining-time-first D) Multilevel queue Answer: B Desc: see 5.14 4. Which of the following scheduling algorithms must be non-preemptive A. FCFS B. SJF C. Priority Scheduling D. Multi-level Feedback Queue Answer: A Desc: see 5.11 5. In multilevel feedback queue algorithm, which of the following statement is true A. Prior knowledge on the next CPU burst time is required for scheduling. B. Classification of ready queue is permanent. C. It handles interactive jobs well by delivering similar performance as SJF. D. It won’t suffer from starvation problem. Answer: C Desc: see 5.29-5.31 6. Which of the following statement about real-time CPU scheduling is true A. Real-time scheduling doesn’t demand performance guarantee. B. In hard real-time systems, a task can be serviced after its deadline. C. Soft real-time systems guarantee only that the process will be prioritized over non-critical processes. D. The scheduler for a real-time system must support a priority-based algorithm without preemption. Answer: C Desc: see 5.45 7. Which of the following scheduling algorithms are free from starvation (COMP3511)[2021](s)midterm~=pcidkjhk^_28633.pdf downloaded by shhoaj from http://petergao.net/ustpastpaper/down.php course=COMP3511&id=23 at 2022-02-11 10:54:23. Academic use within HKUST only. 1. FCFS; 2. Non-preemptive SJF; 3. Preemptive SJF; 4. Round Robin; 5. Multi-level Queue A) 1 4 B) 1 2 4 C) 1 3 4 D) 1 2 4 5 Answer: A [Synchronization Tools] 1. Mutual exclusion implies that ____________ A. if a process is executing in its critical section, then no other process can be executing in their critical sections B. if a process is executing in its critical section, then only one of the other processes can be executing in its critical section C. if a process is executing in its critical section, then all the resources of the system must be blocked until it finishes execution D. none of the above Answer: A Desc: see 6.11 2. A solution to the critical section problem does not have to satisfy which of the following requirements A. mutual exclusion B. progress C. synchronization D. bounded waiting Answer: C Desc: See 6.11 3. A situation where several processes access and manipulate the same data concurrently and the outcome of the execution depends on the particular order in which access takes place is called ____. A. data consistency B. race condition C. aging D. starvation Answer: B Desc: see 6.9 4. Suppose the binary variable lock is initialized to be 0, which of the following can be an implementation of the entry section to solve the critical-section problem A. while (compare_and_swap(&lock, 0, 1) == 0), do nothing; B. while (compare and swap(&lock, 1, 0) != 0), do nothing; C. while (test_and_set(&lock)), do nothing; D. while (!test_and_set(&lock)), do nothing; Answer: C Desc: see 6.16-6.18 (COMP3511)[2021](s)midterm~=pcidkjhk^_28633.pdf downloaded by shhoaj from http://petergao.net/ustpastpaper/down.php course=COMP3511&id=23 at 2022-02-11 10:54:23. Academic use within HKUST only. Part II. Calculations [55 points] 1. [18 Points] Process and fork() 1) [5 points] What is the total number of processes in the following code Please elaborate (suppose all fork() are normal). #include #include #include int main() { pid_t pid1, pid2; pid1 = fork(); pid2 = fork(); if ( pid1 > 0 ) if ( pid2 == 0 ) fork(); return 0; } Answer: There are 5 processes. After the first two “fork()”s, there would be 4 processes. And only one process satisfies “pid1>0”and “pid2==0”, thus the third “fork” will create only one more process. Totally there are 5 processes. 2) [5 points] Consider the following code segments, what is the total number of processes Please elaborate (suppose all fork() are normal). if( fork() == 0) { for (int i = 0; i < 5; i++) if ( fork() == 0 ) fork(); } fork(); Answer: There are total (35+1)*2 processes (2 points). The first fork() creates one child. The second fork(), which is run by the child process, generates 35 child processes. The third fork() is run by the original process and the 35 child processes. Thus in the end there will be (35+1)*2 processes. 3) [8 points] Answer the questions according to the code below. (COMP3511)[2021](s)midterm~=pcidkjhk^_28633.pdf downloaded by shhoaj from http://petergao.net/ustpastpaper/down.php course=COMP3511&id=23 at 2022-02-11 10:54:23. Academic use within HKUST only. int main(void) { printf(“An”); if ( fork() == 0 ) { printf(“Bn”); } else { printf(“Cn”); _____A_____ } printf(“Dn”); exit(0); } a) [2 points] If the code at the A is empty, list all possible output. b) [2 points] If the code at A is: wait(NULL); list all possible output. c) [4 points] If the code at A is: printf(“En”); list all possible output. Answer: 1) ABDCD; ABCDD; ACBDD; ACDBD 2) ABDCD; ABCDD; ACBDD; 3) ABDCED; ABCDED; ABCEDD; ACBDED; ACBEDD; ACEBDD; ACEDBD 2. [26 Points] CPU Scheduling 1) [10 points] Given the following set of processes, with arrival time and length of the CPU-burst time given in milliseconds: Process Arrival Time Burst Time P1 0 2 P2 4 12 P3 6 6 P4 9 4 P5 13 5 For each of the following scheduling algorithms, draw the Gantt charts depicting the sequence of the process execution and calculate the average waiting time. a) FCFS b) SJF (non-preemptive) c) RR (with quantum of 8 milliseconds) d) SRTF Answer: FCFS: (COMP3511)[2021](s)midterm~=pcidkjhk^_28633.pdf downloaded by shhoaj from http://petergao.net/ustpastpaper/down.php course=COMP3511&id=23 at 2022-02-11 10:54:23. Academic use within HKUST only. Average waiting time: (0+0+10+13+13) / 5 = 7.2 milliseconds. SJF: Average waiting time: (0+0+19+7+7) /5 = 6.6 milliseconds. RR: Average waiting time: (0+10+6+9+13) / 5 = 7.6 milliseconds. SRTF: Average waiting time: (0+15+0+3+3) / 5 = 4.2 milliseconds. 2) [8 points] There is a 3-level feedback queue with Round-Robin scheduling used for the two high-priority queues and FCFS used for the lowest priority queue, which is shown in the figure below: Suppose there are six processes, P1, P2, P3, P4, P5 and P6. The arrival time and CPU burst-time of each process is listed below, which is given in milliseconds. Process Arrival Time Burst Time Quantum = 2 WQ Quantum = 4 WQ FCFS WQ (COMP3511)[2021](s)midterm~=pcidkjhk^_28633.pdf downloaded by shhoaj from http://petergao.net/ustpastpaper/down.php course=COMP3511&id=23 at 2022-02-11 10:54:23. Academic use within HKUST only. P1 0 10 P2 10 8 P3 8 30 P4 16 2 P5 22 8 P6 6 22 Draw a Gantt chart to depict the process scheduling sequence and calculate the average waiting time. Answer: Averging waiting time: P1: 36-10-0 = 26 P2: 78-10-8 = 60. P3: 76-8-30 = 38. P4: 0 P5: 80-22-8 = 50 P6: 52-6-22 = 24. Average waiting time: (26+60+38+0+50+24)/6 =33 3) [8 points] Real-time GPU Scheduling. Consider a soft real-time system with the following single-thread process, executing times, deadlines and periods. Assume all processes arrive at timeslot 0. Process Burst Time Deadline Period P1 1.0 3.0 3.0 P2 2.0 4.0 4.0 a) [6 points] Draw the corresponding Gantt charts depicting the scheduling procedures for these processes using Earliest Deadline First (EDF) scheduling and Rate-Monotonic (RM) algorithm within the first 14 timeslots (Hint, in soft real-time systems, the scheduling will continue even if the deadline is missed). Answer: EDF: RM: (COMP3511)[2021](s)midterm~=pcidkjhk^_28633.pdf downloaded by shhoaj from http://petergao.net/ustpastpaper/down.php course=COMP3511&id=23 at 2022-02-11 10:54:23. Academic use within HKUST only. b) [2 points] Based on your results above, comparing the EDF algorithm and the RM algorithm, which one is better and why Answer: EDF better. This is because, unlike the rate-monotonic algorithm with static priority, EDF leverages dynamic priorities according to the deadline, which can increase the fraction of met deadlines. 3. [11 points] Lock Implementation Assume compare_and_reset() is an atomic operation, provided by the hardware, with the following pseudocode. int compare_and_reset(int *a, int old, int new) { if (*a == old){ *a = new; return 1; } else { return 0; } } 1) [4 points] Please implement the code for a simple spinlock using compare-and- swap(). You are not allowed to use any other hardware or kernel supports (e.g., diabling interrupts). Please fill in the code for spinlock data strcture and corresponding acquire & release function. struct spinlock{ int value = 0; }; void acquire(struct spinlock *lock) { while (compare_and_reset(&lock->value, 0, 1) == 0) { /* spin here */ ; } } void release(struct spinlock* lock) { lock->value = 0; } (COMP3511)[2021](s)midterm~=pcidkjhk^_28633.pdf
downloaded by shhoaj from
http://petergao.net/ustpastpaper/down.php course=COMP3511&id=23 at
2022-02-11 10:54:23. Academic use within HKUST only. 2) [7 points] Now assume there are n processes in the system and each process Pi has the following pseudocode. The elements in the waiting[] array (indicating whether a process is waiting for the critical section or not) are initialized to false, and lock is initialized to 0. Will this algorithm be able to correctly solve the critical section problem If yes, please give a sketch proof. If not, please point out and correct the problem(s). (Hint: for security reason, lock should be released when no process is waiting to enter the critical section.) do { waiting[i] = true; key = 0; while (waiting[i] && !key) key = compare_and_reset(&lock, 0, 1); waiting[i] = false; /* critical section */ j = i + 1; while ( j < n && !waiting[j]) j = j + 1; if (j < n) waiting[j] = false; /* remainder section */ } while (true); 1. Some processes (with index smaller than i) may suffer from unbounded waiting. Only processes with index larger than i can be checked for entering their critical sections. 2. The lock will never be released even if no process is waiting. Correction: do { waiting[i] = true; key = 0; while (waiting[i] && !key) key = compare_and_reset(&lock); waiting[i] = false; /* critical section */ j = (i + 1) % n; while ((j != i) && !waiting[j]) j = (j + 1) % n; if (j == i) lock = false; /* no one is waiting, so release the lock */ (COMP3511)[2021](s)midterm~=pcidkjhk^_28633.pdf downloaded by shhoaj from http://petergao.net/ustpastpaper/down.php course=COMP3511&id=23 at 2022-02-11 10:54:23. Academic use within HKUST only. else waiting[j] = false; /* Unblock process j */ /* remainder section */ } while (true); (COMP3511)[2021](s)midterm~=pcidkjhk^_28633.pdf downloaded by shhoaj from http://petergao.net/ustpastpaper/down.php course=COMP3511&id=23 at 2022-02-11 10:54:23. Academic use within HKUST only.