-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathLab-2.html
413 lines (388 loc) · 24.3 KB
/
Lab-2.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
<!DOCTYPE html><html><head><meta charset="utf-8"><style>html { font-size: 100%; overflow-y: scroll; -webkit-text-size-adjust: 100%; -ms-text-size-adjust: 100%; }
body{
color:#444;
font-family:Georgia, Palatino, 'Palatino Linotype', Times, 'Times New Roman',
"Hiragino Sans GB", "STXihei", "微软雅黑", serif;
font-size:12px;
line-height:1.5em;
background:#fefefe;
width: 55em;
margin: 10px auto;
padding: 1em;
outline: 1300px solid #FAFAFA;
}
a{ color: #0645ad; text-decoration:none;}
a:visited{ color: #0b0080; }
a:hover{ color: #06e; }
a:active{ color:#faa700; }
a:focus{ outline: thin dotted; }
a:hover, a:active{ outline: 0; }
span.backtick {
border:1px solid #EAEAEA;
border-radius:3px;
background:#F8F8F8;
padding:0 3px 0 3px;
}
::-moz-selection{background:rgba(255,255,0,0.3);color:#000}
::selection{background:rgba(255,255,0,0.3);color:#000}
a::-moz-selection{background:rgba(255,255,0,0.3);color:#0645ad}
a::selection{background:rgba(255,255,0,0.3);color:#0645ad}
p{
margin:1em 0;
}
img{
max-width:100%;
}
h1,h2,h3,h4,h5,h6{
font-weight:normal;
color:#111;
line-height:1em;
}
h4,h5,h6{ font-weight: bold; }
h1{ font-size:2.5em; }
h2{ font-size:2em; border-bottom:1px solid silver; padding-bottom: 5px; }
h3{ font-size:1.5em; }
h4{ font-size:1.2em; }
h5{ font-size:1em; }
h6{ font-size:0.9em; }
blockquote{
color:#666666;
margin:0;
padding-left: 3em;
border-left: 0.5em #EEE solid;
}
hr { display: block; height: 2px; border: 0; border-top: 1px solid #aaa;border-bottom: 1px solid #eee; margin: 1em 0; padding: 0; }
pre , code, kbd, samp {
color: #000;
font-family: monospace;
font-size: 0.88em;
border-radius:3px;
background-color: #F8F8F8;
border: 1px solid #CCC;
}
pre { white-space: pre; white-space: pre-wrap; word-wrap: break-word; padding: 5px 12px;}
pre code { border: 0px !important; padding: 0;}
code { padding: 0 3px 0 3px; }
b, strong { font-weight: bold; }
dfn { font-style: italic; }
ins { background: #ff9; color: #000; text-decoration: none; }
mark { background: #ff0; color: #000; font-style: italic; font-weight: bold; }
sub, sup { font-size: 75%; line-height: 0; position: relative; vertical-align: baseline; }
sup { top: -0.5em; }
sub { bottom: -0.25em; }
ul, ol { margin: 1em 0; padding: 0 0 0 2em; }
li p:last-child { margin:0 }
dd { margin: 0 0 0 2em; }
img { border: 0; -ms-interpolation-mode: bicubic; vertical-align: middle; }
table { border-collapse: collapse; border-spacing: 0; }
td { vertical-align: top; }
@media only screen and (min-width: 480px) {
body{font-size:14px;}
}
@media only screen and (min-width: 768px) {
body{font-size:16px;}
}
@media print {
* { background: transparent !important; color: black !important; filter:none !important; -ms-filter: none !important; }
body{font-size:12pt; max-width:100%; outline:none;}
a, a:visited { text-decoration: underline; }
hr { height: 1px; border:0; border-bottom:1px solid black; }
a[href]:after { content: " (" attr(href) ")"; }
abbr[title]:after { content: " (" attr(title) ")"; }
.ir a:after, a[href^="javascript:"]:after, a[href^="#"]:after { content: ""; }
pre, blockquote { border: 1px solid #999; padding-right: 1em; page-break-inside: avoid; }
tr, img { page-break-inside: avoid; }
img { max-width: 100% !important; }
@page :left { margin: 15mm 20mm 15mm 10mm; }
@page :right { margin: 15mm 10mm 15mm 20mm; }
p, h2, h3 { orphans: 3; widows: 3; }
h2, h3 { page-break-after: avoid; }
}
</style><title>Lab-2</title></head><body><h1 id="lab-2">Lab-2: RPC and Lock Server</h1>
<h3>Due: 10-14-2018 23:59 (UTC+8)</h3>
<h1></h1>
<h2 id="introduction">Introduction</h2>
<ul>
<li>This lab includes two parts. In <b>Part1</b> you will use RPC to implement a single client file server.
In <b>Part2</b>, you will implememnt a lock server
and add locking to ensure that concurrent operations to the same file/directory from different yfs_clients occur one at a time.</li>
</li>
</ul>
</li>
<ul>
<li>If you have questions about this lab, either in programming environment or requirement, please ask TA: Li Wentai (liweta@sjtu.edu.cn).</li>
</ul>
<h2 id="getting-started">Getting started</h2>
<ul>
<li>
<p>Please backup your solution to lab1 before starting the steps below</p>
<ul>
<li>
<p>At first, please remember to save your lab1 solution:
<pre>
% cd lab-cse/lab1
% git commit -a -m “solution for lab1” </pre></p>
</li>
<li>
<p>Then, pull from the repository:
<pre>
% git pull
remote: Counting objects: 43, done.
…
[new branch] lab2 -> origin/lab2
Already up-to-date
</pre> </p>
</li>
<li>
<p>Then, change to lab2 branch:
<pre>
% git checkout lab2
</pre></p>
</li>
<li>
<p>Merge with lab1, and solve the conflict by yourself (mainly in fuse.cc and yfs_client.cc):
<pre>% git merge lab1
Auto-merging fuse.cc
CONFLICT (content): Merge conflict in yfs_client.cc
Auto-merging yfs_client.cc
CONFLICT (content): Merge conflict in ifs_client.cc
Automatic merge failed; fix conflicts and then commit the result
......</pre></p>
</li>
<li>
<p>After merge all of the conflicts, you should be able to compile successfully:
<pre>
# suppose the absoulte path of lab-cse is /home/xx/lab-cse
% sudo docker run -it --privileged --cap-add=ALL -v /home/xx/lab-cse:/home/stu/devlop
ddnirvana/cselab_env:latest /bin/bash
% cd /home/stu/devlop
% make
</pre></p>
</li>
<li>
<p>Make sure there's no error in make.</p>
</li>
</ul>
</li>
<li>Note: Both 32-bit and 64-bit librpc are provided, so the lab should be architecture independent.</li>
<li>Note: For this lab, you will not have to worry about server failures or client failures. You also need not be concerned about malicious or buggy applications.</li>
<li>Note: Only files in the volume will be persistent, put all the files useful to the volume directory, in the above example: /home/stu/devlop directory.</li>
</ul>
<h2 id="distributed-filesystem-strawmans-approach">Distributed FileSystem (Strawman's Approach)</h2>
<ul>
<li>In lab1, we have implemented a file system on a single machine. In this lab, we just extend the single machine fils system to a distributed file system.</li>
<li>Separating extent service from yfs logic brings us a lot of advantages, such as no fate sharing with yfs client, high availability.</li>
<li>Luckily, most of your job has been done in the previous lab. You now can use extent service provided by extent_server through RPC in extent_client. Then a strawman distributed file system has been finished.</li>
<li><i>You had better test your code with the previous test suit before any progress.</i></li>
</ul>
<h2>Part 1</h2>
<ul>
<li>In lab 2, your aim is to extend it to a distributed file server. And in part 1, it now moves on to the RPC part.<ul>
<li><img src="lab2-part1.png"></li></ul>
<li>In principle, you can implement whatever design you like as long as it satisfies the requirements in the "Your Job" section and passes the testers. In practice, you should follow the detailed guidance below. <ul>
<li>Using the RPC system:<ul>
<li>The RPC library. In this lab, you don't need to care about the implementation of RPC mechanisms, rather you'll use the RPC system to make your local filesystem become a distributed filesystem.</li>
<li>A server uses the RPC library by creating an RPC server object (rpcs) listening on a port and registering various RPC handlers (see <code>main()</code> function in demo_server.cc).</li>
<li>A client creates a RPC client object (rpcc), asks for it to be connected to the demo_server's address and port, and invokes RPC calls (see demo_client.cc).</li>
<li><b>You can learn how to use the RPC system by studying the stat call implementation.</b> please note it's for illustration purpose only, you won't need to follow the implementation<ul>
<li>use <code>make rpcdemo</code> to build the RPC demo</li>
</ul>
</li>
<li>RPC handlers have a standard interface with one to six request arguments and a reply value implemented as a last reference argument. The handler also returns an integer status code; the convention is to return zero for success and to return positive numbers for various errors. If the RPC fails in the RPC library (e.g.timeouts), the RPC client gets a negative return value instead. The various reasons for RPC failures in the RPC library are defined in rpc.h under rpc_const.</li>
<li>The RPC system marshalls objects into a stream of bytes to transmit over the network and unmarshalls them at the other end. Beware: the RPC library does not check that the data in an arriving message have the expected type(s). If a client sends one type and the server is expecting a different type, something bad will happen. You should check that the client's RPC call function sends types that are the same as those expected by the corresponding server handler function.</li>
<li>The RPC library provides marshall/unmarshall methods for standard C++ objects such asstd::string, int, and char. <u>You should be able to complete this lab with existing marshall/unmarshall methods. </u></li>
</ul>
</li>
</ul>
</li>
</ul>
<h3>Test</h3>
<ul>
<li>To grade this part of lab, a test script <code>grade.sh</code> is provided. Here's a successful grading.
<pre>
% ./grade.sh
Passed A
Passed B
Passed C
Passed D
Passed E
Passed G (consistency)
Lab2 part 1 passed
......
</pre></li>
</ul>
<h2>Part 2</h2>
<ul>
<ul>
<li>In part 2, you will implement a locking service to coordinate updates to the file system structures.
Part 2 is further devided into two parts.
In <b>Part2A</b> you should implement a simple lock server.
Then in <b>Part2B</b> you will use the lock service to coordinate yfs clients.<ul>
<li><img src="http://imgur.qiniudn.com/Screenshot%20from%202014-03-29%2010:10:47.png" width="90%"></li>
<li>Reference: <a href="http://www.news.cs.nyu.edu/~jinyang/fa09/notes/ds-lec1.ppt">Distributed Systems (G22.3033-001, Fall 2009, NYU)</a></li>
</ul>
</li>
</ul>
<h2>Part 2A: Lock Server</h2>
<ul>
<li>We provide you with a skeleton RPC-based lock server, a lock client interface, a sample application that uses the lock client interface, and a tester. Now compile and start up the lock server, giving it a port number on which to listen to RPC requests. You'll need to choose a port number that other programs aren't using. For example:<ul>
<li><pre>
% make
% ./lock_server 3772
</pre></li>
<li>Now open a second terminal on the same machine and run lock_demo, giving it the port number on which the server is listening:</li>
<li><pre>
% ./lock_demo 3772
stat request from clt 1386312245
stat returned 0
%
</pre></li>
<li>lock_demo asks the server for the number of times a particular lock has been acquired, using the stat RPC that we have provided. In the skeleton code, this will always return 0. You can use it as an example of how to add RPCs. You don't need to fix stat to report the actual number of acquisitions of the given lock in this lab, but you may if you wish.</li>
</ul>
</li>
<li>The lock client skeleton does not do anything yet for the acquire and release operations; similarly, the lock server does not implement lock granting or releasing. Your job is to implement this functionality in the server, and to arrange for the client to send RPCs to the server.</li>
</ul>
<h3 id="your-job">Your Job</h3>
<ul>
<li>Your job is to implement a correct lock server assuming a perfect underlying network. Correctness means obeying this invariant: at any point in time, there is at most one client holding a lock with a given identifier.</li>
<li>We will use the program lock_tester to check the correctness invariant, i.e. whether the server grants each lock just once at any given time, under a variety of conditions. You run lock_tester with the same arguments as lock_demo. A successful run of lock_tester (with a correct lock server) will look like this:<ul>
<li><pre>
% ./lock_tester 3772
simple lock client
acquire a release a acquire a release a
acquire a acquire b release b release a
test2: client 0 acquire a release a
test2: client 2 acquire a release a
. . .
./lock_tester: passed all tests successfully
</pre></li>
</ul>
</li>
<li>If your lock server isn't correct, lock_tester will print an error message. For example, if lock_tester complains "error: server granted XXX twice", the problem is probably that lock_tester sent two simultaneous requests for the same lock, and the server granted both requests. A correct server would have granted the lock to just one client, waited for a release, and only then sent granted the lock to the second client.</li>
</ul>
<h3 id="detailed-guidance">Detailed Guidance</h3>
<ul>
<li>In principle, you can implement whatever design you like as long as it satisfies the requirements in the "Your Job" section and passes the testers. In practice, you should follow the detailed guidance below. <ul>
<li>Using the RPC system:
• A server uses the RPC library by creating an RPC server object (rpcs) listening on a port and registering various RPC handlers (see lock_smain.cc). A client creates a RPC client object (rpcc), asks for it to be connected to the lock_server's address and port, and invokes RPC calls (see lock_client.cc).<ul>
<li>Each RPC procedure is identified by a unique procedure number. We have defined the acquire and release RPC numbers you will need in lock_protocol.h. You must register handlers for these RPCs with the RPC server object (see lock_smain.cc).</li>
<li>You can learn how to use the RPC system by studying the stat call implementation in lock_client and lock_server. RPC handlers have a standard interface with one to six request arguments and a reply value implemented as a last reference argument. The handler also returns an integer status code; the convention is to return zero for success and to return positive numbers for various errors. If the RPC fails in the RPC library (e.g.timeouts), the RPC client gets a negative return value instead. The various reasons for RPC failures in the RPC library are defined in rpc.h under rpc_const.</li>
<li>The RPC system marshalls objects into a stream of bytes to transmit over the network and unmarshalls them at the other end. Beware: the RPC library does not check that the data in an arriving message have the expected type(s). If a client sends one type and the server is expecting a different type, something bad will happen. You should check that the client's RPC call function sends types that are the same as those expected by the corresponding server handler function.</li>
<li>The RPC library provides marshall/unmarshall methods for standard C++ objects such asstd::string, int, and char. <u>You should be able to complete this lab with existing marshall/unmarshall methods. </u></li>
</ul>
</li>
<li>Implementing the lock server:<ul>
<li>The lock server can manage many distinct locks. Each lock is identified by an integer of type lock_protocol::lockid_t. The set of locks is open-ended: if a client asks for a lock that the server has never seen before, the server should create the lock and grant it to the client. When multiple clients request the same lock, the lock server must grant the lock to one client at a time.</li>
<li>You will need to modify the lock server skeleton implementation in files lock_server.{cc,h} to accept acquire/release RPCs from the lock client, and to keep track of the state of the locks. Here is our suggested implementation plan.<ul>
<li>On the server, a lock can be in one of two states:<ul>
<li>free: no clients own the client</li>
<li>locked: some client owns the lock </li>
<li>The RPC handler for acquire should first check if the lock is locked, and if so, the handler should block until the lock is free. When the lock is free,acquire changes its state tolocked, then returns to the client, which indicates that the client now has the lock. The valuer returned by acquiredoesn't matter. The handler for release should change the lock state to free, and notify any threads that are waiting for the lock. Consider using the C++ STL (Standard Template Library) std::map class to hold the table of lock states.</li>
</ul>
</li>
<li>Implementing the lock client:<ul>
<li>The class lock_client is a client-side interface to the lock server (found in files lock_client.{cc,h}). The interface provides acquire() and release() functions that should send and receive RPCs. Multiple threads in the client program can use the same lock_client object and request the same lock. See lock_demo.cc for an example of how an application uses the interface. lock_client::acquire must not return until it has acquired the requested lock.</li>
</ul>
</li>
<li>Handling multi-thread concurrency:<ul>
<li>Both lock_client and lock_server's functions will be invoked by multiple threads concurrently. On the lock server side, the RPC library keeps a thread pool and invokes the RPC handler using one of the idle threads in the pool. On the lock client side, many different threads might also call lock_client's acquire() and release() functions concurrently.</li>
<li>You should use pthread mutexes to guard uses of data that is shared among threads. You should use pthread condition variables so that the lock server acquire handler can wait for a lock. The Lab Information contain a link to information about pthreads, mutexes, and condition variables. Threads should wait on a condition variable inside a loop that checks the boolean condition on which the thread is waiting. This protects the thread from spurious wake-ups from the pthread_cond_wait() and pthread_cond_timedwait() functions. </li>
<li>Use a simple mutex scheme: a single pthreads mutex for all of lock_server. You don't really need (for example) a mutex per lock, though such a setup can be made to work. Using "coarse-granularity" mutexes will simplify your code.</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
<h2 id="part-2-locking">Part 2B: Locking</h2>
<ul>
<li>Next, you are going to ensure the atomicity of file system operations when there are multiple yfs_client processes sharing a file system. Your current implementation does not handle concurrent operations correctly. For example, your yfs_client's create method probably reads the directory's contents from the extent server, makes some changes, and stores the new contents back to the extent server. Suppose two clients issue simultaneous CREATEs for different file names in the same directory via different yfs_client processes. Both yfs_client processes might fetch the old directory contents at the same time and each might insert the newly created file for its client and write back the new directory contents. Only one of the files would be present in the directory in the end. The correct answer, however, is for both files to exist. This is one of many potential races. Others exist: concurrent CREATE and UNLINK, concurrent MKDIR and UNLINK, concurrent WRITEs, etc.</li>
<li>You should eliminate YFS races by having yfs_client use your lock server's locks. For example, a yfs_client should acquire a lock on the directory before starting a CREATE, and only release the lock after finishing the write of the new information back to the extent server. If there are concurrent operations, the locks force one of the two operations to delay until the other one has completed. All yfs_clients must acquire locks from the same lock server.</li>
</ul>
<h3 id="your-job_1">Your Job</h3>
<ul>
<li>Your job is to add locking to yfs_client to ensure the correctness of concurrent operations. The testers for this part of the lab are test-lab2-part2-a and test-lab2-part2-b, source in test-lab2-part2-a.c and test-lab2-part2-b.c. The testers take two directories as arguments, issue concurrent operations in the two directories, and check that the results are consistent with the operations executing in some sequential order. Here's a successful execution of the testers:<ul>
<li><pre>
% ./start.sh
% ./test-lab2-part2-a ./yfs1 ./yfs2
Create then read: OK
Unlink: OK
Append: OK
Readdir: OK
Many sequential creates: OK
Write 20000 bytes: OK
Concurrent creates: OK
Concurrent creates of the same file: OK
Concurrent create/delete: OK
Concurrent creates, same file, same server: OK
test-lab2-part2-b: Passed all tests.
% ./stop.sh
</pre></li>
<li><pre>
% ./start.sh
% ./test-lab2-part2-b ./yfs1 ./yfs2
Create/delete in separate directories: tests completed OK
% ./stop.sh
</pre></li>
</ul>
</li>
<li>If you try this before you add locking, it should fail at "Concurrent creates" test in test-lab2-part1-a. If it fails before "Concurrent creates", your code may have bugs despite having passed previous testers; you should fix them before adding locks.</li>
</ul>
<h3 id="detailed-guidance_1">Detailed Guidance</h3>
<ul>
<li>What to lock? <ul>
<li>At one extreme you could have a single lock for the whole file system, so that operations never proceed in parallel. At the other extreme you could lock each entry in a directory, or each field in the attributes structure. Neither of these is a good idea! A single global lock prevents concurrency that would have been okay, for example CREATEs in different directories. Fine-grained locks have high overhead and make deadlock likely, since you often need to hold more than one fine-grained lock.</li>
<li>You should associate a lock with each inumber. Use the file or directory's inum as the name of the lock (i.e. pass the inum to acquire and release). The convention should be that any yfs_client operation should acquire the lock on the file or directory it uses, perform the operation, finish updating the extent server (if the operation has side-effects), and then release the lock on the inum. Be careful to release locks even for error returns from yfs_client operations.</li>
<li>You'll use your lock server from part 1. yfs_client should create and use a lock_client in the same way that it creates and uses its extent_client. </li>
<li><b>(Be warned! Do not use a block/offset based locking protocol! Many adopters of a block-id-as-lock ended up refactoring their code in labs later on.)</b></li>
</ul>
</li>
<li>Things to watch out for<ul>
<li>This is the first lab that creates files using two different YFS-mounted directories. If you were not careful in earlier labs, you may find that the components that assign inum for newly-created files and directories choose the same identifiers.</li>
<li>If your inode manager relies on pseudo-randomness to generate unique inode number, one possible way to fix this may be to seed the random number generator differently depending on the process's pid. The provided code has already done such seeding for you in the main function of fuse.cc.</li>
</ul>
</li>
</ul>
<h2>Grading</h2>
Finally, after you have implement all features above, run the grading script:
<pre>
% ./grade.sh
Passed part1 A
Passed part1 B
Passed part1 C
Passed part1 D
Passed part1 E
Passed part1 G (consistency)
Lab2 part 1 passed
Concurrent creates: OK
Concurrent creates of the same file: OK
Concurrent create/delete: OK
Concurrent creates, same file, same server: OK
Concurrent writes to different parts of same file: OK
Passed part2 A
Create/delete in separate directories: tests completed OK
Passed part2 B
Score: 120/120
</pre>
<h2 id="tips">Tips</h2>
<ul>
<li>This is also the first lab that writes null ('\0') characters to files. The std::string(char*)constructor treats '\0' as the end of the string, so if you use that constructor to hold file content or the written data, you will have trouble with this lab. Use the std::string(buf, size) constructor instead. Also, if you use C-style char[] carelessly you may run into trouble!</li>
<li>Do notice that a non RPC version may pass the tests, but RPC is checked against in actual grading. So please refrain yourself from doing so ;)</li>
</ul>
<h2 id="handin-procedure">Handin procedure</h2>
<ul>
<li>After all above done:
<pre>
% make handin
</pre></li>
<li>That should produce a file called lab2.tgz in the directory. Change the file name to your student id:
<pre>
% mv lab2.tgz lab2_[your student id].tgz
</pre></li>
<li>Then upload lab2_[your student id].tgz file to ftp://SJTU.Ticholas.Huang:public@public.sjtu.edu.cn/upload/cse/LAB2/ before the deadline. You are only given the permission to list and create new file, but no overwrite and read. So make sure your implementation has passed all the tests before final submit.</li>
<li>You will receive full credits if your software passes the same tests we gave you when we run your software on our machines.</li>
</ul>
</body></html>