Operating System 29 | Final Review for Special Topics and Quizzes

2. Synchronization

Example 2-1. Spinning and Blocking

In a multiprocessor system, a thread is trying to acquire a locked mutex.

a. What is the main difference between spinning and blocking.

b. Should the thread spin or block until the mutex is released?

c. Why might it be better to spin in some instances?

d. What if this were a uniprocessor system?

Solution:

a. When spinning, the current thread will continue occupy the lock, while for blocking, the current thread will be context switched to some other threads.

b. When the current thread requires resources that is occupied by another core, we should spin. When we currect thread requires resources that is occupied by the current core, we should block.

c. Because the owner of the lock may release it in a time smaller than the cost of context switching twice.

d. We can not use spinlocks for a uniprocessor system or the only CPU will be occupied with no exits.

Example 2-2. Spinlock Implementations Performance

For the following question, consider a multi-processor with write-invalidated cache coherence.

Determine whether the use of a dynamic (exponential backoff) delay has the same, better, or worse performance than a test-and-test-and-set (“spin on read”) lock. Then, explain why by making a performance comparison using each of the following metrics:

• Latency
• Delay
• Contention

Solution:

a. Better when we have less cores and lower loads. This is because the test-and-test-and-set lock is simple and the latency and delay is better. We don’t have to worry about contention when we have lower loads. However, because the delay time for dynamic delay lock is frequently unnecessary, the performance will be worse.

b. Worse when we have more cores and higher loads. This is because the test-and-test-and-set lock O(N²) high contention and dynamic delay lock is better.

c. Same when we have medium cores and medium loads. It is possible that at a specific load, those different approaches will result in the same performance.

3. Memory, Storage, and I/O Devices

Example 3-1. Page Table Size

Consider a 32-bit (x86) platform running Linux that uses a single-level page table. What are the maximum number of page table entries when the following page sizes are used?

a. regular (4 kB) pages?

b. large (2 MB) pages?

Solution:

a.

Page size = 4 kB      =>      log2(4*1024) = 12 bit page offsets
32 bit platform       =>      32 - 12 = 20 bits of tag
Therefore, we can have 2^20 tags
So the maximum number of page table entries is 2^20.

b. Similarly,

Page size = 2 MB      =>     log2(2*1024*1024) = 21 bit page offsets
32 bit platform       =>     32 - 21 = 11 bits of tag
Therefore, we can have 2^11 tags
So the maximum number of page table entries is 2^11.

Example 3-2. PIO and DMA

Answer the following questions about PIO:

a. Considering I/O devices, what does PIO stand for?

b. List the steps performed by the OS or process running on the CPU when sending a network packet using PIO.

c. Considering I/O devices, what does DMA stand for?

d. Explain why DMA can improve the performance of PIO?

Solution:

a. Programmed I/O: CPU directly write command and data to device registers

b. The steps are,

• write ‘command’ to the device to send a packet of appropriate size
• copy the header and data in a contiguous memory location
• copy data to NIC/device data transfer registers
• read status register to confirm that copied data was successfully transmitted
• repeat the last two steps as many times as needed to transmit the full packet, until the end-of-packet is reached.

c. Direct Memory Access: CPU directly write command to device registers but data is written from the memory based on the DMA controller.

d. DMA will be used to transfer data. So we perform 1 store instruction and 1 DMA configuration instead of many times CPU accesses based on the size of the transferred data.

Example 3–3. Inode

Assume an inode has the following structure:

Also, assume that each block pointer element is 4 bytes.

If a block on the disk is 4 kB, then what is the maximum file size that can be supported by this inode structure?

Solution:

Block size = 4 kB
Pointers in a block = 4 kB / 4 B = 1024 pointers

// For the single indirect pointer layers,
Size1 = Pointers in a block * Block size = 4 * 1024 kB

// For the double indirect pointer layers,
Size2 = (Pointers in a block)^2 * Block size = 4 * (1024)^2 kB

// For the triple indirect pointer layers,
Size3 = (Pointers in a block)^3 * Block size = 4 * (1024)^3 kB

// In total, approximately
Size = Size1 + Size2 + Size3 = 4 * (1024)^3 kB 
= 4 * (1024)^2 MB 
= 4 * 1024 GB
= 4 TB

4. RPC and DFS

(1) Consistency Models

• Strict: All writes are in strict order
• Sequential: All writes are in the same order
• Causal: Some writes are in the order implied by some reads
• Weak: No specific order or writes

Example 4-1. XDR Complier

An RPC routine get_coordinates() returns the N-dimensional coordinates of a data point, where each coordinate is an integer. Write the elements of the C data structure that corresponds to the 3D coordinates of a data point.

Solution:

Because N is not specified, we have to use the variable-length array data type in the XDR file, and it should be defined by,

int coordinate<M>;

where M is the maximum value of N (means N ≤ M).

When this is compiled in C, this will translate into a data structure that has two fields, an integer len that corresponds to the actual size of this array and a pointer val that is the address of where the data in this array is actually stored.

struct coordinate {
    int len;
    int *val;
};

Example 4-2. DFS Semantics

Consider the following timeline where ‘f’ is distributed shared file and P1 and P2 are processes:

Assume the original content of file f was 'a'. For each of the following DFS semantics, what will be read by P2 when t = 4s?

• UNIX semantics
• NFS semantics
• Sprite semantics

Solution:

Unix works by updating immediately to the server. the second something happens in P1 or P2, everyone knows about it. So for UNIX semantics, we will read 'ab'.

For NFS (session semantics + periodic update), it works is that it updates the server once the writer for P1 is closed and when we open a file, we will directly read from the memory. So we will read 'a'.

For Sprite semantics, we will open the file in the process that is currently writing. Therefore, it will read 'ab'.

Example 4-3. Causal Consistency

Consider the following sequence of operations by processors P1, P2, and P3 which occurred in a distributed shared memory system:

Answer the following questions:

a. Name all processors (P1, P2, or P3) that observe causally consistent reads.

b. Is this execution causally consistent?

Solution:

a. P1 and P2. W_m1(3)@P1 and W_m1(2)@ P2 are causally related (via R_m1(2) @P1), so these two writes cannot be seen in reverse order, as currently seen by P3. P3 doesn’t observe causally consistent reads.

b. No. P3 doesn’t follow causal consistency. We can not read 2 from m1 after we read 3 from it because of the causal consistency between P1 and p2.

Example 4-4. Distributed Applications

You are designing the new image datastore for an application that stores users’ images (like Picasa). The new design must consider the following scale:

• The current application has 30 million users
• Each user has on average 2,000 photos
• Each photo is on average 500 kB
• Requests are evenly distributed across all images

Answer the following:

a. Would you use replication or partitioning as a mechanism to ensure high responsiveness of the image store?

b. If you have 10 server machines at your disposal, and one of them crashes, what’s the percentage of requests that the image store will not be able to respond to, if any?

Solution:

a. Partitioning. The current data set is ~30 PB, so cannot store it on one machine

b. 10% since requests are evenly distributed on 10 server machines.

Example 4-5. Weak Consistency

Let’s suppose we have the following sequence of operations by processors P1, P2, and P3,

Then answer the following questions,

a. Consider the following sequence of operations. Is this execution weakly consistent? (Yes/No) ______________

b. If you ignore the sync operations, is this execution causal consistency? (Yes/No) ______________

Solution:

a. Yes. This is weakly consistent.

b. No. There will not be any causal consistency because only one process has the operation order.

Example 4-6. Consistency Models

Choose the correct consistency model that defines the following conditions:

I. All Writes are propagated to other processes, and all Writes done elsewhere are brought locally, at a sync instruction.

II. Accesses to sync variables are sequentially consistent

III. Access to sync variable is not permitted unless all Writes elsewhere have completed

IV. No data access is allowed until all previous synchronization variable accesses have been performed

• A. Weak consistency
• B. Causal consistency
• C. Sequential consistency
• D. Strict consistency

Solution: A. Weak consistency

Example 4-7. DFS Caching

Caching is an important optimization technique. Describe the three potential locations for caching in a distributed file system. Briefly discuss the advantages and disadvantages of each location.

Solution:

• Client memory/client buffer cache: for the regular file system, fast but small
• Client storage device (HDD/SSD): slow but large
• Buffer cache in memory on server: the hit rate depends on how many clients are accessing the server and how many of them are interleaved

Example 4-8. Stated Server Vs. Stateless Server

Answer the following questions:

a. What are the advantages of a stateless distributed file server?

b. What are the advantages of a stated distributed file server?

c. What are the disadvantages of a stateless distributed file server?

d. What are the disadvantages of a stated distributed file server?

Solution:

a.
• Stateless server is more robust than stateful file server, hence they provide fault tolerance. 
• Lost connections can't leave a file in an invalid state. 
• Rebooting the server does not lose state information. 
• Rebooting the client does not confuse a stateless server.

b. 
• It is simple. 
• Fewer disk accesses are needed at server side. 
• Server knows if the file was opened for sequential access, and hence can read ahead the next blocks. 
• It reduces the network traffic as client need not send state information with every call to server.

c. 
• As the server doesn't maintain any state information about file processing activity, it cannot detect and discard duplicate requests from client. 
• To ensure consistency of files, the requests made by clients must be idempotent. 
• The stateless file server incurs performance penalty due to: 
    • The file server opens the file at every file operation. 
    • When client performs write operation, the changes are needed to be reflected in disk copy of the file. 
    • Stateless file server cannot employ file caching or disk caching.

d.
• When the client crashes, the file processing activity should be abandoned, and the file state should have to be restored to its previous consistent state, so that the client can restart its file processing activity. 
• The resources allocated to aborted file processing should have to be released. 
• When the server crashes, the state information stored in file server metadata is lost, hence the file processing activity should be terminated. Thus client knows about server crashes.

Example 4–9. RPC Details

Answer the following questions:

a. If the caller machine (client) in an RPC crashes while waiting for a reply, we say that the computation which was initiated on the callee machine is an “orphan”. Properly terminating orphan computations is called the orphan elimination problem. What sort of issues makes orphan elimination difficult in RPC systems?

b. Under what circumstances might an RPC-based program be less efficient than a carefully optimized message-based program?

Solution:

a. When we have an orphan, the RPC runtime will not be able to provide some better understandings of what’s going on. And they will provide a new type of error notification that tries to capture what goes wrong with an RPC request without claiming to provide the exact detail. Thus, we have to manually look into the log files or binary files to find out what goes wrong. This process of locating error details will be costly and this will also make orphan elimination difficult.

b. Message-based program allows sending all data in a single payload and able to finish in one call. So there is no need to wait. In this situation, it is better.

5. Virtualization

Example 5-1. Virtualization Examples

Fill in the following blanks with which virtualization model they are by bare-metal virtualization (B, aka. Type I hypervisor) or hosted virtualization (H, aka. Type II hypervisor).

• Microsoft Hyper-V ____________
• Citrix Xen ______________
• VMware ESX ____________
• Kernel-based VM (KVM) _____________
• Oracle VM for x86 ____________
• VMware Fusion ____________
• Oracle Virtual Box ______________

Solution:

• B
• B
• B
• H
• H
• H
• H

Example 5–2. VMware’s x86 VMM

Which of the following statements about VMware’s x86 virtual machine monitor are true or false? Explain.

• The x86 architecture originally contained instructions that were non-virtualizable using trap-and-emulate virtualization.
• Shadow page tables store the mappings from guest physical to host physical memory addresses.
• VMware’s VMM prevents the guest from accessing the memory used for the VMM’s internal state by unmapping the corresponding entries in the guest’s page table.
• VMware’s binary translation-based VMM translates guest kernel-mode instructions but not guest user-mode instructions.
• A monitor using hardware-assisted virtualization (Intel’s VT-x or AMD-V) is always faster than one using binary translation.

Solution:

• True. For example, the popf instruction in x86 was originally non-virtualizable using trap-and-emulate.
• False. Shadow page tables store the mappings from guest virtual memory to host physical memory addresses.
• False. Permission bits in page tables do not allow for execute-only mappings, which are needed for the Translation Cache. The VMM’s own data must be accessible to translated code but not the original guest instructions, even though both run at the same privilege level. Thus, memory segmentation is used to prevent the guest from accessing the VMM’s internal state.
• True. Why we use binary translation-based VMM is because we want to trap to the kernel, and only the kernel instructions need to conduct operations like that.
• False. Binary translation can also have some optimizations that will result in better performance.

6. IPC

Example 6-1. Shared-Memory IPC

Answer the following questions,

a. What’s the difference between a shared memory id (shmid) and a shared memory key?

b. How does the kernel actually implement shared memory segments?

Solution:

a.

If provided that certain limits of the segments are met, then it assigns to it a shmid. This key is used to uniquely identify the segment within the OS, and any other process can refer to this particular segment using this shared memory id.

key refers to the value which is given in reference to IPC resources like shared memory, message queues, and semaphores.

b.

The kernel supports segments of the shared memory that don’t need to be contiguous physical pages. These segments are system-wide and there is a limit for the total number of these segments. In today’s Linux system, this is not an issue because we can use up to 4,000 segments. However, in the past, we can only use 6 segments. When a process requests that a shared memory segment is created, the OS allocates the required amount of physical memory.