CMPS 111: Introduction to Operating Systems
Spring 2013

Prof. Scott A. Brandt

Computer Science Department
University of California, Santa Cruz

NEWS:

 

6/8/13 - The Final Exam is available on eCommons!!!

As discussed in class, we are having a take-home final. It is nominally due Monday at 10:00 pm, but because I won't look at them until at least late Wednesday evening, you may turn yours in any time before then and eCommons will be open until 11:55 pm on Wednesday.

I received a question about multi-level feedback queues, which are not adequately described in the book. Multi-level feedback queues are a preemptive scheduling algorithm designed to give preference to short jobs and I/O bound processes, while ensuring that all jobs eventually get CPU time.

Here's how they work: The system maintains a set of lists or queues, one per (finite) priority level. Jobs that just started or just unblocked go into the highest-priority list. The system always chooses to run a job from the highest non-empty priority list. A job that uses up its time quantum without finishing or blocking is put in the next lower level list (until it reaches the lowest priority list). A job that blocks and returns may be put in the next higher list.

The question on the exam asks how to implement this using priorities (and interrupts, but preferably without queues).

 

5/28/13 - Code for assignment 3 is now ready! OOPS!!! Please redownload mydisk.c. There was an off-by-one error that caused it to fail on some reads.

 

5/28/13 - The midterm with answers to Section II is available HERE

 

5/20/13 - Code for assignment 3 is now ready!

Here is the code:

  • mydisk.c contains my code for the disk I/O
  • The header file mydisk.h contains the structs and function prototypes for everying in mydisk.c. You must include this header file (and, of course, link with mydisk.c) to use these functions.
  • makedisk.c contains my code for creating a disk file.
  • testdisk.c contains my code for testing and using the disk I/O functions. Check it out. You can use this as the basis for your file system code.
  • Makefile contains my makefile for creating the programs, creating the disk, and even running my test code. Check it out. To build everything and run the test, you only have to type "Make run" or even just "Make" (since run is the first target). Note that my code SHOULD report an error at the end, as it tests seeking off the end of the disk.

The assignment is to:

  1. Write a format program that creates a superblock, a free block map, and an initial root directory for your disk. These functions should use a disk that has been created with makedisk and will have to use opendisk(), seekblock(), and writeblock() to format the disk.
    • Your superblock should include the size of the partition, the location of the free block map, the location of the root directory, and the start of the data blocks.
    • Your superblock and inodes can each be one block long. Your free block map may be larger.
    • Your free block map can be a bitmap with 0s for free blocks and 1s for allocated blocks. I would just include the superblock, root directory, and bitmap blocks in the bitmap. That will make the block numbers correspond to the blocks on your "disk".
  2. Write functions to read and write your root directory (writing a directory = creating a file).
    • Keep in mind that your files should have an inode, but your inodes may be very simple, containing
    • Your inodes can be very simple. They can be fixed size (1 block) and need only contain the size of the file and an array of direct block pointers (i.e., a list of block numbers for the blocks in the file).
  3. Write functions to read and write files on your disk.
    • It might be a good idea to start with 1 block files. Once you get them working, then make it possible for your files to be larger than 1 block.
    • A good way to test all of the above would be to create three small test programs: 1) A program that copies files from your Unix directory into your "disk" directory, 2) A program that lists the directory on your "disk", and 3) A program that reads a file from your "disk" and prints it out.
  4. To turn in: a tar file containing the above code and your test code that shows that it all works. Do NOT turn in .o files or executables. Just the source file and a makefile.
Here are some things you can do for extra credit, if you want to do more:
  1. Extra credit: Make it possible to delete files.
  2. Extra credit: Make it possible to have subdirectories.

 

5/6/13 - Sample code for assignment 2 is now (finally, finally, finally)ready! threads.c is my sample code that switches back and forth between two threads. Please note that this is only guaranteed to work on the UCSC Unix systems (unix.ucsc.edu). Your assignment is to:
1. Generalize this to work with more threads
2. Add a more intelligent scheduler
3. Make it preemptive by adding timer interrupts so the threads do not have to call thread_yield() to switch to another thread.  

5/2/13 - Two important notes. 1. The solutions to the homework problems are now posted in the resources section of the class ecommons site. 2. There are still stack problems with the thread code I provided. Think about the problem and play with setjmp and longjmp, but don't start on the assignment in earnest until I can provide you with working code. Just focus on the midterm for now. We'll come back to this next week.

 

4/29/13 - Sample midterm available HERE

 

4/17/13 - All homeworks and programming assignments are posted on ecommons!!! - As announced in class, all homeworks and programming assignemnts are posted on (and must be turned in via) ecommons. Do not look at this site for the assignments -- look on ecommons.

And because there have been so many problems with the ecommons due dates, I have set ecommons to accept homework submissions any time before finals. I still strongly recommend that you do them as we cover each chapter, but I will accept submissions any time that ecommons allows them.

The programming assignments will still have set due dates. I have changed ecommons to allow the first programming assignment to be submitted any time up to the April 28th.

 

4/9/13 - getline problem for Programming Assignment #1 - Some people reported a problem with the code I supplied for Assignment 1. I have fixed lex.c and myshell.c. They should work now.

 

4/7/13 - Some people reported problems submitting homework #1 - I just extended the due date by a day. Hopefully that will take care of the problem.

 

4/1/13 - Welcome - Welcome to CMPS 111 - Introduction to Operating Systems. I am in the process of updating the web pages. Please check this space frequently for late-breaking news and announcements.

 

Time: MWF 2-3:10
Location: Kresge 321
Instructor: Prof. Scott A. Brandt (scott@cs.ucsc.edu)
Office/Office Hours: E2-347B, Tuesdays 3-4, Thursdays 11-12
TA: Erik Steggal (esteggall@cs.ucsc.edu) Amita Misra (amitamisra@cs.ucsc.edu)
TA Office/Office Hours: TBD
Lab Hours (all in BE 105): M 4-6 & T 10-12 & W 11-1 & Th 12-2 & F 9-11
Prerequisites: CMPE 110
Required Text: Modern Operating Systems, Tanenbaum, 3rd Edition
Optional Text: The Design and Implementation of the 4.4 BSD Operating System, McKusick, et. al.
Course Web Page: http://www.cs.ucsc.edu/~sbrandt/111

Course Objectives

Fundamental principles of operating systems: process synchronization, processes, deadlocks, memory management, resource allocation, scheduling, storage systems.

Grading

  • There will be 9-10 mostly ungraded homework assignments (total: 10%)
  • There will be 3 programming assignments due every three weeks or so, each worth 10% of your grade (total: 40%).
  • There will be a midterm exam approximately halfway through the quarter worth 20% of your grade.
  • There will be a comprehensive final exam worth 30% of your grade.

    Overall grading will roughly follow a 90/80/70/60 scale, but I reserve to adjust the curve upward or downward as appropriate.

    Note: You must average above 50% on the assignments and on the exams in order to pass the class. Lower than 50% on either portion of the class will result in a failing grade regardless of the overall score. This is a necessary, but not sufficient condition for passing the class - averaging above 50% on each does not guarantee a passing grade.

    Homework

    Homeworks will be questions taken from the book and are intended to make sure that everyone is reading the book and to test understanding of the material from each chapter. Homeworks will be mostly ungraded (i.e., they will be checked for reasonableness).

    It is my experience that those people who do well on the homeworks do well on the exams, and those people who do not do well on the homeworks do poorly on the exams. You are therefore strongly encouraged to take the homework seriously and make every effort to answer all of the questions as completely and correctly as possible. Keep in mind that the homework problems listed are a relatively small subset of the problems in the book. If you want to do really well on the exams, I encourage you to do some or all of the other problems in the book and discuss the answers with others in the class.

    Programming Assignments

    The programming assignments are an important component of the course. If all goes as planned, you will be implementing a few components of an operating system kernel.

    We will use MINIX, a simple operating designed for educational purposes. You will run it in a VMware virtual machine on the computer of your choice.

    The programming assignments will be team projects with 3-4 team members. You may choose who you work with, but everyone must work as part of a team. All team members are expected to contribute in the design and implementation of each project.

    The programming assignments will be evaluated on several factors:
  • Documentation: The code must be well-commented and must include a design document describing your solution. Each file submitted must include a comment at the top with the names of all team members.
  • Correctness: The code must do what it is supposed to do.
  • Structure: The code should be broken into natural functions and modules.
  • Style: The code should be easy to read, well indented, well commented, and use clear, self-explanatory variable and function names.

    • The grade for each assignment will be based on your design (40%) and code (60%). Good design and documentation are absolutely crucial for this class because of the difficulty of the concepts.

    You may work on your programming assignments on any computer you wish, using VMware.

    Due dates and lateness:

  • Homeworks and programming assignments are due on the date and time specified.
  • Late homeworks and programming assignments will not be accepted except when due to documented emergencies.
  • Graded homeworks and programming assignments will be returned as soon as possible, usually within one week.

    Attendance

    Class attendance is mandatory. I will post homeworks, assignments, and important dates on the class web page, but this is provided as a courtesy and is not always complete. It is your fault if you miss something important because you skipped class.

    Lab attendance is also required. You will miss important material on the programming assignments if you do not attend. This is where the programming assignments will get discussed in detail.

    Office hours are optional. They are your chance to ask the professor and the TAs questions about the material being covered, the programming assignments, etc.

    Academic Honesty: Collaboration vs. Cheating

    This really should not be an issue, but recurring events have made the following necessary.

    You are encouraged to discuss the course material and concepts with other students in the class. However, all work that you submit must be your own. Under no circumstances may you look at anyone else's code or show anyone else your code, unless you are part of a project team. And while you may discuss the concepts used in the programming assignments with other groups, you may not discuss implementation details of the assignments themselves.

    If you are caught copying or otherwise turning in work that is not solely your own, you will fail the course and a letter will be sent to your Department, the School of Engineering, and to your Provost and academic preceptor.

    The bottom line is that you are expected to conduct yourself as a person of integrity - you are expected to adhere to the highest standards of academic integrity. This means that plagiarism1 in any form is completely unacceptable. As a (soon to be) computing professional, I encourage you to consult the code of ethics appropriate to your discipline2.

    Plagiarism will be assumed until disproved on work that is essentially the same as that of other students. This includes identically incorrect, off-the-wall, and highly unusual duplicate answers where the probability of a sheer coincidence is extremely unlikely. All parties to this unacceptable collaboration will receive the same treatment.

    You should bring a picture identification with you to all examinations and be prepared to show it upon request.

    If you are unsure of what is and is not allowed by this policy, talk to the instructor.

    1 pla-gia-rize vt. to steal and pass of as one's own (the ideas or words of another) to present as one's own an idea or product derived from an existing source - pla-gia-riz-er n. (source: Webster's New World Dictionary).
    2 The Association for Computing Machinery is http://www.acm.org/, the IEEE is http://www.ieee.org/ and the IEEE Computer Society is http://www.computer.org/.

    Getting Answers to your Questions

  • Attend class and labs
  • Check the class web page frequently - I will post as much information as I can
  • Read the class newsgroup: ucsc.class.cmps111
  • Meet with the professor and TAs during office hours
  • Email the professor and TAs
  • Do not drop by or call on the phone outside of office hours