課程名稱︰作業系統
課程性質︰必帶
課程教師︰薛智文
開課學院：電資學院
開課系所︰資訊系
考試日期（年月日）︰103/4/16
考試時限（分鐘）：9:10 ~ 12:10
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
This is an open-book and open-own-note exam. Please do answer with your
own words in the order of question number in EXACTLY one given answer sheet.
You can answer in Chinese and keep these papers. Good luck.
1. [10%] Suppose that an engineer is designing an operating system for data
collectors in a wireless sensor network, and another operating system for
a cloud server used in the network storing the data collected and
providing various data retrieval services. Describe the most important
3 features in the order of importance and reasons for both operating
systems.
2. [10%] 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 teo 0's mean!
#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);
3. [10%] Virtualization enables multiple OSes running simultaneously on
a physical machine. What is "para-virtualization"? [5%] In what situation,
we still need only one OS running on a virtualized environment? [5%]
4. [10%] Both rate-monotonic and earliest-deadline-first are optimal periodic
real-time scheduling algorithms. Describe the difference [6%] and what the
"optimal" means. [4%]
5. [15%] What are the advantages of using thread pool instead of creating
seperate threads for servicing respective requests? [5%] What happens when
the number of requests varies a lot from time to time using thread pool?
[5%] What can other implicit threading help? [5%]
6. [10%] Prove shortest job first scheduling is optimal on average waiting
time both in preemptive and non-preemptive version.
7. [10%] Why Linux 2.6 uses red-black tree to implement Completely Fair
Schedular even it is not O(1)? [5%] Why cache the leftmost node can help?
Please give an example.
8. [5%] Try to use the system call 'fork()' to write a program that generate
a child process and print "Child!" after the parent process printing
"Parent!".
9. [5%] When multiple threads run in parallel on a multicore system, would
the more threads for the same task always finish earlier when the number
of threads is less than the number of cores? Why?
10. [10%] Describe the problem for the following implementation of a critical
section.
do{
┌────────────────┐
│ turn = j; │
│ flag[i] = TRUE; │
│ while(flag[j] && turn == j); │
└────────────────┘
critical section
┌────────────────┐
│ flag[i] = false; │
└────────────────┘
remainder section
} while(1);
11. [15%] The following codes with semaphores can be used to implement a
monitor for synchronization, where F is an external procedure, x is a
condition variable. Explain the purposes of using variable next-count and
semaphores next [5%] and how and why the monitor can help for
synchronization?
semaphore mutex; // (initially = 1) ┌───────────┐
semaphore next; // (initially = 0) │x-count++; │
int next-count = 0; │if (next-count > 0) │
semaphore x-sem; // (initially = 0) │ signal(next); │
int x-count = 0; │else │
x.wait() │ signal(mutex); │
┌────────────┐ │wait(x-sem); │
│wait(mutex); │ │x-count