Flashcards
Advanced Operation Systems - Test 3
Cards in this deck (11)
- 1Giant-scale services You are designing a datacenter in which you want each server to be equipped with an adequate of amount of storage to meet the following design goals. 1) The corpus of data you have to process is 1000 GBytes. You want to be able to process each individual query(which is embarrassingly parallel) by parallelizing it 20 ways ensuring full harvest.What strategy will you use for storing the corpus of data in the servers? 2) In addition to the above two goals, You also want to make sure you can process 20 queries in parallel ensuring full harvest for all the queries.What strategy will you use for meeting this additional design goal?1) To achieve 20-way parallelization for processing an individual query, we’d partition the full corpus of data into 20 partitions (each one is 50 GB). This will allow each of the 20 partitions to run in parallel in servicing an individual request.
2) In order to ensure the ability to process 20 queries in parallel, we’d take the 20 partitions and replicate them 20 times. So there are 20 sets of servers where each set has 20 partitions of the full corpus of data. In total, there are 400 servers. - 2Giant-scale services A datacenter has 100 servers. Each server has a 10 GByte storage. The corpus of data to be processed is 100 GBytes. You have designed the data center such that you can handle 10 simultaneous embarrassingly parallel queries employing 10 servers for each query yielding full harvest. Due to a power outage 10 servers go down. All the queries that come to the data center need full harvest. 1) What is the best case yield possible? 2) What is the worst case yield possible?1) Best case yield is 90% with the 10 servers that went down each being a unique partition.
2) Worst case yield 0% if all 10 servers are the same partition. - 3Map-reduce A map-reduce application consists of: -50 shards of data to be processed -5 distinct outputs to be produced -CPU time to execute a map function: Tm -CPU time to execute a reduce function: Tr -I/O time to write an intermediate result by a mapper: Ti -Synchronous RPC time to fetch an intermediate result by a reducer: Trpc -I/O time to write out the final result by the reducer: Tf 1) The map-reduce infrastructure uses 10 threads for the map function and 5 threads for the reduce function. Ignoring scheduling overheads by the infrastructure, compute the total execution time for the above application. (Show your work for partial credit)-10 threads for mapping require Tm+Ti to finish
-50 shards of data, total time for mapping: 5*(Tm+Ti)
-Each reducer has to perform 50 blocking synchronous RPC operations to get intermediate results: 50*Trpc
-5 threads for reducing in parallel to produce the final result, each taking: 50*Trpc+Tr+Tf
-Total time = 50*Trpc+Tr+Tf + 5*(Tm+Ti) - 4CDN –Coral 1) The problem that Coral’s key-based routing is trying to solve? 2) How does Coral solve it?1) Metadata server overload - avoid the greedy approach taken by DHT which leads to metadata server overload and tree saturation.Origin Server
Overload - as content gets popular, the source server actually storing the content may become overloaded with download requests from users.
2) Metadata server overload - Coral takes a non-greedy approach to democratize content generation, storage, and distribution. This non-greedy approach increases latency, but relieves stress on origin and metaservers, enabling content to be continually served, even when it experiences high demand.
Origin server overload - users that retrieve content can volunteer themselves as a proxy for the content. After they download the content, they can perform a put operation to add themselves to the DHT. - 5CDN –Coral In the Coral system, assume a buddies’ overlay network that includes node-ids: 30, 75, 100, 150, 200 In the following, -Put(x, y) denotes putting the key-value pair (key = x and value = y) -Get (x) denotes getting the value corresponding to the key = x - Assume a coral system in which the “l” value for a node is set to 2; “β” is - All Puts/Gets in this problem using key-based routing go through node- ids: 30, 75, 100, 150, 200 - Currently: * node-id 150 has 1 entry for the key 200 with a value 8 * node-id 200 has 2 entries for the key 200 with values 10 and 11 1) Node-id 1 does: Put(200, 1). Where will its key-value pair be placed? Why? 2) Subsequently, Node-id 2 does: Put(200, 2). Where will its key-value pair be placed? Why? 3) Subsequently, Node-id 5 does: Get(200). What value will it get? Why?1) Node 150, because it is the “furthest” non-overloaded Node in the traversal path
2) Node 100, because the last “put” for 200 made Node 150 full/overloaded.
3) It gets 2, because it will retrieve the value from Node 100, which is the “closest” Node that has this key in its traversal path. - 6TS-Linux (Real-time and Multimedia) One-shot timer is accurate in delivering a timer interrupt, but it has the overhead of the OS having to field these interrupts and having to re-program the APIC timer after each interrupt event. Firm timer uses one-shot timer in its implementation. 1) What makes one-shot timer provide nano-second accuracy for timer events? 2) What makes TS-Linux avoid the overhead of fielding frequent one-shot timer events? 3) Guestimate the overhead of reprogramming the one-shot timer after each interrupt.1) Using APIC hardware, we can re-program one-shot timers in only a few cycles to have ~10ns of accuracy.
2) TSL uses over-shoot parameter to avoid the overhead of interrupts with one-shot timer.
3) Interrupt handler will go through a timer data structure that contains tasks sorted by expiration time. In the data structure there is a callback handler for dealing with each task that will be called by the interrupt handler. Expired timers will be removed from the data structure and the interrupt handler will reprogram the one shot timer for a task in the data structure to handle another event. - 7PTS (Real-time and Multimedia) 1) (Answer True/False with justification) An intermediate node N1 in the channel-thread graph of PTS, performs Get on two of its input channels and receives items with the same times-stamp. Given that the items in these channels are produced by different nodes in the distributed system, how can N1 assume that these items are temporally correlated? 2) (Answer True/False with justification) Nodes N2 and N3 are producers of items into a channel Ch1. Both threads simultaneously attempt to perform Put(Ch1, , ts=100). a) “Only one of the Puts will succeed since they have the same timestamp.” b) “Both will succeed, but the channel will contain exactly one item for ts=100 put in by whichever node was last to succeed.” c) “The results are indeterminate since the nodes should have gotten a mutual exclusion lock on the channel before attempting to execute the Put operation.”1) We can assume that the nodes have synchronized time thus similar timestamps must mean the events are temporally related. All events have timestamps and get / put operations must have timestamps / time ranges.
2a) False, both will succeed. There is a single writer which ensures a append only and concurrent writes will be written in the order they were received.
2b) False, there will be two items for ts=100 written in the order they were received.
2c) False, due to the generic persistence and single writer, memory sync is not required. - 8LRVM (Failures and Recovery) Consider a multithreaded process using the LRVM library. Two threads in this process concurrently modify different persistent data structures (m1, m2, respectively) in the same memory region R1 as shown: Assume T1 aborts the transaction in the middle of its execution while T2 is still in the middle of its transaction. 1) (Answer True/False with justification) - “LRVM will abort T2’s transaction.” 2) (Answer True/False with justification) - “LRVM will ignore T1’s abort since T2 is modifying persistent data in the same region.” 3) (Answer True/False with justification) - “The above execution will result in creating one abort record and redo record on the disk.”1) False. The boundary of a transaction is between the begin and end transaction APIs. Both threads get their own Transaction ID when they issue begin_transaction and handled independently.
2) False. T1's abort will be handled. The abort will be for the data structure m1 alone. T2 is modifying a different part of the persistent data structure m2 .
3) False. Abort record is only in the memory and not in disk. Redo record will be on the disk if Thread T2 commits the transaction. - 9RiosVista (Failures and Recovery) 1) Why are there no redo logs? 2) When are undo logs written to the disk? 3) What happens when the RVM call “Set Range” is executed with RioVista? 4) What happens upon transaction commit? 5) What happens on transaction abort?1) All the modifications done to the data segments directly memory mapped into the virtual memory via the persistent Rio file cache. This way, redo logs are not required in RioVista.
2)
- undo logs are created at the beginning of the transaction; it lives in the Rio file cache
- the undo log is removed once the transaction commits or aborts (after restoring the old values from the undo log into the memory mapped data segment)
- undo log may NEVER be written to the disk unless the Rio file cache has to do a replacement due to space limitation WITHIN the duration of the transaction
3) This call notifies Rio the part of the data segment (memory mapped to virtual memory) that is going to be modified. When the set range call is invoked, the range of memory to be modified will be persisted to the file cache which is the undo log.
4) Upon transaction commit, the undo log is deleted (all or nothing).
5) On transaction abort, the contents of the undo log are applied to the memory mapped space of the data segment. As the memory space is automatically persisted, the data se
- 10Quicksilver (Failures and Recovery) A distributed service in Quicksilver is opting to use the recovery management provided by the operating system. Any client of this service will touch server nodes S1, S2, and S3, in that order to execute the service. The service will result in the creation of intermediate files f1, f2, and f3 on these nodes, respectively. All these intermediate files will be ultimately removed by the service once a client terminates normally. The service designates S1 as the coordinator for recovery management. The service uses 2-phase commit for its recovery operation.When the service is just about to complete, the client node crashes. 1) What is the structure of the transaction tree for recovery management? 2) What will the transaction logs contain in the three server nodes? 3) What actions will ensue due to the client crash? 4) What will be the end result?1)
S1 (coordinator)
|
-----------------
| | |
S2 Client S3
2) Each node has its own checkpoint records where it persists state created on behalf of the client or the server for recoverability.
3)
- Communication Manager (CM) of S1 detects connection failure with client.
-S1, as the coordinator, will clean up its intermediate file f1 (the first phase of the abort) and propagate the abort to its subordinates S2 and S3 (the second phase of the abort)
-S2 and S3 will get the abort message and clean up their intermediate files f2 and f3.
4) The abort will complete. The nodes’ logs will have been cleaned up. - 11AFS (Security) 1. (Answer True/False with justification) - “The number of distinct keys needed in AFS is O(N^2) where is N is the number of users.” 2) (Answer True/False with justification) - Explain the problems in using public-key encryption for AFS focusing on key distribution. (succinct bullets please) 3) 3a) In the second send from the client to the server (E[yr+1, HKC]) how does the server know what key to use for decrypting the message? 3b) If you were a reviewer for this paper, would you have been concerned about the integrity of the system against attacks, given that this bind protocol is also used when the user logs in first time? Why or Why not?1) False. All N users communicate with a single central entity, therefore O(N) keys sufficient.
2) Public-Key encryption would require that for every new client workstation in the network, a new pair of asymmetric keys needs to be generated. (+2)- Distributing this new key pair to ALL the workstations and keeping a replicated database of the keys (associated with the user logins) securely in ALL the workstations is challenging. (+1)- Servers (Vice) are physically secure but same guarantees cannot be made for the client workstations which could be distributed across the entire network. (+1)
3a) The client identity is known from the start of the session for its duration.
3b) Trojans for login could steal passwords or you could dump the credentials out of memory during login. AFS does not defend against this. This actually is one of the most common ways ransomware propagates today.
Information
- Description
- Engineering Flashcards on Advanced Operation Systems - Test 3, created by Jason Cole on 03/05/2021.
- Created by
- Jason Cole
- Views
- 0
- Tags
- Rating