CMPS 111: Introduction to Operating Systems
Fall 2005

Prof. Scott A. Brandt

Computer Science Department
University of California, Santa Cruz

NEWS:

 

12/6/05 - A note on the final - Remember that if a question is incomplete or otherwise confusing you should make a reasonable assumption, state the assumption, and answer the question accordingly. For example, on question 12 where the exam refers to the FAT File system described in question 9, you may safely assume that it actually refers to the FAT File system in question 8.

12/5/05 -THE FINAL

The final exam is now posted here. It is due Tuesday, Dec. 6 at midnight. Please be sure to read everything before beginning. It has 12 short answer questions and no multiple choice. Good luck.

12/1/05 - Assignment #4 - Anyone who wants a little more time on assignment 4 may turn it in any time before Tuesday night (12/6/05). In other words, you may turn it in the same time as the final. However, after this, there will be no more extensions on anything.

11/29/05 - The final exam - By near-unanimous vote of the students attending class, it was decided that the final exam will be a take-home exam. It will be posted on the web site the morning of Monday, Dec. 5, and will be due Tuesday, Dec. 6, at midnight (via electronic submission).

11/25/05 - Assignment #4 - Our industrious TA tells me that there are lots of questions about the revised Assignment #4. I will try to clarify what is expected if you choose not to do the assignment in DLXOS.

As an alternative to the DLXOS assignment, you may write a virtual file system. Your file system should support seven commands:

  • vinit(char *diskname) - Initialize the file system inside a UNIX file called (i.e. whatever the program specifies).
  • int fd = vopen(char *filename) - Open the specified file.
  • int status = vclose(fd) - Close the specified file.
  • int status = vread(int fd, int n, char *buffer) - Read n bytes from the specified file and put them in the buffer (don't forget to have your program allocate a buffer of the appropriate size using malloc()).
  • int status = vwrite(int fd, int n, char *buffer) - Write n bytes from the buffer into the specified file.
  • int status = vseek(int fd, int offset) - Seek to the specified offset within the specified file.
  • vlist() - List all of the files in the directory. Your file system need only support a single directory. In other words, you are creating what is known as a flat file system. For simplicity, you may simply print them out to stdout, although that is not how a real file system would do it.

Your commands will not really be part of the operating system. They will simply be linked with any program that uses them. But from the perspective of a program using these commands they will appear to be no different from a system call.

Your virtual file system will save everything inside of a file on the UNIX system. You will use the file as a block storage device. Within that block storage device you will store a directory, a File Allocatation Table (FAT) (perhaps, although other mechanisms are fine), and the blocks of the files themselves.

A DOS style FAT table is a particularly easy way to represent the free and allocated space on your virtual disk. Your FAT will have one entry per block on your virtual disk (actually a file on the UNIX system). Read the section in the book on FATs for more information about how FATswork.

To use a UNIX file as a block storage device, you should write a simple block_read()/block_write() interface that reads and writes blocks to and from the block storage device (file). You will also have to initialize your "disk" before you can use it by creating the file and setting up an empty directory and an initialized FAT inside it.

Your file system need only support one open file at a time.

For extra credit you may implement hierarchical directories

 

10/26/05 - Assignment #2 - Because of the impending midterm, I am changing the due date of Assignment #2 to Sunday, Oct. 30.

 

10/10/05 - No office hours on Tuesday, 10/11/05 - They will be Wednesday from 2-3 instead.

 

9/26/05 - The broken links to lex.c and myshell.c are fixed.

 

9/22/05 - 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: TTh 12:00-1:45
Location: E2-194
Instructor: Prof. Scott A. Brandt (sbrandt@cs.ucsc.edu)
Office/Office Hours: E2-347B, TTh 2-3
TA: Tim Kaldewey (tkaldewe@ucsc.edu)
TA Office/Office Hours: TBD
Lab Hours: BE 105: M 5-7 & W 11-1
Prerequisites: CMPE 110
Required Text: Modern Operating Systems, Tanenbaum
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 ungraded homework assignments (but you must do at least 7 to pass the class)
  • There will be 4 programming assignments due every two or two and a half weeks, each worth 10% of your grade (total: 40%).
  • There will be a midterm exam approximately halfway through the quarter worth 25% of your grade.
  • There will be a comprehensive final exam worth 35% 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. Note: This is a necessary, but not sufficient condition for passing the class - averaging above 50% 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 ungraded, but you must do at least 7 to pass the class.

    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. Feel free to discuss these on the class newsgroup as well.

    Programming Assignments

    The programming assignments are an important component of the course. If all goes as planned, you will be implementing several components of an operating system kernel running atop a simulated DLX processor. While it would be ideal to work on an actual operating system, circumstances make that impractical (and an operating system, unlike a compiler, really is too complex to write our own from scratch).

    We will use DLXOS, a simple operating system that runs on a DLX processor (and has only 3000 lines of code, much of it documentation). There is a simulator that runs on Solaris and Linux, along with a C compiler targeted to this platform.

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

    • Your grade for each assignment will be based on your design (40%) and your 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. The tools (simulator, cross-compiler, assembler) are installed on the CATS instructional cluster (Solaris machines). In addition, the source code for the tools is available for copying to a personal machine. However, we can provide no assistance with installing the tools in your environment.

    One thing to remember: your assignments must work in the environment on the CATS system. DLX source code should be readily portable, but you should check your assignment on CATS before handing it in.

    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 true 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. And while you may discuss the concepts used in the programming assignments, 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

    Class Schedule

    This is a loose schedule for the class. This page lists all assignments, due dates, and reading material by date. This schedule is tentative, and will almost definitely be adjusted periodically to reflect how far we've gotten in class. In other words: This schedule is subject to change through the quarter. Assignment dates and due dates may be modified depending on the pace of the class.

    Day
    Date
    Topics
    Chapter
    Read before class
    		 Homework
    Th
    Sept. 22
    		Class Introduction
    Basic system calls used in shells
    1
    Chapter 1
    		  
    T
    Sept 27

    Operating Systems history, concepts, structure
    System calls
    1
     
    		  
    Th
    Sept 29
    		 Processes & threads
    2
    Chapter 2
    		 Homework 1
    T
    Oct.4
    		 Scheduling
    2
     
    		  
    Th
    Oct.6

    Interprocess communication (IPC)
    2
     
    		 Homework 2
    T
    Oct. 11
    		 Resource allocation
    3
    Chapter 3
    		  
    W
    Oct. 12
    		 Assignment 1 due
    Th
    Oct.13
    		 Deadlock detection and avoidance
    3
     

    Homework 3
    T
    Oct. 18
    		 Introduction to memory management
    Swapping
    4
    Chapter 4
    		  
    Th
    Oct. 20
    		 Memory management (cont.)
    4
     
    		 Homework 4
    T
    Oct.25
    		 Avoiding and preventing deadlock
    4
     
    		  
    W
    Oct.26
    		 Assignment 2 due
    Th
    Oct. 27
    		MIDTERM (in-class)
    T
    Nov. 1

    Virtual memory
    4
     
    Th
    Nov. 3
    		 I/O hardware & software principles
    I/O software layers
    5
    Chapter 5
    		 Homework 5
    T
    Nov.8
    		 Disk hardware
    Disk scheduling
    5
     
     
    Th
    Nov.10
    		 File systems
    6

    Chapter 6

    		 Homework 6
    T
    Nov. 15
    		File systems (cont.)
     6
     
    		  
    W
    Nov. 16
    		Assignment 3 due
    Th
    Nov. 17
    		 Security basics
    9
    Chapter 9 
    		 Homework 7
    T
    Nov. 22
    		 Authenticating users
    Attacks on computer systems
    9
     
    		  
    W
    Nov. 23
    		      Homework 8
    Th
    Nov. 24
    		 School Holiday (Thanksgiving)
    10
    Chapter 10
    T
    Nov. 29
    		 Unix: history, overview, processes
    10
    Chapter 10
    		  
    Th
    Dec. 1
    		Unix: history, overview, processes
    10
     
    		 Homework 9
    F
    Dec. 2
    Assignment 4 due
    M
    Dec. 5
    FINAL EXAM: 4:00-7:00 in E2-194 (the usual room)

    Telephone: (831) 459-5042 / FAX: (831) 459-4829 / sbrandt@cs.ucsc.edu