3 * Bochs is not fully reproducible.
7 - In Project 2, we're missing tests that pass arguments to system calls
8 that span multiple pages, where some are mapped and some are not.
9 An implementation that only checks the first page, rather than all pages
10 that can be touched during a call to read()/write() passes all tests.
12 - In Project 2, we're missing a test that would fail if they assumed
13 that contiguous user-virtual addresses are laid out contiguously
14 in memory. The loading code should ensure that non-contiguous
15 physical pages are allocated for the data segment (at least.)
17 - Need some tests that test that illegal accesses lead to process
18 termination. I have written some, will add them. In P2, obviously,
19 this would require that the students break this functionality since
20 the page directory is initialized for them, still it would be good
23 - There does not appear to be a test that checks that they close all
24 fd's on exit. Idea: add statistics & self-diagnostics code to palloc.c
25 and malloc.c. Self-diagnostics code could be used for debugging.
26 The statistics code would report how much kernel memory is free.
27 Add a system call "get_kernel_memory_information". User programs
28 could engage in a variety of activities and notice leaks by checking
29 the kernel memory statistics.
33 From: "Godmar Back" <godmar@gmail.com>
34 Subject: priority donation tests
35 To: "Ben Pfaff" <blp@cs.stanford.edu>
36 Date: Fri, 3 Mar 2006 11:02:08 -0500
40 it seems the priority donation tests are somewhat incomplete and allow
41 incorrect implementations to pass with a perfect score.
43 We are seeing the following wrong implementations pass all tests:
45 - Implementations that assume locks are released in the opposite order
46 in which they're acquired. The students implement this by
47 popping/pushing on the donation list.
49 - Implementations that assume that the priority of a thread waiting on
50 a semaphore or condition variable cannot change between when the
51 thread was blocked and when it is unblocked. The students implement
52 this by doing an insert into an ordered list on block, rather than
53 picking the maximum thread on unblock.
55 Neither of these two cases is detected; do you currently check for
56 these mistakes manually?
58 I wrote a test that checks for the first case; it is here:
59 http://people.cs.vt.edu/~gback/pintos/priority-donate-multiple-2.patch
63 I also wrote a test case for the second scenario:
64 http://people.cs.vt.edu/~gback/pintos/priority-donate-sema.c
65 http://people.cs.vt.edu/~gback/pintos/priority-donate-sema.ck
67 I put the other tests up here:
68 http://people.cs.vt.edu/~gback/pintos/priority-donate-multiple2.c
69 http://people.cs.vt.edu/~gback/pintos/priority-donate-multiple2.ck
71 From: "Godmar Back" <godmar@gmail.com>
72 Subject: multiple threads waking up at same clock tick
73 To: "Ben Pfaff" <blp@cs.stanford.edu>
74 Date: Wed, 1 Mar 2006 08:14:47 -0500
76 Greg Benson points out another potential TODO item for P1.
81 The alarm tests do not test to see if multiple threads are woken up if
82 their timers have expired. That is, students can write a solution
83 that just wakes up the first thread on the sleep queue rather than
84 check for additional threads. Of course, the next thread will be
85 woken up on the next tick. Also, this might be hard to test.
88 Way to test this: (from Godmar Back)
90 Thread A with high priority spins until 'ticks' changes, then calls to
91 timer_sleep(X), Thread B with lower priority is then resumed, calls
92 set_priority to make its priority equal to that of thread A, then
93 calls timer_sleep(X), all of that before the next clock interrupt
96 On wakeup, each thread records wake-up time and calls yield
97 immediately, forcing the scheduler to switch to the other
98 equal-priority thread. Both wake-up times must be the same (and match
99 the planned wake-up time.)
102 I actually tested it and it's hard to pass with the current ips setting.
103 The bounds on how quickly a thread would need to be able to return after
104 sleep appear too tight. Need another idea.
106 From: "Godmar Back" <godmar@gmail.com>
108 For reasons I don't currently understand, some of our students seem
109 hesitant to include each thread in a second "all-threads" list and are
110 looking for ways to implement the advanced scheduler without one.
112 Currently, I believe, all tests for the mlfqs are such that all
113 threads are either ready or sleeping in timer_sleep(). This allows for
114 an incorrect implementation in which recent-cpu and priorities are
115 updated only for those threads that are on the alarm list or the ready
118 The todo item would be a test where a thread is blocked on a
119 semaphore, lock or condition variable and have its recent_cpu decay to
120 zero, and check that it's scheduled right after the unlock/up/signal.
122 From: "Godmar Back" <godmar@gmail.com>
123 Subject: set_priority & donation - a TODO item
124 To: "Ben Pfaff" <blp@cs.stanford.edu>
125 Date: Mon, 20 Feb 2006 22:20:26 -0500
129 it seems that there are currently no tests that check the proper
130 behavior of thread_set_priority() when called by a thread that is
131 running under priority donation. The proper behavior, I assume, is to
132 temporarily drop the donation if the set priority is higher, and to
133 reassume the donation should the thread subsequently set its own
134 priority again to a level that's lower than a still active donation.
138 From: Godmar Back <godmar@gmail.com>
139 Subject: project 4 question/comment regarding caching inode data
140 To: Ben Pfaff <blp@cs.stanford.edu>
141 Date: Sat, 14 Jan 2006 15:59:33 -0500
145 in section 6.3.3 in the P4 FAQ, you write:
147 "You can store a pointer to inode data in struct inode, if you want,"
149 Should you point out that if they indeed do that, they likely wouldn't
150 be able to support more than 64 open inodes systemwide at any given
153 (This seems like a rather strong limitation; do your current tests
154 open more than 64 files?
155 It would also point to an obvious way to make the projects harder by
156 specifically disallowing that inode data be locked in memory during
157 the entire time an inode is kept open.)
161 From: Godmar Back <godmar@gmail.com>
162 Subject: on caching in project 4
163 To: Ben Pfaff <blp@cs.stanford.edu>
164 Date: Mon, 9 Jan 2006 20:58:01 -0500
166 here's an idea for future semesters.
168 I'm in the middle of project 4, I've started by implementing a buffer
169 cache and plugging it into the existing filesystem. Along the way I
170 was wondering how we could test the cache.
172 Maybe one could adopt a similar testing strategy as in project 1 for
173 the MLQFS scheduler: add a function that reads "get_cache_accesses()"
174 and a function "get_cache_hits()". Then create a version of pintos
175 that creates access traces for a to-be-determined workload. Run an
176 off-line analysis that would determine how many hits a perfect cache
177 would have (MAX), and how much say an LRU strategy would give (MIN).
178 Then add a fudge factor to account for different index strategies and
179 test that the reported number of cache hits/accesses is within (MIN,
180 MAX) +/- fudge factor.
182 (As an aside - I am curious why you chose to use a clock-style
183 algorithm rather than the more straightforward LRU for your buffer
184 cache implementation in your sample solution. Is there a reason for
185 that? I was curious to see if it made a difference, so I implemented
186 LRU for your cache implementation and ran the test workload of project
187 4 and printed cache hits/accesses.
188 I found that for that workload, the clock-based algorithm performs
189 almost identical to LRU (within about 1%, but I ran nondeterministally
190 with QEMU). I then reduced the cache size to 32 blocks and found again
191 the same performance, which raises the suspicion that the test
192 workload might not force any cache replacement, so the eviction
193 strategy doesn't matter.)
195 Godmar Back <godmar@gmail.com> writes:
197 > in your sample solution to P4, dir_reopen does not take any locks when
198 > changing a directory's open_cnt. This looks like a race condition to
199 > me, considering that dir_reopen is called from execute_process without
200 > any filesystem locks held.
202 * Get rid of rox--causes more trouble than it's worth
204 * Reconsider command line arg style--confuses everyone.
206 * Finish writing tour.
208 * Introduce a "yield" system call to speed up the syn-* tests.
212 * Project 3 solution needs FS lock.
214 * Get rid of mmap syscall, add sbrk.
216 * Make backtrace program accept multiple object file arguments,
217 e.g. add -u option to allow backtracing user program also.
219 * page-linear, page-shuffle VM tests do not use enough memory to force
220 eviction. Should increase memory consumption.
222 * Add FS persistence test(s).
224 * process_death test needs improvement
228 * Improve automatic interpretation of exception messages.
232 - Mark read-only pages as actually read-only in the page table. Or,
233 since this was consistently rated as the easiest project by the
234 students, require them to do it.
236 - Don't provide per-process pagedir implementation but only
237 single-process implementation and require students to implement
238 the separation? This project was rated as the easiest after all.
239 Alternately we could just remove the synchronization on pid
240 selection and check that students fix it.
244 - Need a better way to measure performance improvement of buffer
245 cache. Some students reported that their system was slower with
246 cache--likely, Bochs doesn't simulate a disk with a realistic
251 - Add "Digging Deeper" sections that describe the nitty-gritty x86
252 details for the benefit of those interested.
254 - Add explanations of what "real" OSes do to give students some
261 . Low-level x86 stuff, like paged page tables.
263 . Specifics on how to implement sbrk, malloc.
267 . opendir/readdir/closedir
269 . everything needed for getcwd()
271 To add partition support:
273 - Find four partition types that are more or less unused and choose to
274 use them for Pintos. (This is implemented.)
276 - Bootloader reads partition tables of all BIOS devices to find the
277 first that has the "Pintos kernel" partition type. (This is
278 implemented.) Ideally the bootloader would make sure there is
279 exactly one such partition, but I didn't implement that yet.
281 - Bootloader reads kernel into memory at 1 MB using BIOS calls. (This
284 - Kernel arguments have to go into a separate sector because the
285 bootloader is otherwise too big to fit now? (I don't recall if I
286 did anything about this.)
288 - Kernel at boot also scans partition tables of all the disks it can
289 find to find the ones with the four Pintos partition types (perhaps
290 not all exist). After that, it makes them available to the rest of
291 the kernel (and doesn't allow access to other devices, for safety).
293 - "pintos" and "pintos-mkdisk" need to write a partition table to the
294 disks that they create. "pintos-mkdisk" will need to take a new
295 parameter specifying the type. (I might have partially implemented
296 this, don't remember.)
298 - "pintos" should insist on finding a partition header on disks handed
301 - Need some way for "pintos" to assemble multiple disks or partitions
302 into a single image that can be copied directly to a USB block
303 device. (I don't know whether I came up with a good solution yet or
304 not, or whether I implemented any of it.)
308 - Needs to be able to scan PCI bus for UHCI controller. (I
309 implemented this partially.)
311 - May want to be able to initialize USB controllers over CardBus
312 bridges. I don't know whether this requires additional work or if
313 it's useful enough to warrant extra work. (It's of special interest
314 for me because I have a laptop that only has USB via CardBus.)
316 - There are many protocol layers involved: SCSI over USB-Mass Storage
317 over USB over UHCI over PCI. (I may be forgetting one.) I don't
318 know yet whether it's best to separate the layers or to merge (some
319 of) them. I think that a simple and clean organization should be a
322 - VMware can likely be used for testing because it can expose host USB
323 devices as guest USB devices. This is safer and more convenient
324 than using real hardware for testing.
326 - Should test with a variety of USB keychain devices because there
327 seems to be wide variation among them, especially in the SCSI
328 protocols they support. Should try to use a "lowest-common
329 denominator" SCSI protocol if any such thing really exists.
331 - Might want to add a feature whereby kernel arguments can be given
332 interactively, rather than passed on-disk. Needs some though.