課程名稱︰作業系統
課程性質︰必修
課程教師︰薛智文
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰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.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.103
※ 文章網址: https://www.ptt.cc/bbs/NTU-Exam/M.1556075676.A.E4A.html
※ 編輯: ciltsinn (140.112.25.103), 04/24/2019 11:20:08
推
04/24 12:59,
5年前
, 1F
04/24 12:59, 1F