[理工] [os]一堆問題

[jim055006 (好崩潰)]

第一題
Which of the following statements about processes are incorrect?
(A) The many - to - one multithreading model is suitable when
    the number of kernel threads per process is limited.
(B) SJF scheduling is used frequently in long-term CPU scheduling.
(C) FCFS is the RR algorithm with an infinite time quantum.
(D) A counting semaphore can be implemented using 2 binary semaphores.
(E) Semaphores can avoid busy waiting altogether.

答案是A
可是E不也是錯的嗎?  busy waiting無法完全避免吧!!

-------------------------------------------------------------------------------
第二題
The following shows the structures of a reader and writer process
in the readers-writers problem The semaphores mutex and wrt are
initialized to 1; readcount is initialized to 0.


Writer Process         ｜  Reader Process
----------------------------------------------------------------
wait (wrt);            ｜  wait(mutex);
…                     ｜  readcount++;
Writing is performed   ｜  if (readcount == 1 ) wait (wrt);
…                     ｜  signal (mutex);
signal (wrt)           ｜  …
                       ｜  reading is preformed
                       ｜  …
                       ｜  wait(mutex);
                       ｜  readcount--;
                       ｜  if (readcount == 0 ) signal (wrt);
                       ｜  signal(mutex);
                       ｜
                       ｜
                       ｜
                       ｜
                       ｜


Which of the following statements is incorrect?
(A) No reader will be kept waiting unless a writer has already
    obtained permission to use the shared object.
(B) The above program structure allows concurrent readers.
(C) When a writer executes signal(wrt), the scheduler will resume
    the execution of waiting readers first, and then resume the
    execution of waiting writers.
(D) When a writer is performing writing, 10 readers arrive and try
    to read .Then the first reader will be blocked by wait(wrt) and
    the other 9 readers will be blocked by wait (mutex).
(E) The above program structure is not starvation-free.

答案是C
為什麼呢??
write執行完不是就會讓reader進去嗎??
還是說會讓reader一直進去只有在第一個reader進入的時候??

-------------------------------------------------------------------------------
第三題
Consider the organization of a UNIX file as represented by the Inode.
Assume that there are 10 direct block pointers, and a singly, doubly,
and triply indirect pointer in each Inode. Furthr, assume that the
system block size and the disk sector size are both 1K. If the disk
block pointer is 4 bytes, then what is the maximum file size suppored
by this system? (Choose the closest number)

(A)12G (B)16G (C)20G (E)24G (D)36G

答案給B

請問這題是要怎麼計算呢??

-------------------------------------------------------------------------------
第四題
X could lead a process to leave from the "running" state to the "ready" state
and Y could lead lead a process to leave from the "running" state to the
"waiting" state. What is (X,Y)?

(A)(hardware interrupt, software interrupt)
(B)(hardware interrupt, clock interrupt)
(C)(software interrupt, clock interrupt)
(D)(clock interrupt, hardware interrupt)
(E) (clock interrupt, software interrupt)

答案是給E
可是A不也對嗎??

-------------------------------------------------------------------------------
第五題
Consider a disk drive whose transfer speed to the memory over the bus
is 100 Mbps and the speed to read blocks right under its disk head depends
on how fast its disk rotates. Suppose that the rotation speed is 600 rpm,
there are 1200 blocks, of 4K bytes each, in each track, and the disk drive
cannot transfer and read at the same time. What interleaving factor should
be designed, so that the disk head can read blocks of contiguous order
without skipping a desired block at the first chance ?
(Note that an interleaving factor of n means the disk controller reads one
block and then skips n blocks under the disk head.)

(A)2 (B)3 (C)4 (D)5 (E)6

答案是給 C
我求出了賺一圈要花10^(-1)秒
        一秒可讀取48M的資料

但是還是不知道題目要求的比例是啥??
去除以100M也得不到4= =

請問這題到底要算啥??

-------------------------------------------------------------------------------
第六題

在paging system下
再算page table size時
page entry 是只要算frame bit就好
           還是要加上page bit跟一些有的沒的bit?????
                                   ^^^^^^^^^^^^^
                                 像是vaild,dirty等等

-------------------------------------------------------------------------------
第七題
Consider a 32-bit operating system that runs on a machine with 64 MB of physical
memory. The operating system divides the 32-bit logical address space into
pages. Each page is sized of 4KB. There are 4 methods for translating a virtual
address to a physical address：
a.one-level page table, b.two-level page table, c.hashed paged table,
and d.inverted page table.

Please calculate the memory space required for a process’s page table in each
method under the following assumptions：

A.each entry in the page table is sized of 4 bytes,
B.in the two-level page table, the outer(first-level) page table has 256 entries
C.in the hashed paged table, the range of the value returned by the hash
  function is between 0 and 127.

我所求出來的

logical address 32bit
physical address 26bit

d=12bit  p=20bit


for one-level page table: 2^20*4

for two-level page table: (2^8+2^12)*4

    first level=8bit
    second level=12bit

for hashing page table: 128*4

    有128個bucket

for inverted page table: 2^26*4

    有2^26個frame

因為我的答案跟解答有些出入非常大
所以想請問大家我這樣寫是對是錯...

-------------------------------------------------------------------------------
第八題
An IDE hard disk spins at 7200 RPM, has 2 megebytes internal cache, 5000
cyclinders, 20 tracks per cylinder, 120 sectors per track, 512 bytes per sector,
and connects to a computer via Ultra ATA/133 interface at a speed of 133
megebytes per second.

a.Calculate the disk size.
b.Estimate the sustained transfer rate of this drive in megabytes per second.
c.Suppose that the average seek time for the drive is 4 ms. Estimate the I/Os
  per second and effective transfer rate for a random-access workload that reads
  individual sectors scattered across the disk.
d.Calculate the random-access I/Os per second and transfer rate for I/O sizes of
  4KB, 8KB, and 16KB.
e.If the hard disk connects to a computer via USB 1.0, 1.1 and 2.0 at speed of
  1.5, 12 and 480 Megabits per second respectively, please estimate the
  sustained transfer rate of this drive via a different USB interfaces from a
  device driver point of view.

想問bcde要如何算XDD
因為不太了解他後面的一些敘述

-------------------------------------------------------------------------------
第九題

true or false

Memory pages that are shared between two or more processes
can never be swapped out to the disk.

答案是F
為什麼呢???

-------------------------------------------------------------------------------
第十題
A computer has the following parameters. The CPU has a clock rate of 1 GHz.
The cache has a block size of W bytes and an average access time of X ns/byte.
The virtual memory has a page size of Y KB, and the average disk transfer rate
is Z KB/ms.

(a)Give each of the four parameters a reasonable and representative numerical
   value, and then use the values to estimate the time to serve a page fault and
   that to serve a cache miss.
(Please note the units of the parameters and make additional assumptions if
necessary.)

(b)Use the above estimations to explain why page faults will result in context
   switches while cache misses usually only stall the CPU.

這題到底是要算甚麼東西呢??

-------------------------------------------------------------------------------
第十一題
In operating systems, the scheduler performs a rescheduling when current process
requests an I/O, the time slice assigned to current process is exhausted, the
current process yields, or higher-priority processes arrive. On every
rescheduling, it will take time for the kernel to perform context switch. Is it
possible for a round-robin scheduler with a 100-millisecond time slices to spend
over half its time in the OS context switch code? Assume that it take the OS 1
millisecond to context switch the CPU. Please justify your answer and give an
example.

這題我是完全不太懂到底是在講甚麼
也不知道是要求甚麼...

-------------------------------------------------------------------------------
第十二題
Please define what a re-entrant function is. The following function,
strToLower(), accepts one character pointer and translates all characters in the
string into lower characters. The implementation in NOT a re-entrant function.
Please correct the code so it becomes a re-entrant function.

Char *strToLower(char *str)
{
  static char buffer[STRING_SIZE_LIMIT];
  int index;
  for(index=0;str[index];index++)
     buffer[index] = tolower(str[index]);
  buffer[index] =  "\0";
  return buffer;
}

答案是

 Char *strToLower(char *str)
{
  char buffer[STRING_SIZE_LIMIT];
  int index;
  for(index=0;str[index];index++)
     buffer[index] = tolower(str[index]);
  buffer[index] =  "\0";
  return buffer;
}

就只是把static刪掉就變成reentrant code??
為什麼呢??
那個static的作用是啥??

-------------------------------------------------------------------------------
第十三題
Determining the optimal page size of a memory requires balancing some competing
factors. The memory overhead of paging consists of the page table (increased as
page size gets smaller) and the internal fragmentation waste (increased as page
size gets larger). Suppose that the average process size is 2M bytes, page entry
size is 4 byres, the average wasted memory in the last page of each process due
to internal fragmentation is a half page.

a.What is the optimal page size, in bytes?
b.What is the minimum overhead, in bytes, for an average process?

這題要怎麼求overhead??

-------------------------------------------------------------------------------
第十四題
A system enables the MMU(memory management unit) and supports logical addressing
and virtual memory management. Which of the following statement is NOT correct?

(A)To add more physical memory may increase the logical address space of a
   program.
(B)To add more physical memory may increase the number of entries in page tables
   if the inverted page table scheme is employed.
(C)A system with more swapping spaces in the backing store can execute more
   programs on the system simultaneously.
(D)A system with more swapping spaces can grant more memory requests generated
   by programs.

答案是B
可是inverted page table裡面不是以physical momery為記錄對象嗎??
所以有多少frame就有多少entry??
這樣B應該是對的啊?

-------------------------------------------------------------------------------
第十五題
page replacement中使用dirty bit來表示page有被修改過...
那所謂的修改過是指怎樣修改??

-------------------------------------------------------------------------------
第十六題
Consider the following hardware configurations.
Virtual address = 32 bits, page size =4K bytes, and a page table entry occupies
4 bytes. How many pages should the OS allocate for the page tables of a 12M-byte
process under the following paging mechanisms?

b.two-level paging (assuming that the number of entries in a first-level page
  table is the same as that in a second-level page table)

這題要如何計算呢??

-------------------------------------------------------------------------------
第十七題
Suppose that you have a UNIX file system where the disk block size is 1kB, and
an inode takes 128 bytes. Disk addresses take 32 bits, and the inode contains
space for 64 bytes of data (a recent optimization), 8 direct addresses, one
indirect, one double-indirect and one triple-indirect (the rest of the space in
the mode is taken up with other information such as ownership and protection).
An index block is the same size as a disk block. How much space (including
overhead) do the following files that have data require?


a. one (1) byte long,
b. 1025 bytes long,
c. 65536 (64KB) bytes long, and
d. 1048576 (1MB) bytes long

這題跟第三題很像只是他下面多了一些條件,所以我一樣也不懂XDDDD

-------------------------------------------------------------------------------

以上
真的是又臭又長
不好意思這是因為做了考古積出來的問題
希望有熱心的高手可以耐心看完幫我解答
先謝謝各位囉!!


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 223.138.179.44
推 da0910cc:先推再想  ㄎ
推 madd1412:2.W寫完,不一定會先給R,因為搞不好另一個Writer更早到!
→ madd1412:3. (10 + 2^8 + 2^16 + 2^24)*1K =16GB(大約)
→ jim055006:感謝樓上
→ jim055006:還有1F
→ jim055006:怎麼都沒人鳥我= ="
推 gskman:因為太多了 攬的看XD
推 kiwidoit:按右鍵就按到手軟了:)
→ jim055006:XD~~~
→ jim055006:OK....我一個一個慢慢PO
→ sneak: OK....我一個一個 https://daxiv.com