Test_2

Question 1

2. [SEE QUESTION] a.(2 points) E1 and E6?

Answer 1

Transitively E1 happened before E6. P1 send message to P2 at E3. The corresponding receipt is E6 msg-received from E1.

Question 2

2. [SEE QUESTION] (b) (2 points) E4 and E6?

Answer 2

Concurrent, e4 is a local event so it happened after e3 but we don’t know if e6 happened before e4 because we don’t know what time P2 received the message sent in e3.

Question 3

2. [SEE QUESTION] (c) (2 points) E6 and E8?

Answer 3

E6 happened before E8, since both the events belong to same program and are executed sequentially.

Question 4

2. [SEE QUESTION] (d) (2 points) E3 and E10?

Answer 4

E3 happened before E10. E3-> E6 -> E8 -> E9 -> E10.

PIAZZA: E3 happened before E10. E3 happened before E6 (communication pair), E6 happened before E9 (Same Process), and E9 happened before E10 (communication pair). Therefore, by the transitive property, E3 happened before E10.

Question 5

2. [SEE QUESTION] (e) (2 points) E5 and E10?

Answer 5

PIAZZA: E5 and E10 are Concurrent Events - they’re separate events occurring in different processes that are not part of a communication pair and do not have a transitive relationship.

Question 6

3. [SEE QUESTION] (a) What additional machinery would you need to make sure the algorithm will work correctly if the first assumption is relaxed?

Answer 6

From Spring 2020 Final:

• Every node maintains a distinct sequence number for each peer
• Sending a message will include the relevant sequence number for that peer, in addition the current information (lock requested, timestamp). After sending a message, the sequence number is incremented
• When receiving a message, if sequence number is one greater than the previous message then the message is in order and can be processed. Otherwise the message is out of order and must be buffered locally until the earlier message(s) arrive.

Question 7

3. [SEE QUESTION] (b) What additional machinery would you need to make sure the algorithm will work correctly if the second assumption is relaxed?

Answer 7

• Include sequence number machinery above as a starting point
• Introduce network packet acknowledgment (different from the normal ACK for Lamport’s M.E) mechanism similar to that which is seen in TCP
• When receiving a packet:
  
  • • If the message has not been seen before (determined from the sequence number) process the packet.
  • • If it’s a duplicate message (perhaps the previous network ack was lost so the sender retransmitted), just drop the packet
  • • In either case, send a network ack
• When sending a packet:
  
  • • buffer the message until a network ack is received for the packet
  • • Retransmit the message if no network ack received within a timeout period, which could indicate a lost message
  • • Even if this ends up sending a duplicate message, the sequence number uniquely identifies it and the receiver will ignore the duplicate

Question 8

4. [SEE QUESTION] (10 points, 7 mins) (Latency Reduction in RPC)

Answer 8

• the client stub stays in the user space.
• keep a structured mechanism for the stub to communicate its arguments into the kernel without copying them in - a shared descriptor
• the scatter/gather DMA controller can read this shared descriptor directly without any copying of data EXCEPT the (unavoidable) copy the DMA controller itself makes when it reads the arguments from the memory locations, put the information in a network packet and sends it over the wire.

Question 9

5. (10 points, 7 minutes) (Active Networks)
   One could argue that Software Defined Networking (SDN) is “old wine in a new bottle”.

(a) Justify this argument with a few concise bullets.

Answer 9

SDN has become the reincarnation of Active Networks by taking the motivations, research, and techniques for Active networks and applied it to a new “killer-app” environment, data-center networks.

Specifically it contributed the following key 3 ideas:

1. Programmable functions in the network to lower the barrier to innovation
2. Network virtualization, and the ability to demultiplex to software programs based on packet headers.
3. The vision of a unified architecture for middlebox orchestration.

Question 10

5. (10 points, 7 minutes) (Active Networks)
   One could argue that Software Defined Networking (SDN) is “old wine in a new bottle”.

(b) With a few concise bullets, summarize the social and technology enablers that has made this wine drinkable now.

Answer 10

• The rise of cloud computing, which promotes the idea of utility computing wherein multiple tenants/businesses can host portions of their corporate network simultaneously on the same computing resources using the safe isolation of network traffic provided by SDN.
• The isolation of networking traffic is provided by virtualization of the network, allowing for a level of abstraction that also eases management of the network hardware.
• Chipsets are now available for building your own router to enable the creation of a SDN and avoiding lockin to router vendors who were loath to allowing Active Networking or SDN.

Question 11

6. [SEE QUESTION] (5 points, 3 minutes) (Ensemble/Nuprl)

Answer 11

No, this is not a contradiction:

• The Ensemble system was built over three design stages: specification, configuration (coding), and optimization
• OCaml was selected for the configuration (code) stage because of its support for precise formal semantics and ability to be compiled to efficient machine code
• The quality-of-life features of OCaml (garbage collection, easy marshalling and unmarshalling of data structures) also led to a faster development cycle and a smaller code base
• The optimization stage of Ensemble’s development circumvented the performance penalties of these features, but did not invalidate their use
• Optimization tools like Nuprl can take existing code and make it faster, but they cannot create the initial code itself

Question 12

7. [SEE QUESTION] (5 points, 3 minutes) (Spring Kernel)

Answer 12

To optimize this, the client-stub subcontractor can first check to see the location of the server. If the client and server are actually co-located on the same node (i.e. they’re both on the same machine) then the data can be marshalled into a shared memory space that the server can access directly, without the data needing to be transmitted at all.

Question 13

8. [SEE QUESTION] (5 points, 3 minutes) (EJB)

(a) What functionalities would you put into the Web container (that interfaces with the client browsers)?

Answer 13

From Fall 2020 Exam #2:
Functionalities to put in the Web container:
i. Servlet which corresponds to a session
ii. Presentation logic for each servlet
iii. NOT the business logic so that it won’t be exposed

Question 14

8. [SEE QUESTION] (5 points, 3 minutes) (EJB)

(b) What functionalities would you put into the EJB container?

Answer 14

From Fall 2020 Exam #2:

i. A session façade that corresponds to each servlet in the web container
ii. The business logic layer associated with each session façade
iii. Entity beans which are the data access objects serving as an interface for the business logic layer to access the database
iv. With this design, the business logic is not exposed and also parallelism across independent client requests and within the client requests can be exploited through the entity beans.

Question 15

9. [SEE QUESTION] (15 points, 10 minutes) (GMS)

a) (5 points

Answer 15

• In the default implementation, only copies of clean pages are placed in cluster memory with GMS, so if node n2 shuts down the page can be retrieved again from disk. It will be in disk because GMS writes dirty pages to disk before bringing them into global memory (So before writing N2, page X is updated on the disk)
• If a dirty node were paged out, any changes would be lost when N2 went down, and N1 would need to fetch the outdated copy from disk. This data loss is why GMS does not store dirty pages. It does, however, offer performance advantages to make this change. Maybe it is replicated on other nodes?

Question 16

9. [SEE QUESTION] (15 points, 10 minutes) (GMS)

b) (5 points

Answer 16

False, the algorithm identifies the min-age for the M oldest pages that are likely to be evicted during the next epoch. What actually gets evicted depends on the timing of page faults. One of the candidate pages could be requested before it needs to be evicted, sparing it from this epoch.

(see Fall 2017 Q4a)

Question 17

9. [SEE QUESTION] (15 points, 10 minutes) (GMS)

c) (5 points

Answer 17

(gms paper section 4.4)

• Check in with master node
• Master node notifies all existing members
• Master node distributes new copies of page-ownership-directory to each node
• Each node distributes portions of the global-cache-directory to the new node

Question 18

10. [SEE QUESTION] (20 points, 15 minutes) (DSM/GMS)

(a) (i) (5 points) What should happen before P4 starts executing CS1? Justify your answer.

Answer 18

P4 must acquire L1 and perform consistency actions on lock acquire

1. Acquiring L1 will include some information about modified pages under L1, which includes X
2. If P4 has an existing copy of page X, it is invalidated to generate a fault on future accesses

Question 19

10. [SEE QUESTION] (20 points, 15 minutes) (DSM/GMS)
    (a) (ii) (5 points) While inside CS1, P4 accesses page X. What should happen to ensure correct execution? Justify your answer.

Answer 19

If P4 has an outdated copy, it was already invalidated during acquisition of L1

1. Prior to use, diffs associated with the lock must be acquired and applied in the order they were created. So Xd1 must be applied first, then Xd2. Note Xd3 is absent because it happened under a different lock, L2
2. The handler upgrades the access rights to the now up-to-date page X to allow writes (until the next invalidation)

Question 20

10. [SEE QUESTION] (20 points, 15 minutes) (DSM/GMS)

(b) (5 points) (Answer True/False with justification. No credit without justification).
In Treadmarks, upon a page fault for a page X in Node N1, the DSM software on N1 broadcasts the virtual page number (VPN) of the faulting page to all the peer nodes.

Answer 20

Lec 07b video 16:
False, Treadmarks in general minimize network usage (hence LRC). The DSM software knows the page owner via its bookkeeping and can directly contact them to get the new page. Every other node doesn’t need to know.

Question 21

10. [SEE QUESTION] (20 points, 15 minutes) (DSM/GMS)

(c) (5 points)
Inspired by the material they learned, alums of OMSCS 6210 decide to design a system that combines services offered by GMS and DSM in one integrated system. Give them your sketch of a design for integrating DSM and GMS in one unified system. (Concise bullets please.)

Answer 21

• GMS is a paging facility and quicker recovery from page faults (doesn’t deal with coherence)
  
  • • In GMS, nodes of a cluster offer up their unused memory as global memory to store pages of the cluster
  • • Therefore, upon a page fault, a node can check the global memory of other nodes for the page first, which is much faster than going to the disk
• DSM gives us memory coherence via LRC multi-writer coherence protocol
  
  • • In DSM, nodes keep track of updates they make to a page, which are condensed to diffs
  • • If a node wishes to write to a page it first collects and applies, in order, all diffs made to that page by other writers
• Combining GMS and DSM, we want to create a system that maintains coherence at the granularity of pages while still allowing multiple threads to write the same page

Question 22

11. [SEE QUESTION] (10 points, 7 minutes) (DFS)

(a) Multiple network servers can provide file system service.

Answer 22

True, the directory tree can be partitioned across multiple servers, such as having one server for faculty files and one server for student files. Single file will still be on only one server, can cause hotspots.

Question 23

11. [SEE QUESTION] (10 points, 7 minutes) (DFS)
    (b) The network servers for the data (actual file content) and the metadata (information about client nodes that are using the file, etc.) for a given file are not necessarily the same.

Answer 23

False, in traditional NFS metadata lives on the same node as the data itself (which xFS complains can lead to hotspots)

Question 24

11. [SEE QUESTION] (10 points, 7 minutes) (DFS)

c) Individual files are striped across the disks of multiple network servers on the Local Area Network (LAN

Answer 24

False, an individual file is only serviced by a single server, which leads to hotspots

Question 25

11. [SEE QUESTION] (10 points, 7 minutes) (DFS)
    (d) A file cached at a client may be used to serve the needs of other network clients for the same file bypassing the network server that hosts the file on its disk.

Answer 25

False, NFS doesn’t treat everyone as peers. Only the server hosting the file contributes to serving the file.