微信客服：xiaoxionga100
微信客服：ITCS521
程序代写案例-COMP 3511
时间：2022-02-11
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(“A\n”);
if ( fork() == 0 ) {
printf(“B\n”);
}
else {
printf(“C\n”);
_____A_____
}
printf(“D\n”);
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(“E\n”); 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.
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(“A\n”);
if ( fork() == 0 ) {
printf(“B\n”);
}
else {
printf(“C\n”);
_____A_____
}
printf(“D\n”);
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(“E\n”); 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.
