CSE 121 Home Page

This is the class home page for CSE 121, Operating Systems Architecture and Implementation.

The initial handout is available in postscript [PDF]. Please make sure that you sign and hand in the class cheating policy page -- you will not receive a grade unless you do so.

The signal SIGXCPU is part of BSD4.4, just not well documented/known. See the file kern/kern_synch.c; the function mi_switch is responsible for posting the signal. See also table 4.4 in the text.

The TA for the course is Ankur Jain. His office hours are Mondays 12pm-1pm and Wednesdays 3pm-4pm in 3337A.

Final

Final Exam Grade Distribution

The statistics are: 

23 students handed in Final exam.

Final exam as a whole: mean  77.6522
                       stdev 11.0359

w/o late adjustment: mean  77.6522
                     stdev 11.0359

Excluding all-zero scores:

Final exam as a whole: mean  77.6522
                       stdev 11.0359

w/o late adjustment: mean  77.6522
                     stdev 11.0359

Per-problem statistics:

Num  1:  mean  1.173913
         stdev 0.760559
Num  2:  mean  3.434783
         stdev 1.096480
Num  3:  mean  4.043478
         stdev 1.232821
Num  4:  mean  2.565217
         stdev 1.884169
Num  5:  mean  2.826087
         stdev 0.636032
Num  6:  mean  1.913043
         stdev 1.059657
Num  7:  mean  4.173913
         stdev 1.403479
Num  8:  mean  2.565217
         stdev 0.770437
Num  9:  mean  2.739130
         stdev 0.673562
Num 10:  mean  2.782609
         stdev 0.507039
Num 11:  mean  2.739130
         stdev 0.605582
Num 12:  mean  2.434783
         stdev 0.876063
Num 13:  mean  2.521739
         stdev 0.650723
Num 14:  mean  2.565217
         stdev 0.770437
Num 15:  mean  3.000000
         stdev 1.285369
Num 16:  mean  5.565217
         stdev 1.056083
Num 17:  mean  5.869565
         stdev 0.447636
Num 18:  mean  4.043478
         stdev 1.232821
Num 19:  mean  5.652174
         stdev 0.865206
Num 20:  mean  4.217391
         stdev 2.518739
Num 21:  mean  4.434783
         stdev 2.446401
Num 22:  mean  4.652174
         stdev 1.709531
Num 23:  mean  1.739130
         stdev 1.451158


Per-problem statistics, omitting zero grades:

Num  1:  mean  1.500000
         stdev 0.500000
Num  2:  mean  3.434783
         stdev 1.096480
Num  3:  mean  4.227273
         stdev 0.901101
Num  4:  mean  3.933333
         stdev 0.249444
Num  5:  mean  2.954545
         stdev 0.208299
Num  6:  mean  2.000000
         stdev 1.000000
Num  7:  mean  4.363636
         stdev 1.109687
Num  8:  mean  2.681818
         stdev 0.554843
Num  9:  mean  2.863636
         stdev 0.343174
Num 10:  mean  2.782609
         stdev 0.507039
Num 11:  mean  2.739130
         stdev 0.605582
Num 12:  mean  2.666667
         stdev 0.471405
Num 13:  mean  2.521739
         stdev 0.650723
Num 14:  mean  2.681818
         stdev 0.554843
Num 15:  mean  3.000000
         stdev 1.285369
Num 16:  mean  5.565217
         stdev 1.056083
Num 17:  mean  5.869565
         stdev 0.447636
Num 18:  mean  4.227273
         stdev 0.901101
Num 19:  mean  5.652174
         stdev 0.865206
Num 20:  mean  5.388889
         stdev 1.339108
Num 21:  mean  5.368421
         stdev 1.494218
Num 22:  mean  4.863636
         stdev 1.423678
Num 23:  mean  2.352941
         stdev 1.185261

Homework / Projects

Use the ACS-provided turnin program to turn in your work. The default is that assignments are due before class, one week after the day on which I give them. Use the tar program to turn in multiple files.
  1. Due Oct 3. There are two questions that you must answer. You may either read through the BSD4.4 kernel sources and explain to me in detail how you determine the answers to following two questions, at the level of detail of which lines in which functions is doing what, or determine the answers experimentally by writing a test program and running it on a Solaris machine (e.g., an ACS uAPE machine). (The behavior of FreeBSD and Solaris should be identical on these questions.) If you do write a program, you must turn in the program as well as a writeup of why you think the program's output(s) answers the questions.
    1. Are pending alarm(2)s inherited across a fork(2)? I.e., if you set an alarm, fork before the alarm expires and delivers a SIGALRM signal, what happens? Is the signal delivered to both the parent and child processes? Neither? Only one? (if so, which?)
    2. Are posted but not delivered signals inherited across a fork(2)? I.e., if you mask the delivery of a signal via sigprocmask(2), post the signal -- either by invoking kill(2) directly or some other way -- fork, and then unblock the signal delivery in both the parent and child processes, will the signal be delivered to both the parent and child processes? Neither? Only one? (if so, which?)
  2. Due Oct 10. Do the following:
    1. Find out how sleep(3c) is implemented in FreeBSD's libc and whether / how it interacts with signals. This is operating system dependent and also libc version dependent.
    2. Find where in the FreeBSD kernel sources are file locking performed and what kernel data structure is used to record that an advisory lock (via flock [solaris] and via lockf [solaris]) has been placed on a file. Identify which kernel function(s) manipulate this data structure and explain what the function(s) do.
  3. Due Oct 19. Find out, based on reading the kernel sources, what happens to the virtual memory data structures when process A first maps in a file via mmap(2) [solaris] with MAP_PRIVATE, and then another process, B maps in the same file with MAP_SHARED. In your writeup, trace the evolution of the virtual memory data structures; describe which kernel functions are involved and what do they do in a step-by-step fashion. Also name the source files that contain these functions.

    Clarification (Oct 17): you should explain how the kernel virtual memory data structures would appear as a result of the above process execution. Since I did not specify when does process A or B access memory, you should explain what happens with the kernel's virtual memory data structures given all possible memory access patterns interleaved between and after the mmap(2) [solaris] operations.

  4. Due Nov 7. Take the pico thread library (in the public directory) and (1) add guard pages to the thread stacks so that an error occurs if a thread overflows its fixed-size stack, and (2) add a per-thread memory allocator which returns memory pages that is only accessible to the requesting thread. (The global memory allocator is still desirable to hold data that must be shared among the threads, but protecting thread-private data from access by other threads should reduce certain kinds of wild-pointer bugs.)

    The allocator entry points should have the type signatures: 

    void *pico_thread_malloc(size_t nbytes);
void pico_thread_free(void *);
    Your allocator doesn't have to implement a fancy allocation algorithm, but avoid obviously bad implementation choices. new!

    Your writeup should include a discussion of the design choices that you made as well as documentation of the additions and changes that you had to make to the pico library. Also discuss the cost of implementing stack guard pages and thread-private memory, the benefit(s) of having these features, and the trade off in performance, if any, that necessarily result from having these features even if the programmer doesn't take advantage of them, as well as the costs of using these features.

    You should also include the code that you wrote to test out your implementation, with descriptions that would permit the inclusion of the test code in a regression test suite. new!

    You should turn in a complete package: we should be able to just type in make and make test_progs to create all the binaries, without having to figure out if you've omitted some (unchanged) files. Do not include any generated (e.g., binary) files in the turn in. Include as many test programs as was necessary to convince you -- and your product group -- that your code works as specified. The feature specifications for this is pretty simple:

    1. On a stack overflow that hits a guard page (the requested stack size is a minimum size; the actual size may be larger), a SIGSEGV occurs.
    2. If a thread allocates memory via pico_thread_malloc and a non-NULL pointer is returned, all nbytes are usable; like malloc, the memory should be word aligned. pico_thread_malloc is supposed to be a drop-in replacement for malloc.
    3. If thread A allocated memory via pico_thread_malloc, then thread B should not be able to access that memory. Doing so will cause a SIGSEGV to be delivered.

    You are not required to use a fancy memory allocating algorithm: don't leak memory, but don't worry about memory fragmentation.

    The calculation for stack_top is wrong, and the function pico_this_thread() returns the wrong value on machines where the stack grows down (most machines). This functionality was never tested -- no test in the regression test suite uses pico_this_thread!

    Note that the global variable pico_cur_thread gives the same functionality without scanning the list of stacks. You probably noticed this variable being used when scanning through the code, since it is used throughout the pico thread package.

    The sources in the public directory has the bug fix for this and for the missing pico_thread_exit on_exit processing.

    The due date for this remains Nov 7 before class starts, but I will be accepting late turn ins until Nov 9 before class starts, with a penalty of 10% per day late.

  5. Due Nov 14. Given the IMMUTABLE and APPEND-ONLY flags prevent such files from being overwritten, determine whether the name space leading to the inode corresponding to the file can be altered, e.g., can the user rename an immutable file and put a different file in its place. (If this is possible, then a trojan horse program, e.g., a bogus /bin/login or some /sbin/ program, might still be installed. If you believe that the kernel checks for this case, find the procedures involved and in your writeup include a discussion of which lines of code are involved and what they do. If you believe that the kernel does not check for this, determine where such checks should go and discuss how to go about fixing this oversight.

Reading Assignments

  1. Sep 26. Read chapters 1 and 2. We are also making forays into chapters 3 and 4 during the lecture.
  2. Sep 28. Read chapters 3 and 4.
  3. Oct 3. Read chapter 5.
  4. Oct 13. Read chapter 6.
  5. Oct 31. Read chapter 7.
  6. Nov 9. Chapter 8 has been covered.
  7. Nov 16. Chapters 9 is being covered.

Lecture Summaries

  1. Lecture 1, Sep 21.
  2. Lecture 2, Sep 26.
  3. Lecture 3, Sep 28.
  4. Lecture 4, Oct 3.
  5. Lecture 5, Oct 5.
  6. Lecture 6, Oct 10.
  7. Lecture 7, Oct 12.
  8. Lecture 8, Oct 17.
  9. Lecture 9, Oct 19.
  10. Lecture 10, Oct 24.
  11. Lecture 11, Oct 26.
  12. Lecture 12, Oct 31.
  13. Midterm, Nov 2. The answer key is now available. The statistics are also available.
  14. Lecture 13, Nov 7.
  15. Lecture 14, Nov 9.
  16. Lecture 15, Nov 14.
  17. Lecture 16, Nov 16.

Reference Materials

Syllabus

The goal of this class is to gain in-depth knowledge about operating system implementations by studying one such implementation, the BSD4.4 operating system.

The following are the list of topics to be covered in this course. This is flexible and will change depending on your interests.

Misc

Occasionally I am contacted by head-hunters. The most recent is from a local network consulting company which is looking for people to serve as "Technical Support Specialists". Help desk type of stuff. Part time work. Let me know if you're interested.
[ search CSE | CSE home | bsy's home page | webster i/f | MRQE | google | yahoo | hotbot | lycos | altavista | pgp key svr ]
picture of bsy

bsy+cse121.f00@cs.ucsd.edu, last updated Sat Dec 9 18:39:41 PST 2000. Copyright 2000 Bennet Yee.
email bsy.

Don't make me hand over my privacy keys!