Syllabus
- Reading:
- Required reading:
- Recommended reading:
- Suggested reading:
- Other reading:
- Work:
- In this course we will write essays, enter into classroom
discussion and do a lot of
Hacking.
- For a syllabus, or near equivalent, see last
year's offering of the course, or the many
previous year's
offerings.
- Lateness: One week grace automatic; homeworks are generally scored
on a 0 to 5 scale; over one week late, one point off for each week late.
- Last day of class is TBA. I expect all work to be done by
that date.
- Computers:
- We will be working in various modes. I recommend strongly that
you have your own computer to work on. We will install Virtual Box and work on virtual
machines hosted by Virtual Box.
- We will also explore cloud computing using Amazon Web Services.
- If you do not have a computer of sufficient power to work comfortably with
Virtual Box, please we will discuss options.
- We will make extensive use of subversion, a source code control system.
You will turn in your assignments using subversion, and if you use subversion,
I and the TA can help you by examining and correcting your code, at any
time and from any location, when we are on-line.
- New media:
- There is a CSC521 topic on my blog.
It includes both my posts and as a sub-category
the grader's posts.
- You follow twitter.com/cs521. I
will keep it super-low traffic for the courtesy of those who want to enable SMS.
- Contact:
- The "lab instructor" is Nagin Arhami, n.arhami _at_ cs _dot_ miami _dot_ edu.
She is available to help with any topic in the course, but most likely
you will seek her aid for the practical problems that arise with Linux,
and with your C language problems.
- Office hours: I am available Friday, 1:30-3:30, and by appointment.
- Writing credit:
- Writing credit is offered. The student submits
three essays of length 1500 words each (not counting references section,
if any) on a subject related to computer
operating systems, technical, historical, or even market-business.
-
New: Recommended:
- Grants/Sponsorship:
-
Thanks to Amazon: for a grant under their AWS
for Education program, to explore cloud computing, and integrate cloud computing
concepts into the course.
Class notes
- Introduction
- Kernels
- Processes
- General remarks: (blog entry)
- Scheduling (blog entry)
- Other dispatched entities:
- Interrupts and exceptions
- APC/DPC, (Windows)
- Tasklets, Work queues (Linux)
- System class (Solaris)
- Soft interrupts (FreeBSD)
- Work loops (OS X)
- Priority inversion, priority boosting
- Synchronization
- Signals, time and timers.
- Interprocess Communication
- Memory
- Virtual memory system
- Kernel memory management
- Buddy System and contiguous page frames
- Slab
- User memory management
- Virtual Address Descriptors
- sbrk, malloc and the heap
- Linking and loading
- References
- File systems
- Blog posts:
- Disk technology
--- topics in green we did not get to
- Graphical Systems
- X windows
- Window managers
- OSX and compositors
- MS windowing, VNC and RDP
- Android windowing systems
- fonts and colors
- Cloud computing and virtual machines
- Software engineering
- Open source and proprietary
- Release engineering
- Updates and security
Pop quizes!
- Pop quiz 1:
svn update to get class/quiz/quiz1.txt; Copy it to
[your repo name]/quiz/quiz1.txt and edit it to add
your answers; commit it by class time of the due date.
Due: Monday, Sep 3.
- Pop quiz 2:
Due: Commit by 23:59 miami local time, Tuesday, Sep 11.
- Pop quiz 3:
Due: Commit by 23:59 miami local time, Thursday, Sep 20.
- Pop quiz 4:
Due: Commit by 23:59 miami local time, Thursday, Sep 27.
- Pop quiz 5:
Due: Commit before Wednesday's class, Oct 3.
- Pop quiz 6:
Due: Commit before Wednesday's class, Oct 10.
- Midterm:
Click here to take midterm-survey.
Due: Take survey before Wednesday's class, Oct 17.
- Pop quiz 7:
Due: Commit before Wednesday's class, Oct 31.
- Pop quiz 8:
Due: Commit before Wednesday's class, Nov 21.
- Pop quiz 9:
Due: Commit before Wednesday's class, Nov 28.
- Final:
Click here to take final-survey.
Due: Take survey before end of finals.
Assignments
- Project 0:
Due: Monday, Sept 3.
- Project 1:
- Install Virtual Box (or your choice of VM product);
- Install Ubuntu on Virtual Box, 32 bit 12.04 desktop is fine. Best be 32 bit in any case.
- Build a custom kernel. See these very
fine instructions.
- Read Love, chapters 1, 2, 5 and 18.
- Modify the kernel: insert a printk statement in the set_user_nice function. you will find this in kernel/sched.c;
rebuild, reboot, write a test function and test.
- To submit in a proj1 subdirectory of your subversion repo:
- A diff of your kernel changes
- A user test program, with makefile to build
- A target in the makefile to test, with a README.txt on how you tested your program.
Due: Monday, Sept 17.
- Project 2:
- Create the "hello kernel!" system call. The system call printk's "hello kernel". That's all it does.
- Although you could lenghten the syscall table, I'd just replace one of the empty slots in
the table. These are system calls that are-no-more.
- Add your code to implement the system call to a file (although you could create a new file, I'm
not sure exactly what build changes you would need make). My usual victim file to add to is
kernel/sched.c.
- in a proj2 directory, leave diffs of changes to kernel files, your test program, a
make for to build and test your project (the makefile is important!) and some
output that shows the test run of your program (just system logs showing "hello kernel!").
- The makefile is important. When you say "I tested my program", when any programmer says that,
it means "on this and that input my program did this and that thing and I think that was
what it was supposed to do". In a perfect world, there is a complete specification for the
notion of "correctly working" and your program will be ablaze with its essence when it achieves
this perfection. Not likely to happen in the real world. For the most part "correctly working"
is going to be defined by observed behavoir under various test cases. The makefile documents what were those
test cases.
Due: Monday, Sept 24.
- Project 3:
-
Read Love, chapters 3, 4, 6, 7, and 8.
-
Create the notnice system call, same as nice but it lets you raise your priority,
as well of lower it.
- Hint: Use the previous assignment to create a new system call.
- Hint: Use and modify existing code to write notnice.
Due: Monday, Oct 1.
- Project 4:
-
Read The little book of
Semaphores by Allen Downey (PDF),
chapters 1, 2 an about the first half of 3; chapter 4, Produced Consumer and Reader Writer.
- Read Love, chapters 9 and 10.
- Review the Java code in
A morality tale
- Write a reader-writer lock for the similar task as the symple sync example in Java.
- Note: you are going to have to build this out of Java synchronization. The Java lock
is manditory only.
- Hint: The advisory lock will have to pass through a synchronization block on its way into
and on its way out of a critical section, but it will not be synchronized in the middle. Many
readers can read.
- Hint: you will probably have to user wait/notify, for the writer threads.
- To install java on Ubuntu use:
apt-get install openjdk-6-jdk
- What is you don't know java? We will talk about this is class.
- Hints are available.
Due: Monday, Oct 15.
- Project 5:
- Implement a monitor in the Linux kernel.
- Use your monitors to implement a solution to Producers-Consumers problem.
- A further discussion of the project is found
here....
- There are (at least) 3 recommended steps to this project:
- You re-do the experiment as
as described.
For students that have not got SYSCALL to work, this provides an opportunity
to get that to work, so you can go back and resubmit prior homeworks.
- You should design a monitor from a semaphore. The difference between these
two is that a monitor implements notify/wait. My design uses two semaphores and
a counter. One semaphore is the critical section lock, the other gives something
that the waiting threads can queue on.
- Then implement your semaphore with kernel code and test it with user code.
Due: Monday, Oct 29.
- Project 6:
- This is practice with understanding the virtual address to physical address
mapping. You will be given a virtual address trace, a sequence of numbers in
a suitable range to imitate virtual addresses, and you will look up the page
frame in data structures you create and maintain. The result of the lookup is
make-believe a page frame, but it is actually just a number starting from 1000 and
counting by 1 for each page frame you need to allocate. If when looking up the
physical address you "fault" then you will allocate either one or two page frames
and write the number into the page tables.
- The input trace file is class/proj6/va_trace.txt. It is a list of virtual addresses.
- Your program will produce an output file pa_trace.txt, giving for each virtual
address in va_trace.txt the physical address that it maps to.
- Use the two-level mapping scheme exactly as 32 bit Linux - a single PDE table
with 1024 PDE's chosen by the high 10 bits of the VA, pointing to one of however many as
needed PTE tables, each PTE having 1024 PTE's chosen by the next 10 bits of the V.A.
- Your output will write +X where X is the page frame when you have to add a page frame;
and will write *X when X is the page frame when you already have it mapped.
- Also increment
when taking a frame for a PDE or PTE table. So our numbers agree exactly, increment
as soon as you need the PDE or PTE. Example: your first output will be +1002, because
page frame 1000 is the PDE table and page frame 1001 is the PTE table.
- As always, Makefiles for everything, with a clean target and a test target
which tests your program on known input, and a run target which runs it on the
test trace. You name and a date in everything as well.
- There is only one week for this project; the 1 week grace still applies but you
do have the FAT file system group project next.
Due: Monday, November 5.
- Project 7:
- For the seventh and last project, you will work in groups of not more than
four. Please form a group and give me the names in the group. I will open a
svn repo for the group with permissions for everyone in the group.
- Implement mini fat fuse
- Read:
- Love, chapters on Virtual File System and Block I/O.
- the FAT specifications: FAT Functional Specs
- Fuse on sourceforge.
- IBM
Article concerning FUSE. Warning: all documentation about FUSE is wrong.
- FUSE documentation from another source. Possibly no worse than any other source of misinformation.
- Harvey Mudd
- See class/proj7 for a head start on Fuse. Sync, run make, make run; see make install-fuse
if the compile complains of missing symbols.
- See class/proj7b for a head start on memory mapped IO.
Due: Nov 30.
References
- Inside the Mac OS X Chaos club
- Linux Boot
- Operating
Systems (wikipedia)
- Improvements
from Linux 2.4 to 2.6, at IBM Developerworks.
- LinuxChix:
hacking for grrls (sic).
- VBoxManage manual
- GDB manual
- Make manual
- Historical Perspective
- Operating system design philosopies and software engineering
- Schedulers
- Linking and loading
- Virtual Memory
- File systems
- EXT3, Journaling Filesystem by Dr. S. Tweedie
- ext3 Journaling File Sytems (ppt) Chadd Williams
- Linux NTFS
- FAT 16, visually, clark@hushmail
- Journaling the Linux ext2fs Filesystem, Stephen Tweedie
- How NTFS Works Microsoft Technet.
- Implementing CIFS by
Christopher Hertel
- CIFS by
Paul Leach and Dan Perry at MSDN.
- draft-leach-cifs-v1-spec-01.txt by Paul Leach. The standard before the Samba people reversed engineered it.
- Op Locks in SMB from MSDN.
- Common Internet File Systems Technical Reference from Storage
Networking Industry Association.
- Understanding NFS Michael Lucas at O'Reilly books.
- 8.3 Filename, and LFN to SFN algorithm, and directory layout (as of 15 Oct 08) Wikipedia.
- Design and Implementation of the Sun Network Filesystem, Sandberg et at.
- Use of NFS Considered Harmful, Shane Kerr.
- FreeBSD fs technologies:
softupdates, snapshots, and comparision to logging.
- Protection
- Graphical systems
- Cloud computing and virtual machines
