Final Exam Solutions, Fall 2002
Part of
22C:116, fall 2002
|
Mean = 14.20 Median = 13.0 or 16.0 ________X___X___X_____X_____X_____X_X_____X_____X_______X_______ 0 . 2 . 4 . 6 . 8 . 10. 12. 14. 16. 18. 20. 22. 24. 26. 28. 30
Mean = 21.65 Median = 21.5 or 23.0 X _X___X___________________X___X_____X___X_______X_________________X_______X__ 4 . 6 . 8 . 10. 12. 14. 16. 18. 20. 22. 24. 26. 28. 30. 32. 34. 36. 38. 40.
Mean = 38.32 Median = 39.2 or 40.5 ______X_____________X_______X_______X___X_X___X_X_____X_X___ 20. 22. 24. 26. 28. 30. 32. 34. 36. 38. 40. 42. 44. 46. 48.
Mean = 59.97
Median = 57.2 or 62.2 X X
____X___X___X___X_____X_____X___X_________________X__
36. 40. 44. 48. 52. 56. 60. 64. 68. 72. 76. 80. 82.
C+ C+ B- B B B+ A- A+
If interprocess communication is relatively inexpensive compared to kernel calls, then use of a kernel call to access device I/O routines has no particular advantage for access to local devices, so we may as well use client-server interactions for access to all devices, whether local or remote.
In contrast, if interprocess communication is relatively expensive, we should avoid it whenever we access local devices, using it only to access remote devices. In this case, use of remote I/O drivers allows us to maintain device independence by making the call to a remote server appear to be a normal kernel call for access to a local device interface.
Only 2 gave good answers here. 1 more gave half of a good answer, indicating that they clearly understood the issues. 4 gave interesting answers that didn't clearly address the issues, and 3 earned no credit. Too many did not identify the issue -- relative cost of two communication models, or did not understand that the client-server model could apply locally on a single machine. Others seem to have concluded that the term server referred only to file servers, despite the fact that the term file was carefully avoided in the wording of the question!
The registry described (holding channel id, buffer start, buffer length and semaphore) obviously holds the description of an I/O operation. Therefore, we conclude that processes register I/O operations if there is a need to look them up later. When would we need to look up an I/O operation? If the operation has not yet been completed when there is a chance that new information is available to complete it. This occurs when some other process tries to do I/O on the same channel!
Therefore, we conclude that a process trying to receive from a channel will register if there is no registered sender for that channel. If there is already a registered sender, the receiver does not need to register.
Similarly, if a process is trying to send to a channel and there is no registered receiver, the process will register. If there is a registered receiver, the sender does not need to register.
Only 2 did well here, and 1 more was halfway to a good answer. 3 earned half credit for answers that concluded that all processes involved in interprocess communication must register, and 1 more earned partial credit. 3 earned no credit.
This question was based directly on the first study question. Any student who understood an efficient uniprocessor implementation of the ECOS communication primitives should have done well.
Part B: On a uniprocessor, either send will copy the data and send the completion signals or receive will copy the data and send the completion signals. What determines which primitive goes first? Hint: This is very closely related to part A.
When a process registers, this means that it cannot move the data because the process with which it will communicate has not yet executed a send or receive. Therefore, the copying of data and sending of the completion signals will be done by the sender if it finds that there is already a registered receiver, and by the receiver if it finds that there is already a registered sender.
4 did well here, and 3 more received partial credit. 3 received no credit. This suggests that some of those who received partial credit for part A actually understood more than they successfully expressed in their answers.
Part C: Suppose the sender's and receiver's buffers are not the same size. What happens at the end of the transfer. Specifically, what hapens to the registration record?
If the sender's buffer still holds data after the receiver's buffer has been filled, the registration record will be converted to a send, with the buffer pointer and count describing the part of the sender's buffer that has yet to be sent. If the receiver's buffer was not filled after the sender's buffer becomes empty, the registration record will be changed to describe a receive, with the buffer pointer and count describing the part of the receiver's buffer that remains to be filled.
3 did well here, 3 earned partial credit, and 4 earned no credit Partial credit went to those who, while not offering any hint of the implementation, at least expressed some understanding of the semantics of ECOS interprocess communication.
This problem was harder than the first ones because it rested on an understanding of the eccentric features of ECOS interprocess communication. The first parts could be answered assuming that ECOS channels were something analogous to datagram channels, comparable to the Demos model or to some lower layer inside Amoeba.
Part D: When should the registration records of a process be removed from the registry? Hint: There is a normal case and an abnormal case you must consider.
Registration records are normally deleted when the I/O operation they describe is completed, but they are also deleted when the memory region holding the buffer is deleted, for example, when the process owning that memory terminates or is aborted.
Again, 3 did well, while 6 earned partial credit for describing one or the other of the two conditions mentioned above. Only one received no credit.
Part E: In a multicomputer, where each machine's kernel maintains a local registry, what events cause a broadcast from one machine to the others on the network and how does this lead to a priority relationship between local and remote communications? Hint: Not all communication requires a broadcast!
If a process registers in the local registry, this means that there was no listing for its correspondant. Therefore, when it registers, it should also broadcast. If the process finds a correspondant in the local registry, a broadcast is not needed.
There are several ways to continue the answer from this point, depending on how the broadcast is used! If the receipt of a broadcast only does a lookup in the local registry and never registers a remote process, then local communication always takes priority over local communication. On the other hand, if receipt of such a broadcast can create a registration record for a remote process, then all registries could be identical so that there was no preference given to local or remote partners.
5 got full credit here, while 1 more had an interesting but hard to use answer that was worth partial credit. 4 received no credit.
Because ECOS channels were defined as behaving like FIFO streams, the malicious programmer's bytes are inserted between buffers sent by other users of the channel. Recipients cannot determine where the data from one sender's buffer ends and the next begins, so there is no absolute defense against this attack! Probabilistic defenses such as requiring that every logical message begin with some magic byte sequence are possible, but there is always a chance that the attacker will insert this byte sequence.
2 did well and 5 gave relevant answers worth partial credit. 3 received no credit.
This answer tested the student's understanding of the ECOS specification. Students who assumed message passing communication (where the system enforced some kind of message boundary) could not receive full credit.
Part B: Would your answer have been different if the ECOS send and receive primitives matched each send to exactly one receive, instead of having pipe-like byte serial FIFO semantics?
If the receiver had a guarantee that each receive was matched to one send, then legitimate users of the service offered by the receiver would not see their messages corrupted. Because each client-to-server message in ECOS contains at least 128 bits (the identity of the reply channel to use), the server will probably be able to detect the fact that the malicious user's messages were only one byte and ignore them.
Simple yes-no answers here were hard to grade, but fortunately, few gave them and in several cases, they were wrong anyway. 4 did well here, 2 got partial credit, and 4 earned no credit.
Part C: In later Unix systems (POSIX), the mkfifo command creates a named pipe (a file of type FIFO) attached to the directory tree. Given your answer to problem 1, comment on the utility of named pipes as public gateways to servers.
Because ECOS channels behave like Unix pipes once the sender and receiver agree on a channel ID or once they manage to create and distribute the rights to a pipe, the answers above lead to the conclusion that Unix named pipes are not useful as public gateways for client-server interaction.
1 did well here, all of the remainder earned no credit.
The most common problem here was to assume that the protection against this attack that mattered was some kind of access rights restriction that would prevent the malicious user from using the channel in question. It is true that Unix named pipes offer such protections, but the context makes this irrelevant! The context is a public server to which all users are entitled to send messages requesting service! Therefore, by definition, the channel is public, with no access restrictions!
ECOS has no mechanism that would allow the server to wait for a message on any of several channels. Server-side authentication implemented as specified would allocate one channel per object, using the channel ID as an object ID, and this requires that the server wait for a message on any of a large set of channels (one per object implemented by that server).
1 did well here, while 6 earned partial credit by focusing on secondary issues without seeing the big problem. 3 earned no credit.
The third and fourrth study questions should have prepared for this problem, since working through the design of a widget server, including issues of channel use, should have led people to think about the possibility of server-side authentication and the possibility of encoding object ID as part of the channel ID.
The most popular secondary problem that distracted people was the problem of transmitting the key or magic number that is required to encode access rights and permission to use a particular object. There is nothing in the ECOS architecture to facilitate passing this key, but there is also nothing to prevent passing this key as part of the message to the server, so this is really a non-issue.
Given that the variable sized part of the client-to-server message must be passed as a second message on a different channel, the first message will include the channel ID to be used for this follow-up, along with a fixed-sized description of the parameter list; at minimum, the latter would be the byte count for the parameter message, assuming that the message itself contains all of the remainder of the parameter description.
3 did well here, 2 more were very good, and 4 forgot to mention the need to pass the channel ID because they were distracted by the far more interesting questions involving passing a variable sized argument list. Only 1 received no credit.
This question also followed naturally from the study questions that asked for the design of an RPC protocol on top of ECOS and for the design of a server to run under ECOS.
Part B: Why is it necessary to send the arguments in a separate message and using a different channel from the initial message you described in part A?
Public client-to-server channels in ECOS work best if all message are the same size; see question 3 for examples of why this is so! Therefore, we must pass the variable sized part of the message from client to server using a second channel.
4 did well here, 6 received no credit.
This question was, at heart, a broad hint about the correct answer to part A. The answers distinguished between those who'd understood the issues raised by part A and the ones who had reasonable answers to that part without really understanding the issues.
Part C: What channel(s) should be used for the reply, and how many distinct receives are required to capture the reply, assuming that the server determines the size and number of items in the reply?
The same channel used to pass the variable-sized part of the parameter list from client to server can be used as a reply channel, assuming that the client allocates this channel and tries to do so in a way that makes it extremely unlikely that anyone else will use this channel.
The same arguments that required the parameters to be passed in two parts, one fixed-size and one variable-size, requires the reply to be broken up this way. The first reply could be as simple as a statement of the number of bytes in the remainder of the reply. This would necessarily be received using two separate receives. Curiously, it could be sent using a single send, but the question was not worded to require this curiosity to be noticed!
3 did well here, 2 more almost did well, and 4 more earned partial credit. Only 1 received no credit.
ECOS channels have no location dependency, while Demos channels are tied intimately to the receiving process. Therefore, if an ECOS process is moved, there is no need for an elaborate system of forwarding addresses and there is no need to try to do anything like garbage collection to collect old forwarding addresses when they are no longer needed.
3 did very well, 2 more did well, and 2 earned half credit. 1 more earned some credit, and only 2 earned no credit.
No study question warned abut this, but a student who studied ECOS in the context of Demos, Amoeba and Mach should have at least wondered about migration, since this was discussed at least briefly in the contexts of all these systems.
Part B: An ECOS process registers to receive a buffer of data on some channel. Then, the process is frozen so it can be moved to a different machine. What problems does this cause, and why were there no similar problems in Demos MP?
Demos used synchronous blocking message passing, so the migration mechanism never had to address the problem of a process being moved while in the middle of a message exchange. In ECOS, in contrast, a process may have many buffers registered to be sent or received; when such a process is moved, the registration records for its buffers must be found and moved along with it.
5 did well here, and 5 earned no credit. Several of the wrong answers were little more than copies from the notes on Demos MP, explaining how process migration was done there, with no reference to ECOS.