资源描述
SYSTEMSPRINCIPLES AND PARADIGMSSECOND EDITIONPROBLEM SOLUTIONSANDREW S. TANENBAUMMAARTEN VAN STEENVrije UniversiteitAmsterdam, The NetherlandsPRENTICE HALLUPPER SADDLE RIVER, NJ 07458SOLUTIONS TO CHAPTER 1 PROBLEMS1. Q: A n alter native de.n iti on for a distributed system is that of a collecti on of independent computers providing the view of being a single system that is, it is completely hidde n from users that there eve n multiple computers. Give an example where this view would come in very han dy.A: What immediately comes to mind is parallel computing. If one could desig n programs that run without any serious modi.cati ons on distributed systems that appear to be the same as non distributed systems, life would be so much easier. Achiev ing a sin gle-system view is by now con sidered virtually impossible whe n performa nee is in play.2. Q: What is the role of middleware in a distributed system?A: To enhance the distribution transparency that is missing in network operating systems. In other words, middleware aims at improv ing the sin gle-system view that a distributed system should have.3. Q: Many networked systems are organized in terms of a back of.ce and a front of.ce. How does orga ni zati ons match with the cohere nt view we dema nd for a distributed system?A: A mistake easily made is to assume that a distributed system as operating in an orga ni zati on, should be spread across the en tire orga ni zati on. In practice, we see distributed systems being in stalled along the way that an orga ni zati on is split up. In this sen se, we could have a distributed system support ing backof .ce procedures and processes, as well as a separate fron t-of.ce system. Of course, the two may be coupled, but there is no reas on for lett ing this coupli ng be fully tra nspare nt.4. Q: Explain what is meant by (distribution) transparency, and give examples of differe nt types of tran spare ncy.A: Distribution transparency is the phenomenon by which distribution aspects in a system are hidde n from users and applicati ons. Examples in clude access tra nspare ncy, locati on tra nspare ncy, migrati on tran spare ncy, relocati on tra nspare ncy, replicati on tra nspare ncy, con curre ncy tra nspare ncy, failure tra nspare ncy, and persiste nee tra nspare ncy.5. Q: Why is it sometimes so hard to hide the occurrenee and recovery from failures in a distributed system?A: It is gen erally impossible to detect whether a server is actually dow n, or that it is simply slow in resp onding. Con seque ntly, a system may have to report that a service is not available, although, in fact, the server is just slow. 2 PROBLEM SOLUTIONS FOR CHAPTER 16. Q: Why is it not always a good idea to aim at implementing the highest degree of tra nspare ncy possible?A: Aiming at the highest degree of transparency may lead to a considerable loss of performa nee that users are not willi ng to accept.7. Q: What is an open distributed system and what bene.ts does openness provide? A: An open distributed system offers services according to clearly de.nedrules. An ope n system is capable of easily in teroperati ng with other ope n systems but also allows applicati ons to be easily ported betwee n differe nt impleme ntati ons of the same system.8. Q: Describe precisely what is meant by a scalable system.A: A system is scalable with respect to either its number of components, geographical size, or num ber and size of adm ini strative doma in s, if it can grow in one or more of these dime nsions without an un acceptable loss of performa nee.9. Q: Scalability can be achieved by applying different techniques. What are these tech niq ues?A: Scali ng can be achieved through distributi on, replicati on, and cach ing.10. Q: Explain what is meant by a virtual organization and give a hint on how such orga ni zati ons could be impleme nted.A: A virtual organization (VO) de.nes a group of users/applications that have access to a speci.ed group of resources, which may be distributed across many differe nt computers, owned by many differe nt orga ni zati ons. In effect, a VO de.nes who has access to what. This also suggests that the resources should keep an acco unt of foreig n users along with their access rights. This can ofte n be done using sta ndard access con trol mecha ni sms (like the rwx bits in UNIX), although foreig n users may n eed to have a special acco unt. The latter complicates matters con siderably.11. Q: Whe n a tra nsacti on is aborted, we have said that the world is restored to its previous state, as though the tran sacti on had n ever happe ned. We lied. Give an example where resetti ng the world is impossible.A: Any situation in which physical I/O has occurred cannot be reset. For example, if the process has pr in ted some output, the ink cannot be removed from the paper. Also, in a system that con trols any kind of in dustrial process, it is usually impossible to undo work that has bee n done.12. Q: Executi ng n ested tra nsacti ons requires some form of coord in ati on. Expla in what a coord in ator should actually do.A: A coord inator need simply ensure that if one of the nested transactions aborts, that all other subtra nsacti ons abort as well. Likewise, it should PROBLEM SOLUTIONS FOR CHAPTER 1 3 coord in ate that all of them commit whe n each of them can. To this end, a n ested tra nsacti on should wait to commit un til it is told to do so by the coord in ator.13. Q: We argued that distribution transparancy may not be in place for pervasice systems. This stateme nt is not true for all types of tra nspare ncies. Give an example.A: Think of migration transparency. In mnay pervasive systems, components are mobile and will n eed to re-establish conn ecti ons whe n moving from one access point to ano ther. Preferably, such han dovers should be completely tra nspare nt to the user. Likewise, it can be argued that many other types of tra nspare ncies should be supported as well. However, what should not be hidde n is a user is possibly access ing resources that are directly coupled to the users curre nt en vir onment.14. Q: We already gave some examples of distributed pervasive systems: home systems, electr onic health-care systems, and sen sor n etworks. Exte nd this list with more examples.A: There are quite a few other examples of pervasive systems. Think of largescale wireless mesh n etworks in cities or n eighborhoods that provide services such as In ter net access, but also form the basis for other services like a n ews system. There are systems for habitat mon itori ng (as in wildlife resorts), electr onic jails by which offen ders are continu ously mon itored, large-scale in tegrated sports systems, of.ce systems deplo ying active badges to know about the whereabouts of their employees, and so on.15. Q: Sketch a design for a home system consisting of a separate media server that will allow for the attachme nt of a wireless clie nt. The latter is conn ectedto (an alog) audio/video equipme nt and tra nsforms the digital media streams to an alog output. The server runs on a separate machi ne, possibly conn ected to the In ter net, but has no keyboard an d/or mon itor conn ected.SOLUTIONS TO CHAPTER 2 PROBLEMS1. Q: If a client and a server are placed far apart, we may see network latency domin ati ng overall performa nee. How can we tackle this problem?A: It really depends on how the client is organized. It may be possible to divide the clie nt-side code into smaller parts that can run separately .In that case, whe n one part is wait ing for the server to resp ond, we can schedule ano ther part. Alter natively, we may be able to rearra nge the clie nt so that it can do other work after hav ing sent a request to the server. This last soluti on effectively replaces the syn chr onous clie nt-server com muni cati on with asyn chr onous on e-way com muni cati on.4 PROBLEM SOLUTIONS FOR CHAPTER 22. Q: What is a three-tiered client-server architecture?A: A three-tiered client-server architecture consists of three logical layers, where each layer is, in pr in ciple, impleme nted at a separate mach ine. The highest layer con sists of a clie nt user in terface, the middle layer contains the actual applicati on, and the lowest layer impleme nts the data that are being used.3. Q: What is the differenee between a vertical distribution and a horizontal distribution? A: Vertical distribution refers to the distribution of the different layers in amultitiered architectures across multiple machi nes. In prin ciple, each layer is impleme nted on a differe nt machi ne. Horiz on tai distributi on deals with the distributi on of a sin gle layer across multiple machi nes, such as distribut ing a sin gle database.4. Q: Consider a chain of processes P1, P2,Pn implementing a multitieredclient-server architecture. Process Pi is client of process Pi+1, and Pi will return a reply to Pi-1 only after receiving a reply from Pi+1. What are the main problems with this orga ni zati on whe n tak ing a look at the request-reply performa nee at process P1?A: Performanee can be expected to be bad for large n. The problem is that each com muni cati on betwee n two successive layers is, in pr in ciple, betwee n two different machines. Consequently, the performanee between P1 and P2 may also be determined by n - 2 request-reply interactions between the other layers. Ano ther problem is that if one machi ne in the chai n performs badly or is eve n temporarily un reachable, the n this will immediately degrade the performa nee at the highest level.5. Q: In a structured overlay network, messages are routed according to the topology of the overlay. What is an importa nt disadva ntage of this approach?A: The problem is that we are dealing only with logical paths. It may very well be the case that two no des A and B which are n eighbors in the overlay n etwork are physically placed far apart. As a con seque nee, the logically short path between A and B may require routing a message along a very long path in the un derly ing physical n etwork.6. Q: Consider the CAN network from Fig. 2-0. How would you route a message from the node with coord in ates (0.2,0.3) to the one with coord in ates (0.9,0.6)?A: There are several possibilities, but if we want to follow the shortest path accord ing to a Euclidea n dista nee, we should follow the route (0.2,0.3) (0.6,0.7) (0.9,0.6), which has a dista nee of 0.882. The alternative route (0.2,0.3) (0.7,0.2) (0.9,0.6) has a dista nee of 0.957.PROBLEM SOLUTIONS FOR CHAPTER 2 57. Q: Con sideri ng that a node in CAN knows the coord in ates of its immediate n eighbors, a reas on able routi ng policy would be to forward a message to the closest node toward the desti nati on. How good is this policy?A: In our example from the previous question, it can already be seen that it n eed not lead to the best route. If node (0.2,0.3) follows this policy for the message dest ined for node (0.9,0.6), it would send it off to node (0.7,0.2).8. Q: Consider an unstructured overlay network in which each node randomly chooses e neighbors. If P and Q are both neighbors of R, what is the probability that they are also n eighbors of each other?A: Con sider a n etwork of N no des. If each node chooses c n eighbors at ran dom, then the probability that P will choose Q, or Q chooses P is roughly 2c/ (N-1).9. Q: Consider again an unstructured overlay network in which every node randomly chooses c neighbors. To search for ae, a node oods a request to itsn eighbors and requests those to ood the request once more. How many no des will be reached?A: An easy upper bound can be computed as c (c -1), but in that case we ignore the fact that neighbors of node P can be each others neighbor as well. The probability q that a neighbor of P will ood a message only to nonneighbors of P is 1 minus the probability of sending it to at least one neighbor of P: q = 1 - c-1 k=1 S沁 c-1 k 00 沁 cN-100ke1 -cN-100c-1-kIn that case, this ood ing strategy will reach c q (c-1) no des. For example, with c = 20 and N = 10, 000, a query will be ooded to 365.817 nodes.10. Q: Not every node in a peer-to-peer network should become superpeer. What are reas on able requireme nts that a superpeer should meet?A: In the .rst place, the node should be highly available, as many other no des rely on it. Also, it should have eno ugh capacity to process requests. Most importa nt perhaps is that fact that it can be trusted to do its job well.11. Q: Consider a BitTorrent system in which each node has an outgoing link with a ban dwidth capacity Bout a nd an incoming link with ban dwidth capacity Bin. Some of these no des (called seeds) volun tarily offeres to be dow nl oaded by others. What is the maximum dow nl oad capacity of a BitTorre nt clie nt if we assume that it can con tact at most one seed at a time?A: We n eed to take into acco unt that the outgo ing capacity of seed ing no des needs to be shared between clients. Let us assume that there are S seeders and N clients, and that each client randomly picks one of the seeders. The joint outgoing capacity of the seeders is S Bout, giving each of the clients5 Bout/ N immediate dow nl oad capacity .In additi on, if clie nts help each6 PROBLEM SOLUTIONS FOR CHAPTER 2other, each one of them will be able to download chunks at a rate of Bout, assuming that Bin Bout. Note that because of the tit-for-tat policy, the download capacity of a BitTorrent client is mainly dictated by its outgoingcapacity. In conclusion, the total download capacity will be S Bout/ N + Bout.12. Q: Give a compelling (technical) argument why the tit-for-tat policy as used in BitTorre nt is far from optimal fore shari ng in the Intern et.A: The reasoning is relatively simple. Most BitTorrent clients are operated beh ind asymmetric links such as provided by ADSL or cable modems. In gen eral, clie nts are offered a high incoming ban dwidth capacity, but no one really expects that clie nts have services to offer. BitTorre nt does not make this assumpti on, and tur ns clie nts into collaborative servers. Having symmetric conn ecti ons is the n a much better match for the tit-for-tat policy.13. Q: We gave two examples of using interceptors in adaptive middleware. What other examples come to mind?A: There are several. For example, we could use an interceptor to support mobility .In that case, a request-level in terceptor would .rst look up the curre nt locati on of a refere need object before the call is forwarded. Likewise, an in terceptor can be used to tran spare ntly en crypt messages whe n security is at stake. Ano ther example is whe n logg ing is n eeded. In stead of letti ng this be han dled by the applicati on, we could simply in sert a method-speci.c in terceptor that would record speci.c eve nts before pass ing a call to the refere need object. More of such example will easily come to mind.14. Q: To what exte nt are in terceptors depe ndent on the middleware where they are deployed?A: In general, interceptors will be highly middleware-dependent. If we consider Fig. 2-0, it is easy to see why: the clie nt stub will most likely be tightly bound to the lower level in terfaces offered by the middleware, just as messagelevel in terceptors will be highly depe ndent on the in teracti on betwee n middleware and the local operati ng system. Nevertheless, it is possible to sta ndardize these in terfaces, ope ning the road to develop ing portable in terceptors, albeit ofte n for a speci.c class of middleware. This last approach has bee n followed for CORBA.15. Q: Moder n cars are stuffed with electr onic devices. Give some examples of feed-back con trol systems in cars.A: One obvious one is cruise control. On the one hand this subsystem measures curre nt speed, and whe n it cha nges from the required sett ing, the car is slowed dow n or speeded up. The an ti-lock brak ing systems (ABS) is ano ther example. By pulsati ng the brakes of a car, while at the same time regulat ing the pressure that each wheel is exert in g, it is possible to con ti nue steeri ng without los ing con trol because the wheels are blocked. A last example is PROBLEM SOLUTIONS FOR CHAPTER 2 7 formed by the closed circuit of sen sors that mon itor engine con diti on. As soon as a dan gerous state is reached, a car may come to an automatic halt to preve nt the worst.16. Q: Give an example of a self-managing system in which the analysis component is completely distributed or eve n hidde n.A: We already came across this type of system: in unstructured peer-to-peer systems where no des excha nge membership in formati on, we saw how a topology could be gen erated. The an alysis comp onent con sists of dropp ing certa in links that will not help con verge to the inten ded topology. Similar examples can be found in other such systems as we referred to as well.17. Q: Sketch a solution to automatically determine the best trace length for predicting replicati on policies in Globule.A: An origin server would need to use the traces from Ti to Ti+1 to check its predicti on of policy for that period. It can simply see whether the policy that would have bee n chose n on the actual access patter ns is the same as the one chosen based on the requests in the period Ti-1 to Ti. This would allow the server to compute the predicti on error. By vary ing the trace len gth, the orig in server would be able .nd the len gth for which the predicti on is mini mal. I n this way, we get an automatic determ in ati on of the optimal trace len gth, effectively con tribut ing to the self-ma naging n ature of Globule.18. Q: Using existing software, design and implement a BitTorrent-based system for distribut inges to many clie nts from a sin gle, powerful server. Matters are simpli.ed by using a sta ndard Web server that can operate as tracker.SOLUTIONS TO CHAPTER 3 PROBLEMS1. Q: In this problem you are to compare reading ae using a single-threaded e server and a multithreaded server. It takes 15 msec to get a request for work, dispatch it, and do the rest of the n ecessary process ing, assu ming that the data n eeded are in a cache in main memory. If a disk operati on is n eeded, as is the case on e-third of the time, an additi onal 75 msec is required, dur ing which time the thread sleeps. How many requests/sec can the server han dle if it is sin gle threaded? If it is multithreaded?A: In the single-threaded case, the cache hits take 15 msec and cache misses take 90 msec. The weighted average is 2/3 T5 + 1/390. Thus the mea n request takes 40 msec and the server can do 25 per sec ond. For a multithreaded server, all the wait ing for the disk is overlapped, so every request takes 15 msec, and the server can han dle 66 2/3 requests per sec ond.8 PROBLEM SOLUTIONS FOR CHAPTER 32. Q: Would it make sense to limit the number of threads in a server process? A: Yes, for two reasons. First, threads require memory for setting up their own private stack. Con seque ntly, hav ing many threads may con sume too much memory for the server to work properly. Ano ther, more serious reas on, is that,to an operat ing system, in depe ndent threads tend to operate in a chaotic manner.In a virtual memory system it may be dif.cult to build a relatively stable work ing set, result ing in many page faults and thus I/O. Having many threads may thus lead to a performa nee degradati on result ing from page thrash ing.Eve n in those cases where everyth ing .ts into memory, we may easily see that memory is accessed follow ing a chaotic patter n ren deri ng caches useless. Agai n, performa nee may degrade in comparis on to the sin gle-threaded case.3. Q: In the text, we described a multithreadede server, showing why it is better tha n a sin gle-threaded server and a .n ite-state mach ine
展开阅读全文