From a4ccd3df2c9097a25340c54bc2acd072f872a0cd Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Sun, 9 Jul 2006 17:58:21 +0000 Subject: [PATCH] First stab at grading advice. --- ta-advice/HW1 | 470 +++++++++++++++++++++++++++++++++++++ ta-advice/README | 293 +++++++++++++++++++++++ ta-advice/check-duplicates | 72 ++++++ ta-advice/cleanup | 28 +++ ta-advice/hw1.txt | 129 ++++++++++ ta-advice/run-tests | 219 +++++++++++++++++ 6 files changed, 1211 insertions(+) create mode 100644 ta-advice/HW1 create mode 100644 ta-advice/README create mode 100755 ta-advice/check-duplicates create mode 100755 ta-advice/cleanup create mode 100644 ta-advice/hw1.txt create mode 100755 ta-advice/run-tests diff --git a/ta-advice/HW1 b/ta-advice/HW1 new file mode 100644 index 0000000..99b59e1 --- /dev/null +++ b/ta-advice/HW1 @@ -0,0 +1,470 @@ + PROJECT 1 GRADING ADVICE + ======================== + +This file contains advice for grading project 1. General advice for +Pintos grading is in README, which you should read first. + + ALARM CLOCK + =========== + +Most students solve this problem with a linked list of sleeping +threads and a timer interrupt handler that wakes up sleeping threads +at the appropriate time. Details that distinguish solutions include: + + - List ordering: Good solutions order the list of threads by + wake-up time. + + - Time left vs. wake-up time: Good solutions store the wake-up + time in the list, instead of the number of ticks remaining. + + - Interrupt efficiency: Good solutions that order the list by + wake-up time and store wake-up times (see above two items), + only need their timer interrupt to examine as many items in + the list as are actually waking up on this tick (plus one). + Otherwise, every sleeping thread must be examined (and + possibly modified). + + - Allocation: Good solutions put the fields needed for + sleeping in struct thread (or, possibly, in local + variables). Dynamic allocation is another possibility, but + malloc() failure must be dealt with; it is unacceptable to + busy-wait or fail to wait if malloc() fails. A third + possibility is a static array of list elements, but that + puts a fixed limit on the number of simultaneously sleeping + threads, which is also unacceptable. + + - Synchronization: Most solutions manipulate the list with + interrupts disabled to protect against the interrupt + handler. Other solutions are possible but most of them are + incorrect--watch out for missing memory barriers (see the + Memory Barriers section in the reference guide) or bad + assumptions of atomicity when there is none. + + In most solutions only the list insertion (typically a + single call to list_insert_ordered()) needs to be protected + by disabling interrupts. + + - Wake-up precision: Good solutions wake up sleeping threads + at exactly the tick they should (although the timer + interrupt might be processed a little late due to disabled + interrupts). Some solutions deal with synchronization by + delaying a wake-up that should occur during a call to + timer_sleep() until the following timer tick, which is + unacceptable. + + - Wake-one vs. wake-all: Good solutions wake up all the + threads that are scheduled to wake up at a particular timer + tick. Bad solutions only wake up one thread and delay + waking the next until the following timer tick. + +A1: + + Usually this includes a structure or, as in the sample solution, + new members in struct thread: + + /* Alarm clock. */ + int64_t wakeup_time; /* Time to wake this thread up. */ + struct list_elem timer_elem; /* Element in wait_list. */ + struct semaphore timer_sema; /* Semaphore. */ + + Typically there is a global list of sleeping threads also: + + /* Threads waiting in timer_sleep(). */ + static struct list wait_list; + +A2: + + Usually, timer_sleep() initializes a data structure (or struct + thread members) and, with interrupts disabled, inserts it in the + correct position on the global list. Then it goes to sleep by + downing a semaphore. + + On each tick, the timer interrupt handler checks the front of the + list. If it is ready to wake up, it pops it off the list, ups its + semaphore, and checks the next one. If it's not ready, then none + of the others can be ready, either, so it's done. + +A3: + + Ordering the list by time of wake-up and storing wake-up times + instead of ticks remaining, typically. (Some students don't + realize that the latter is an optimization, because it is so + obvious; that's fine, as long as they mention the first part.) + +A4: + + Typically only the global list itself is shared with other + threads, and the list elements are private, so that disabling + interrupts to insert into the list is sufficient. + + If the group introduces additional synchronization, such as a + semaphore, make sure that it is actually needed. + +A5: + + Typically, disabling interrupts around the list insertion protects + against races against the timer interrupt. + +A6: + + A good discussion will mention some of the features on the list of + distinguishing characteristics above. + + It is insufficient to compare against "solutions" that do not + satisfy the terms of the assignment, such as against the supplied + code that busy-waits. + + PRIORITY SCHEDULING + =================== + +Priority scheduling by itself is a simple exercise. Priority donation +is more difficult. Many groups do not seem to completely grasp the +structure of priority donation. Some properties of priority donation +that you may find useful while grading: + + - A thread can only directly donate its priority to at most + one donee thread at a time, because donation only occurs + when a thread is blocked waiting for a lock, and a thread + can only block waiting for a single lock at a time. + + This property means that each thread can keep track of its + donee, if any, with a single pointer in struct thread. + + - A thread can receive donations from any number of threads, + because any number of threads can wait on a lock. The + donors may be waiting for a single lock or multiple locks. + + These first two properties, taken together, mean that if a + thread keeps a "struct list" of its donor threads, a single + list_elem in "struct thread" in the donor is sufficient, + because the donor cannot be donating (directly) to more than + one thread. + + - Donations can nest to form a tree, but circularity is + impossible as long as no deadlock in the locking structure + exists. Deadlock would itself be a bug, so there is no need + to worry about circularity in donations. + +B1: + + The sample solution has essentially a minimal set of additions to + "struct thread": + + /* Scheduler data. */ + int priority; /* Priority, including donations. */ + int normal_priority; /* Priority, without donations. */ + struct list donors; /* Threads donating priority to us. */ + struct list_elem donor_elem; /* Element in donors list. */ + struct thread *donee; /* Thread we're donating to. */ + struct lock *want_lock; /* Lock we're waiting to acquire. */ + + The sample solution redefines the "priority" member to include + priority donations and adds a second "normal_priority" member that + does not include donations. An alternative might be to + recalculate the donated priority whenever it is needed, but this + is often, so a good rationale would be required. + + Some submissions omit the list of donors and attempt to record + pre-donation priority in the "struct lock" whose ownership causes + the donation. These submissions typically just restore the + original priority when the lock is released. But this is + insufficient. Consider a thread of priority 3 that owns locks A + and B and that receives a donation of priority 5 via A, then + priority 8 via B. If it releases A first, then its priority will + be restored to 3, even though it should be 5. Deduct points for + such an implementation. + + A common mistake is dynamically allocating the list of donations. + It is unacceptable to fail to maintain the required semantics if + malloc() fails. Failing to check malloc() for failure is also + unacceptable (see the OVERALL section). + + A global list of donations is not necessary. Deduct points if one + is present. + + Most solutions add an element to struct semaphore_elem also, used + in cond_signal() to find the highest-priority waiting thread to + signal: + struct thread *thread; /* Thread. */ + If the students don't mention such an addition, check whether they + made one. If so, deduct a few points for failing to mention it. + If not, read the answer to B3 carefully and make sure that they + actually handle condition variables properly. + +B2: + + The minimum ASCII art requirement here includes three threads and + two locks, e.g. for the sample solution: + + /--------------------------\ + | | + /------------------------\ | + Thread H V Thread M V | Thread L | + +-------------+ +-------------+ | +----------------+ | + |priority = 8 | |priority = 8 | | |priority = 8 | | + |norm_pri = 8 | |norm_pri = 5 | | |norm_pri = 3 | | + |donors = {} | |donors = {H} |-/ |donors = {M} |-/ + |donee = M |---->|donee = L |---->|donee = null | + |want_lock = A|--\ |want_lock = B|--\ |want_lock = null| + +-------------+ | +-------------+ | +----------------+ + ^ | ^ ^ | ^ + | Lock A V | | V Lock B | + | +-------------+ | | +-------------+ | + | |holder = M |-/ | |holder = L |-/ + | |waiters = {H}|-\ | |waiters = {M}|-\ + | +-------------+ | | +-------------+ | + | | | | + \------------------/ \------------------/ + + Some explanatory text must also be included. + +B3: + + The answer must describe what happens for each kind of + synchronization primitive. + + For semaphores, typically sema_up() selects the highest-priority + thread on the wait list, instead of the one that has been waiting + the longest. + + Locks are implemented in terms of semaphores so no extra work is + typically needed (but the submission must say this). + + Condition variables need the same kind of change as semaphores. + + One minor issue is the ordering of the ready_list and other lists + (such as semaphore lists) that keep track of threads waiting for + various events. It makes sense to maintain these in sorted order, + but threads' priorities can change while they waiting on lists, + which would require their positions to be adjusted (see the FAQ + for this problem). In practice it may be easier to simply search + the lists for maximum or minimum elements when required, as done + in the sample solution. + +B4: + + The expected answer is that lock_acquire() determines the holder + of the lock (lock->holder), if any, and then donate the current + thread's priority to it. The answer must mention how the priority + donation cascades through to nested donations. + + There is a race in lock_acquire() between checking for the lock's + holder and "down"ing the semaphore. The obvious way to fix this + is by disabling interrupts before checking the holder and keeping + them off until after sema_down() returns. You will check the code + for this by hand (see below). + +B5: + + The expected answer is that lock_release() returns the donations + to the threads waiting for the lock, releases the semaphore, and + recomputes the current thread's priority. + + Take a closer look if the answer says something about "restoring", + or similar, a previous priority instead of recomputing it. This + probably indicates that the implementation is buggy: it will fail + in the same way described in the last paragraph of B1 (above). + Deduct points for such an implementation. + +B6: + + The expected answer is that thread_set_priority() needs to + recompute the priority based on the highest donated priority and + the new base priority (see the FAQ for this problem for details). + However, the donated priorities can change during the computation + (e.g. a new donation can occur when another thread attempts to + take a lock owned by this thread). + + A lock cannot easily be used to avoid this race, because + lock_acquire() would need to take it before making a new + donation, and that would cause lock_acquire() to call itself. The + problem is probably solvable, but it is more straightforward to + simply disable interrupts. + + Sometimes students identify other races in this function. That is + acceptable, as long as it is a genuine race and they describe it + adequately. + +B7: + + The issue mentioned in the final paragraph of B3 above may come up + here. + +Check the submitted code, by hand, for the following: + + 1. When sema_up() unblocks a thread with a higher priority than the + running thread, it yields to it, but *not* if it unblocks a thread + with priority equal to or lower than the running thread. + + 2. When sema_up() does not unblock a thread, it does not yield. + + 3. Race condition between priority donation, which is probably + implemented in lock_acquire(), and "down"ing the underlying + semaphore, in sema_down(). This likely requires disabling + interrupts in lock_acquire(), as done in the sample solution. + + 4. Race condition between release of donated priorities, which is + probably implemented in lock_release(), and "up"ing the underlying + semaphore, in sema_up(). This likely requires disabling + interrupts in lock_release(), as done in the sample solution. + + ADVANCED SCHEDULER + ================== + +C1: + + Most groups create a list of all threads so that they can update + recent_cpu in all of them during a timer interrupt, e.g.: + + /* List of all threads. */ + static struct list all_threads_list; + + Some new "struct thread" members also make sense: + + int nice; /* Niceness. */ + fixed_point_t recent_cpu; /* Recent amount of CPU time. */ + struct list_elem all_elem; /* all_threads list element. */ + + Typically the load average is maintained as a global variable, + e.g.: + + static fixed_point_t load_avg; /* Load average. */ + + Most groups choose to abstract fixed-point numbers to some extent, + and so there is probably an associated type definition, e.g.: + + /* A fixed-point number. */ + typedef struct + { + int f; + } + fixed_point_t; + +C2 and C3: + + The first two rows are unambiguous and must be filled in just as + shown here: + + timer recent_cpu priority thread + ticks A B C A B C to run + ----- -- -- -- -- -- -- ------ + 0 0 0 0 63 61 59 A + 4 4 0 0 62 61 59 A + + From this point on, the answers will vary because A and B both + have equal priority (61) and there is no clearly stated rule on + which to choose. Some form of round-robin should be used, and on + C3 students must describe how they chose to do it. The following + answers give priority to the thread that has run least recently: + + 8 8 0 0 61 61 59 B + 12 8 4 0 61 60 59 A + 16 12 4 0 60 60 59 B + 20 12 8 0 60 59 59 C + 24 12 8 4 60 59 58 A + 28 16 8 4 59 59 58 B + 32 16 12 4 59 58 58 C + 36 16 12 8 59 58 57 A + + Don't feel obligated to check every entry. However, please do + "spot checks" on at least these rules of thumb: + + - Within each row, the recent_cpu values must sum to the + number of timer ticks. + + - Only one priority value changes from one row to the next, + decreasing by 1 for the thread that was chosen on the + previous row. + + - A runs more than B, which runs more than C. + + A few more notes: + + - It's possible there are more ambiguities than this one, but + that's the one that most students notice. + + - There is no need for non-integers or rounding in the table. + recent_cpu is only reduced based on load_avg every 100 + ticks, and the table is not that long. (It's possible that + some group could choose to reduce recent_cpu in some single + row on the assumption that the 100th tick happens there, but + no group has actually done that yet.) + +C4: + + This is the first quarter we've used this question, so I'm not + sure what kind of answers to expect. Please use your judgment in + grading answers. + +C5: + + Many groups comment on their choice between a single queue and an + array of 64 queues here. Good reasons for either choice include: + + - Scanning a 64-queue array may waste time if there aren't any + high-priority processes. (A good implementation could use a + bit vector to avoid scanning empty queues, but this may not + be obvious to students.) + + - A single queue has to be kept sorted, or it has to be + searched for the maximum-priority element, but there's no + such cost if there are 64 queues--we can just "push" and + "pop" at each end. + + - A single queue is more flexible if PRI_MIN or PRI_MAX is + changed, especially if PRI_MIN is changed to be nonzero or + if the range between PRI_MIN and PRI_MAX becomes much + larger. + + If they don't mention this choice, then they should talk about + some other important choice. + + Make sure that each group mentions in their answer at least one + advantage and one disadvantage of their design choices. + +C6: + + Generally the "right" answer here is that the group designed some + kind of abstraction for fixed-point math. If they didn't, then a + good justification is needed. + +Check the submitted code, by hand, for the following: + + 1. That the code that updates the load average, recent_cpu, and + thread priorities once per second is readable. It is probably in + thread_tick() in thread.c. Look at the code that uses the + fixed-point math, in particular, and try to figure out how it + implements the formulas for load_avg and updating recent_cpu. As + an example, the core of the code in the reference solution is + pretty straightforward: + + /* Update load average. */ + load_avg = fix_add (fix_mul (fix_frac (59, 60), load_avg), + fix_mul (fix_frac (1, 60), fix_int (ready_threads))); + + /* Update recent_cpu. First, calculate some constants: */ + fixed_point_t twice_load = fix_scale (load_avg, 2); + fixed_point_t twice_load_plus_1 = fix_add (twice_load, fix_int (1)); + fixed_point_t load_factor = fix_div (twice_load, twice_load_plus_1); + + /* Then, for each thread: */ + t->recent_cpu = fix_add (fix_mul (load_factor, t->recent_cpu), + fix_int (t->nice)); + + If you can't understand how their code does its calculations, take + off a lot of points. If you can't understand *easily*, take off a + few. + + 2. That the timer interrupt does *not* update every thread's priority + on every fourth timer tick. The 4.4BSD scheduler specification + says that priority is "recalculated once every fourth clock tick, + for every thread," but clearly the students should realize that + only the *running* thread's recent_cpu, and therefore priority, + will actually change. + + This code is probably also in thread_tick() in thread.c. + + 3. For a race condition in thread_get_recent_cpu() or + thread_get_load_avg(). Generally these need to be protected by + disabling interrupts, because they are updated in the timer + interrupt. A call to barrier() would be acceptable, too. diff --git a/ta-advice/README b/ta-advice/README new file mode 100644 index 0000000..9b68daf --- /dev/null +++ b/ta-advice/README @@ -0,0 +1,293 @@ + PINTOS GRADING ADVICE + ===================== + +This directory contains advice for TAs regarding Pintos grading. This +file contains overall advice for grading all the projects, and each +project has a file with additional, more specific advice for grading +that particular project. + +Be familiar with the Grading subsection within the Introduction +chapter in the Pintos manual. The principles stated there should +guide your grading decisions. You should also carefully read the +Coding Standards chapter and, of course, the assignments themselves. + +Grading is inherently subjective. The most important principle is to +be fair. Try to be patient with students, in the same way that you +would appreciate a TA being patient with you when you take classes +yourself. In my experience, this takes practice: many TAs tend to be +fairly impatient in their first quarter of TAing, and then improve in +their second quarter. I have noticed this pattern in myself and +others. + +Submission Structure +==================== + +At Stanford, each project submission puts files into a directory named +/usr/class/cs140/submissions/hw/, where is +the project number (between 1 and 4) and is the user name +of the team member who did the project submission. + +Each submission directory contains a tarball that actually contains +the submission. The tarball contains pintos/src and the files and +directories underneath it. If a student group submits more than once, +then there will be multiple tarballs, one for each submission. + +Each submission directory also contains a file named grade.txt that +describes the group, giving first and last name and email address for +each student. There is only a single copy of this file, regardless of +the number of submissions. + +If two different students from a single group both submit the project, +then you can end up with almost-identical submissions in two different +directories. It's best to check for this before beginning grading, to +avoid duplicating effort. The check-duplicates script in this +directory can help you with this (there should be a copy of it in +/usr/class/cs140/submissions). + +Grading Test Results +==================== + +Obtaining test results should be the easier half of the grading +process. The procedure for obtaining test results for one submitted +project is roughly this: + + 1. Extract the student code from its tarball into "pintos/src": + + tar xzf .tar.gz + + 2. Delete the existing pintos/src/tests directory and replace + it by a pristine copy: + + rm -rf pintos/src/tests + cp -R /usr/class/cs140/pintos/pintos/src/tests pintos/src/tests + + 3. Run "make clean" in the top-level directory, to get rid of + any binaries or objects mistakenly included in the + submission: + + (cd pintos/src && make clean) + + 4. Run "make grade" in the project-specific directory, + e.g. threads: + + (cd pintos/src/threads && make grade) + + 5. Make a copy of the "grade" file that this produces, which + is in the "build" directory. + + cp pintos/src/threads/build/grade tests.out + + 6. Compare the grade report that you produced against the one + submitted by the group. You can use "diff -u" or just + compare the final grades: + + diff -u tests.out pintos/src/threads/GRADE + + If there are major discrepancies (e.g. all their tests + passed, but all yours failed) then you should contact the + group. Otherwise, use the grade report that you produced. + + Grade reports can vary a number of reasons: QEMU is not + fully reproducible, Bochs sometimes has reproducibility + bugs, the compilers used on different machines may produce + code with different behavior, and so on. Finally, it's + possible that the group submitted a grade report that goes + with an earlier version of their code. + + 7. Run "make clean" in pintos/src again: + + (cd pintos/src && make clean) + + You don't have to do this immediately, but if you try to + grade too many projects without doing so, then you will + probably run out of quota. + + An alternative is to do the builds in temporary storage, + e.g. in /tmp. This will probably be a lot faster than + doing it in AFS, but it is slightly less convenient. + +There is a script called run-tests in this directory (and in +/usr/class/cs140/submissions) that can do most of this work for you. +Run "run-tests --help" for instructions. + +You can automate running the tests in several directories using a +command like (in the default C shell) + foreach d (*) + cd $d && run-tests threads + end +or in the Bourne shell: + for d in *; do cd $d && run-tests threads; done + +Grading Design +============== + +There are two parts to grading students' designs: their design +documents and their code. Both are lumped into a single grade, taken +out of 100 points. + +A suggested form to use for grading each project is in hw.txt in +this directory. You should copy this file into each submission +directory and delete the lines that do not apply. + +The subtractions for each kind of problem with a submission are +suggestions. You are free to modify them. You can also add your own +subtractions for problems that are not listed. + +When you add up the subtractions for a project, those for the OVERALL +section are not capped at any particular maximum. Those for +individual problems are capped at the value of the problem. + +IMPORTANT: Be critical in grading designs. Most submissions will pass +most of the tests, which means that they get almost 50% of the grade +for "free". When TAs only take off a few points in the design grade, +then total project scores can average 90% or even higher. This may +not sound like a bad thing, but it is, because students who receive +numerically high grades think that they did well relative to the other +students. At the end of the quarter when the curve is applied, these +students are then understandably disappointed or angry that their +final grades are so low when their intermediate grades seemed so high. +It is better to take off lots of points on projects and thereby give +students more realistic expectations about their final course grades. + +Grading Design Documents +------------------------ + +Be familiar with the Design Document subsection of the Introduction +chapter in the Pintos manual. + +Deduct all the points for a given question in these cases: + + - Missing: The question is not answered at all. + + - Non-responsive: The response does not actually answer what + is being asked. (If the question does not reasonably apply + to the solution chosen by the group, then the answer should + explain why it does not.) + + - Too long: e.g. a "25 words or less" response takes a whole + page. These qualifiers aim to save the group's time and + your time, so don't waste your time in these cases. + + - Too short: The response is evasive or excessively terse to + the point that you don't feel confident in the answer. + + - Grossly inaccurate: When you examine the code, you find that + it has no resemblance to the description. + + - Not implemented: The functionality described in the answer + was not implemented. This often happens when a group runs + out of time before implementing the entire project. Don't + give credit for a design without an implementation. + +Take off some points (use your judgment) for: + + - Capitalization, punctuation, spelling, or grammar: An + occasional mistake is tolerable, but repeated or frequent + errors should be penalized. Try to distinguish grammar + errors made by non-native speakers of English, which are + understandable, from those made by others, which are less + so. + + In Emacs, it is easy to check the spelling of a word: put + the cursor on or just after it, then type M-$. You can also + make it highlight misspelled words with M-x flyspell-buffer. + + - Minor inaccuracies: Some aspects of the code do not match + its description. + + - Conceptual errors: Statements, assumptions, or strong + implications made in the design document are incorrect, + e.g. assuming that unblocking a thread immediately schedules + it. + + - Partial response: Multiple questions are asked, but only + some of them are answered. + + - Excessive redundancy: The answer restates much of what is + specified in the assignment. + +Instructions for recurring questions: + + ---- DATA STRUCTURES ---- + + Copy here the declaration of each new or changed struct or + struct member, global or static variable, typedef, or + enumeration. Identify the purpose of each in 25 words or + less. + + - Deduct points if the required comment on each declaration is + missing. (The Introduction states "Add a brief comment on + every structure, structure member, global or static + variable, and function definition.") + + - Deduct points if the response does not describe *purpose*. + We can see the type and the name of each entity from their + declarations. But why are they needed? If the comments + themselves adequately explain purpose, then that is + sufficient. + + ---- RATIONALE ---- + + Why did you choose this design? In what ways is it superior to + another design you considered? + + - Deduct points for failing to compare their design to another + *correct* possibility. + +Grading Code +------------ + +You should start by quickly scanning all the submitted code by eye. +Usually the easiest way to do this is with a command like + diff -urpbN -X /usr/class/cs140/submissions/diff.ignore \ + /usr/class/cs140/pintos/pintos/src pintos/src | less +in a group's top-level directory. The options to "diff" here are +useful: + -u: produces a "unified" diff that is easier to read than the + default. + -r: recurses on directories. + -p: prints the name of the function in which each difference + lies. + -b: ignores differences in white space. + -N: includes added files in the diff. + -X .../diff.ignore: ignore files that match patterns listed in + diff.ignore, which lists files that you don't really want + to look at. You can add to the list when you notice files + that should be. + +You can page through the "diff" output fairly quickly, perhaps a few +seconds per page. Nevertheless, you should be able to notice some +important flaws: + + - Inconsistent style: indentation changing randomly between 4 + spaces and 8 spaces per level, between BSD and GNU brace + placement, and so on. (The Introduction states "In new + source files, adopt the existing Pintos style by preference, + but make your code self-consistent at the very least. There + should not be a patchwork of different styles that makes it + obvious that three different people wrote the code.") + + - Bad style: such as no indentation at all or cramming many statements + onto a single line. + + - Many very long source code lines (over 100 columns wide). + + - Lack of white space: consistent lack of spaces after commas + or around binary operators that makes code difficult to read. + + - Use of static or file scope ("global") variables instead of + automatic, block scope ("local") variables: one student + submission actually declared 12 (!) different global + variables "just so we don't have to make a new var in each + function". This is unacceptable. + + - Use of struct thread members instead of automatic, block + scope ("local") variables: sometimes it's not obvious + whether this is the case, but subtract points when it is. + + - Code copied into multiple places that should be abstracted + into a function. + + - Gratuitous use of dynamic allocation: e.g. a struct that + contains a pointer to a semaphore instead of a semaphore + itself. diff --git a/ta-advice/check-duplicates b/ta-advice/check-duplicates new file mode 100755 index 0000000..c0ae960 --- /dev/null +++ b/ta-advice/check-duplicates @@ -0,0 +1,72 @@ +#! /usr/bin/perl -w + +use strict; + +usage () if !@ARGV; +(print "$ARGV[0]: chdir: $!\n"), usage () if !chdir ($ARGV[0]); + +sub usage { + print <) { + last if /^\s*$/; + my ($student) = /\(([[:alnum:]]+)\@stanford.edu\)/ or next; + push (@students, $student); + } + close (GRADE); + + print "warning: no students in group $group\n" + if @students == 0; + print "warning: ", scalar (@students), " students in group $group\n" + if @students > 3; + + @students = sort @students; + for (my $i = 0; $i <= $#students; ) { + push (@{$stu2grp{$students[$i]}}, $group); + + my $j; + for ($j = $i + 1; $j <= $#students; $j++) { + last if $students[$i] ne $students[$j]; + } + + my ($reps) = $j - $i; + print "warning: $students[$i] appears $reps times in group $group\n" + if $reps > 1; + + $i = $j; + } + + print "warning: no student named $group in group $group\n" + if !grep ($_ eq $group, @students); + + $group_cnt++; +} + +for my $student (keys %stu2grp) { + my (@groups) = @{$stu2grp{$student}}; + next if @groups == 1; + print "warning: $student appears in groups ", join (', ', @groups), "\n"; +} +print "Scanned ", scalar (keys (%stu2grp)), + " unique students in $group_cnt groups.\n"; diff --git a/ta-advice/cleanup b/ta-advice/cleanup new file mode 100755 index 0000000..b24c179 --- /dev/null +++ b/ta-advice/cleanup @@ -0,0 +1,28 @@ +#! /usr/bin/perl -w + +use strict; + +usage () if !@ARGV; +(print "$ARGV[0]: chdir: $!\n"), usage () if !chdir ($ARGV[0]); + +sub usage { + print < 79 characters) + -10 Numerous capitalization, punctuation, spelling, or grammar errors + + DESIGN + -10 Failure to check return value of malloc() + -10 Use of ASSERT to check something that can actually fail, e.g. malloc() + + CODING STYLE + -10 Inconsistent or bad coding style: no indentation, cramming + many statements into one line, other issues at TA's discretion + -10 Numerous very long source code lines (> 100 characters) + -10 Commented-out or #if'd out code makes real code hard to read + -10 Many missing comments on structure, structure members, + global or static variables, or function definitions + -10 Function(s) should be decomposed for clarity [indicate function] + -10 Cut-and-pasted code should be made into function [indicate where] + -10 Uninformative or deceptive identifiers + +Subtotal: /10 (not capped) + +PROBLEM 1: ALARM CLOCK + + DOCUMENTATION + -30 Grossly inaccurate: documentation has no resemblance to code + -15 Important inaccuracies: documentation and code differ significantly + [indicate how] + -5 Minor inaccuracies: documentation and code differ [indicate how] + -5 A1: Missing entirely/missing comments or purpose/too long + -2 A1: Forgot to include some declarations [which] + -5 A2: Missing/non-responsive/too long/too short + -5 A3: Missing/non-responsive/too long/too short + -5 A4: Missing/non-responsive/too long/too short + -5 A5: Missing/non-responsive/too long/too short + -5 A6: Missing/non-responsive/too long/too short + -3 A6: "Straw man"--comparing correct design to an incorrect one + -10 Claim or implication that list operations are atomic + + DESIGN + -30 Not implemented + -10 Interrupt handler always examines or modifies every waiting thread + -5 Race between list modification and interrupt handler + -10 A timer tick that occurs during list modification delays waking + threads until the next timer tick + -10 Race between two threads modifying list + -10 Wakes only one thread even if multiple are finished sleeping + -15 Malfunctions (e.g. by busy waiting or not waiting the full time), + even in corner case (e.g. when malloc() returns NULL) + -15 Fixed limit on number of threads that may sleep + -5 Uses thread_block() instead of higher-level synchronization primitives + -5 Disables interrupts unnecessarily + -5 Unnecessary or redundant synchronization in timer_sleep() + +Subtotal: /30 (capped at 0) + +PROBLEM 2: PRIORITY SCHEDULING + + DOCUMENTATION + -30 Grossly inaccurate: documentation has no resemblance to code + -15 Important inaccuracies: documentation and code differ significantly + [indicate how] + -5 Minor inaccuracies: documentation and code differ [indicate how] + -5 B1: Missing entirely/missing comments or purpose/too long + -2 B1: Forgot to include some declarations [which] + -5 B2: Missing/non-responsive/too long/too short + -3 B2: Diagram is difficult to follow + -3 B2: Diagram is not specific to the chosen design + -3 B2: Didn't include explanatory text, just a diagram + -3 B2: Didn't include diagram, just explanatory text + -5 B3: Missing/non-responsive/too long/too short + -3 B3: Didn't explain semaphores + -3 B3: Didn't explain locks + -3 B3: Didn't explain condition variables + -5 B4: Missing/non-responsive/too long/too short + -5 B5: Missing/non-responsive/too long/too short + -5 B6: Missing/non-responsive/too long/too short + -5 B7: Missing/non-responsive/too long/too short + -3 B7: "Straw man"--comparing correct design to an incorrect one + + DESIGN + -30 Not implemented + -15 Malfunctions in corner case (e.g. when malloc() returns NULL) + -15 Fixed limit on total number of donations, donees, donor locks, etc. + -5 Global list of donations is unnecessary and inefficient + -3 sema_up() yields regardless of whether a higher-priority + thread was unblocked + -5 sema_up() yields even when it does not unblock a thread + -8 Race in lock_acquire() between priority donation and "down"ing sema + -8 Race in lock_release() between release of donated pri and "up"ing sema + +Subtotal: /30 (capped at 0) + +PROBLEM 3: ADVANCED SCHEDULER + + DOCUMENTATION + -30 Grossly inaccurate: documentation has no resemblance to code + -15 Important inaccuracies: documentation and code differ significantly + [indicate how] + -5 Minor inaccuracies: documentation and code differ [indicate how] + -5 C1: Missing entirely/missing comments or purpose/too long + -2 C1: Forgot to include some declarations [which] + -5 C2: Missing/non-responsive/too long/too short + -2 C2: Minor mistakes in table + -5 C2: Major mistakes in table + -5 C3: Missing/non-responsive/too long/too short + -5 C4: Missing/non-responsive/too long/too short + -5 C5: Missing/non-responsive/too long/too short + -3 C5: Did not mention advantage of submitted design + -3 C5: Did not mention disadvantage of submitted design + -5 C6: Missing/non-responsive/too long/too short + -5 C6: Did not properly justify failure to abstract fixed-point math + + DESIGN + -30 Not implemented + -10 Code to update load average, recent_cpu, and thread priorities + once per second is unreadable + -5 Code to update load average, recent_cpu, and thread priorities + once per second is difficult to read + -5 Wastefully recalculates every thread's priority every 4th timer tick + -5 Race against timer interrupt in thread_get_recent_cpu() + or thread_get_load_avg() + +Subtotal: /30 (capped at 0) diff --git a/ta-advice/run-tests b/ta-advice/run-tests new file mode 100755 index 0000000..74d1130 --- /dev/null +++ b/ta-advice/run-tests @@ -0,0 +1,219 @@ +#! /usr/bin/perl -w + +use strict; +use Getopt::Long; +use POSIX; + +our ($PINTOSDIR) = "/usr/class/cs140/pintos/pintos"; + +our ($verbose) = 0; +our ($start) = -d 'pintos/src' ? 4 : 1; +our ($stop) = 7; + +GetOptions ("v|verbose+" => \$verbose, + "h|help" => sub { usage (0) }, + "r|replace" => sub { + die "Can't start from step 2: pintos/src does not exist\n" + if ! -d 'pintos/src'; + $start = 2; + }, + "x|extract" => sub { $stop = 2 }, + "c|clean" => sub { $stop = 3 }, + "b|build" => sub { $stop = 4 }, + "t|test" => sub { $stop = 6 }) + or die "Malformed command line; use --help for help.\n"; + +die "Exactly one non-option argument required; use --help for help.\n" + if @ARGV != 1; + +my (@valid_projects) = ('threads', 'userprog', 'vm', 'filesys'); +my ($project) = $ARGV[0]; +$project = $valid_projects[$project - 1] if $project =~ /^[1234]$/; +die "Unknown project \"$project\"; use --help for help.\n" + if !grep ($_ eq $project, @valid_projects); + +sub usage { + my ($exitcode) = @_; + print < "extraction failed\n"); +} + +if (do_step (2)) { + print "Replacing tests with pristine copy...\n"; + xsystem ("rm -rf pintos/src/tests", + DIE => "removal of old tests failed\n"); + xsystem ("cp -pR $PINTOSDIR/src/tests pintos/src/tests", + DIE => "replacement of tests failed\n"); +} + +if (do_step (3)) { + print "Cleaning...\n"; + xsystem ("cd pintos/src && make clean", DIE => "clean failed"); +} + +if (do_step (4)) { + print "Building...\n"; + xsystem ("cd pintos/src/$project && make", DIE => "build failed"); +} + +if (do_step (5)) { + print "Grading...\n"; + xsystem ("cd pintos/src/$project && make grade", DIE => "grade failed"); +} + +if (do_step (6)) { + print "Saving grade report to tests.out...\n"; + xsystem ("cp pintos/src/$project/build/grade tests.out", + DIE => "copy failed"); +} + +if (do_step (7)) { + print "Cleaning...\n"; + xsystem ("cd pintos/src && make clean", DIE => "clean failed"); +} + +# do_step ($N) +# +# Returns true if step $N should be executed. +sub do_step { + my ($n) = @_; + return $n >= $start && $n <= $stop; +} + +# Returns the name of the tarball to extract. +sub choose_tarball { + my (@tarballs) + = grep (/^[a-z0-9]+\.[A-Za-z]+\.\d+\.\d+\.\d+\.\d+.\d+\.tar\.gz$/, + glob ("*.tar.gz")); + die "no pintos dir, no files matching username.MMM.DD.YY.hh.mm.ss.tar.gz\n" + if scalar (@tarballs) == 0; + + if (@tarballs > 1) { + # Sort tarballs in order by time. + @tarballs = sort { ext_mdyHMS ($a) cmp ext_mdyHMS ($b) } @tarballs; + + print "Multiple tarballs:\n"; + print "\t$_ submitted ", ext_mdyHMS ($_), "\n" foreach @tarballs; + print "Choosing $tarballs[$#tarballs]\n"; + } + return $tarballs[$#tarballs]; +} + +# Extract the date within a tarball name into a string that compares +# lexicographically in chronological order. +sub ext_mdyHMS { + my ($s) = @_; + my ($ms, $d, $y, $H, $M, $S) = + $s =~ /.([A-Za-z]+)\.(\d+)\.(\d+)\.(\d+)\.(\d+).(\d+)\.tar\.gz$/ + or die; + my ($m) = index ("janfebmaraprmayjunjulaugsepoctnovdec", lc $ms) / 3 + or die; + return sprintf "%02d-%02d-%02d %02d:%02d:%02d", $y, $m, $d, $H, $M, $S; +} + +sub xsystem { + my ($command, %options) = @_; + print "$command\n" if $verbose || $options{VERBOSE}; + + my ($log) = $options{LOG}; + + my ($pid, $status); + eval { + local $SIG{ALRM} = sub { die "alarm\n" }; + alarm $options{TIMEOUT} if defined $options{TIMEOUT}; + $pid = fork; + die "fork: $!\n" if !defined $pid; + if (!$pid) { + if (defined $log) { + open (STDOUT, ">output/$log.out"); + open (STDERR, ">output/$log.err"); + } + exec ($command); + exit (-1); + } + waitpid ($pid, 0); + $status = $?; + alarm 0; + }; + + my ($result); + if ($@) { + die unless $@ eq "alarm\n"; # propagate unexpected errors + my ($i); + for ($i = 0; $i < 10; $i++) { + kill ('SIGTERM', $pid); + sleep (1); + my ($retval) = waitpid ($pid, WNOHANG); + last if $retval == $pid || $retval == -1; + print "Timed out - Waiting for $pid to die" if $i == 0; + print "."; + } + print "\n" if $i; + $result = 'timeout'; + } else { + if (WIFSIGNALED ($status)) { + my ($signal) = WTERMSIG ($status); + die "Interrupted\n" if $signal == SIGINT; + print "Child terminated with signal $signal\n"; + } + + my ($exp_status) = !defined ($options{EXPECT}) ? 0 : $options{EXPECT}; + $result = WIFEXITED ($status) && WEXITSTATUS ($status) == $exp_status + ? "ok" : "error"; + } + + + if ($result eq 'error' && defined $options{DIE}) { + my ($msg) = $options{DIE}; + if (defined ($log)) { + chomp ($msg); + $msg .= "; see output/$log.err and output/$log.out for details\n"; + } + die $msg; + } elsif ($result ne 'error' && defined ($log)) { + unlink ("output/$log.err"); + } + + return $result; +} -- 2.30.2