Operating Systems - Fall 2008, Exercise 6

Operating Systems, Fall 2008, Exercise 6

These homework exercises will be covered in practice sessions on week 41 (Thu 9.10. or Fri 10.10). Each week one of the questions must be submitted on paper to the teacher.

Exam is on Wednesday 15th of October at 16.00 in room A111.

RETURN ON PAPER:

Write (In Finnish or in English) a bit longer (approximately 1-2 page) answer to the question:

Compare ext3fs and NTFS file systems. What are the similarities and biggest differences between Linux ext3fs and Microsoft NTFS file systems. Think about at least disk partitioning, file metadata (such as attributes) and its management, file and disk block allocation, directory structure and its usage, disk system consistency, different size restrictions.

For this question you can find a lot of information from the current course book. Inf you use information from other sources, please state very clearly the sources you have used to collect information from: article names, wikipedia page names, http-address of internet pages, etc.

Solve in advance for the class meeting:

Tan08 Problem 8.3: If a CPU issues one memory request every instruction and the computer runs at 200 MIPS, about how many CPUs will it take to saturate a 400-MHz bus? Assume that a memory reference requires one bus cycle. Now repeat this problem for a system in which caching is used and the caches have a 90% hit rate. Finally, what cache hit rate would be needed to allow 32 CPUs to share the bus without overloading it?
Sta05 Question 14.3: The following FORTRAN program is to be executed on a computer, and a parallel verison si to be executed on a 32-computer cluster.
```
  L1:        DO 10 I= 1,2024
  L2:           SUM(I)=0
  L3:           DO 20 J = 1,I
  L4:  20          SUM(I) = SUM(I) + I
  L5:  10    CONTINUE 
```
Suppose lines 2 and 4 each take two machine cycle times, including all processor and memory-access activities. Ignore the overhead caused by the software loop control statements (lines 1,3,5) and all other system overhead and resource conflicts.
1. What is the total execution time (in machine cycle times) of the program on the single computer?
2. Divide the I-loop iterations among the 32 computers as follows: Computer 1 executes the first 32 iterations (I = 1 to 32), processor 2 executes the next 32 instructions, and so on. What are the execution time and speedup factor compared with part (a)? (Note that the computational workload, dictated by the J-loop, is unbalanced among the computers.)
3. Explain how to modify the pallelizing to facilitate a balanced parallel execution of all the computational workload over 32 computers. By a balanced load is meant an equal number of additions assigned to each computer with respect to both loops.
4. What is the minimum execution time resulting from the parallel execution on 32 computers? What is the resulting speedup over a single computer?
Virtual machines
1. Tan08 8.26: Consider a type 1 hypervisor that can support up to n virtual machines at the same time. PCs can have a maximum of four disk primary partitions. Can n be larger than 4? If so, where can the data be stored?
2. Tan08 8.28: VMware does binary translation one basic block at a time, then it executes the block and starts translating the next one. Could it translate the entire program in advance and then execute it? If so, what are the advantages and disadvantages of each technique?
LINUX
1. Tan08 10.8: As multi-megabyte programs became more common, the time spent executing the fork system call and copying the data and stack segments of the calling process grew proportionally. When fork is executed in Linux, the parent's address space is not copied, as traditional fork semantics would dictate. How does Linux prevent the child from doing something that would completely change the fork semantics?
2. Tan08 10.9: Does it make sense to take away process' memory when it enters zombie state? Why or why not?
3. Tan08 10.15: What combination of the sharing_flags bits used by the Linux clone command corresponds to a conventional UNIX fork call? To creating a conventional UNIX thread?
Tan 10.17: When booting Linux or Windows (or most other operating system for that matter), the bootstrap loader in sector 0 of the disk first loads a boot program which then loads the operating system. Why is this extra step necessary? Surely, it would be simpler to have the bootstrap loader in sector 0 just load the operating system directly.
Windows
1. Tan 11.6: Windows uses 4-MB pages because it improves the effectiveness of the TLB, which can have profound impact on performance. Why is this?
2. Tan 11.14: Even when there is plenty of free memeory available, and the memory manager does not need to trim working sets, the paging system can still frequently be writing to disk. Why?
3. Tan 11.8: The Win32 API call WaitForMultipleObjects allows a thread to block on a set of synchronization objects whose handles are passed as parameters. As soon as any one of them is signaled, the calling thread is released. Is it possible to have the set of synchronization objects include two semaphores, one mutex, and one critical section? Why or why not? Hint: This is not a trick question, but it does require some careful thought.

Tiina.Niklander@cs.helsinki.fi

Department of Computer Science

Department information