课程名称︰作业系统
课程性质︰必修
课程教师︰薛智文
开课学院：电资学院
开课系所︰资工系
考试日期（年月日）︰2019/04/17
考试时限（分钟）：180
试题 :
This is an open-book and open-own-note exam. Please close copied notes and
do answer with your own words in the order of question number in EXACTLY one
given answer sheet. Make your own assumption if the question is not clear
enough. You can answer in Chinese and keep these papers. Have fun.
1. [10%] Describe two (new) OS features which can be improved by hardware,
software and theory efforts for better perfomance. Elaborate the efforts as
possible.
2. [10%] For some OS, there is an extra state, ZOMBIE, between RUNNING and
TERMINATED. Why? [5%] How can we have the same function without the ZOMBIE
state? [5%]
3. [10%] Roughly, how many processes and threads respectively after Ubuntu
boots?
4. [10%] Strassen algorithm can speed up a matrix multiplication with 7
smaller matrix multiplications. For many matrices stored in a file in a
single-processor computer, if we implement a matrix multiplication by
Strassen algorithm with 7 threads of smaller matrix multiplications,
discuss the speedup scenarios. Hint: it might be faster or slower.
5. [15%] Prove or disprove that preemptive shortest job first scheduling
always has shorter average waiting time than non-preemptive one.
6. [15%] Describe a mouse event as detail as you can from generated to shown
in a desktop of a virtualized OS environment such as Ubuntu in Virtual Box
on Windows 10. Hint: There should be a real mouse interrupt in Windows 10
and a virtualized one in Ubuntu.
7. [15%] For the following codes related in Linux kernel list structure,
describe how an entry of list of msg_sender can be accessed,
especially what the two 0's mean! [10%] Why a prefetch
statement previously included in list_for_each_entry macro was removed?
[5%]
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type, member) );})
#define list_for_each_entry(pos, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member); \
&pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))
struct list_head {struct list_head *next, *prev;};
struct msg_sender {
struct list_head list;
struct task_struct *tsk;
};
struct list_head *tmp;
struct msg_sender *mss;
mss = list_entry(tmp, struct msg_sender, list);
8. [25%] Consider a process synchornization problem, in which we have N people
competing for M chairs, and each chair can be used by one person at a time.
Let the competing go by rounds. That is, N people compete for M chairs in
the beginning of each round, and the M winners release their chairs at the
end of each round so that the next round starts. Please use semaphores to
write programs for the entry and exit sections of the M people so that
every person will win at least W times in competing the chairs for every R
consecutive rounds. Hint: M/N < W/R needs to be checked. A n-process
barrier, where waiting processes will be released until the n-th one has
arrived, and barrier_wait (barrier *b, int n) might be helpful.