COP4610: Operating Systems & Concurrent Programming up↑

Study Guide

Spring 2015

Contents

  1. About This Study Guide
  2. Welcome
  3. Before Taking This Course
  4. Organizing Your Time
  5. The Instructors
  6. Communication
  7. The Course Website
  8. Programming Environment
  9. Syllabus
  10. The Honor Code & Plagiarism
  11. Programming Assignments
  12. Examinations
  13. Calendar

About This Study Guide

This document is provided as a supplement to the Syllabus. Suggestions on how this study guide might be improved are welcome.

Welcome

Welcome to COP 4610 Operating Systems & Concurrent Programming. The course is about two different things, which are closely related: (a) operating systems; (b) concurrent programming. Not entirely incidentally, this course is also about software architecture and intelligent use of data structures. You are likely to find the course to be demanding of time and effort, but making the effort to master this subject will pay off. You will learn many useful skills and techniques, and also some intellectually pleasing new concepts.

By this point in your studies you should already be somewhat familiar with operating systems. You have used at least two different operating systems, including one or more variants of Unix ( e.g. Sun Microsystem's Solaris, or the open source Linux) and one or more of the Microsoft Windows operating systems. You have used these operating systems as a programmer -- to write and debug programs -- and probably also as an ordinary user -- to read and send e-mail, play games, and to work with office applications like a word processor, spreadsheet, and database.

In this course you will study operating systems more thoroughly and at a deeper level. You should come out able to use an operating system better, and with sufficient understanding of the principles of operating system design and construction to be able teach yourself what you need to know about a new operating system whenever you encounter one in the future. The course is not intended to prepare you to write an operating system on your own, but when you come out you should know enough that you might be able to teach yourself the rest of what you need to do some productive hacking on the source code of an open-source operating system like Linux.

As you move through the course, which is mainly organized into units corresponding to areas of operating system functionality, it will be helpful if make an effort to look at each topic from at least the following three different views:

  1. The human user's view, e.g. from a shell command or GUI. This includes a number of abstractions, such as processes, files, and windows, that are visible to a human.
  2. An applications programmer's view. This includes the system or library calls that are made from a program to obtain services from the system. It also includes some more abstractions, such as Unix signals and open file descriptions, that are not visible to the end user, but are very important to an application program.
  3. An operating system builder's view. This includes the theory and design principles that guide the design of the operating system, as well as the modular breakdown, data structures, and algorithms that are used to implement it.

The programming exercises in this course should exercise and strengthen your general programming ability and your adeptness with the application of some specific data structures. Your readings will also expose you to other algorithms and data structuring techniques, used to solve problems that occur within the design of an operating system. You are likely to find, later, that you are able to apply those techniques to a variety of programming problems you encounter outside of operating systems. Similarly, you will find the internal software architecture and modular decompositions found in operating systems can be applied to the design and organization of other large software systems.

Probably the most challenging and interesting part of the course is concurrent programming. This is where you see a whole new dimension of programming. Up to this point in a computer science curriculum, most students will only have experience with single-threaded programs, that execute a single sequence of instructions, one after the other. In this course you will write programs that have more than one thread of control, in which several sequences of instructions executed in a parallel of interleaved fashion. A musical analogy is a person singing a single melody, versus a directing chorus singing many parts at once. A sports analogy is one person dribbling a basketball down a court alone, versus playing basketball with two full teams.

Concurrent programming is linked with operating systems in two ways:

  1. Operating systems provide tools and services to make it easier to write concurrent application programs.
  2. Operating systems are internally concurrent. They need to be, in order to manage all the different activities (multiple users) and devices (disk drives, tape drives, network interfaces, etc.) that are operating in parallel.

In this course you will encounter and learn to understand the use of concurrency in both of these contexts.

Distance Learning Courses & On-Campus Students

As explained in the syllabus, this document and other materials are for distance-learning-only sections of this course.

Besides not having to travel to Tallahassee, an advantage students in FSU's distance learning programs gain is flexibility. They are able, in effect, to carry their classrooms with them and enter them at any time, day or night. They are not required to attend any specific class meetings. Instead of taking their exams at a fixed time with the class they are allowed a window of time in which they can schedule taking the examination at an FSU-approved testing center. This flexibility allows the student to work around conflicts with other responsibilities, such as care of a family or employment. However, distance students do have deadlines for assignments and exams, the same as on-campus students. Moreover, distance learning courses impose some special demands on students.

To be successful as a distance student one needs to self-disciplined and an active learner. Too keep up with the assignments, and not be caught unprepared for the examinations, one must develop a work schedule and be productive within it. Where the on-campus student has specified meeting times with instructors and classmates, which serve as external prompts, the student in distance learning must discipline him/herself through internal prompts. In addition, a student in distance learning appreciates building and participating in an online community that, although designed to be asynchronous, demands thoughtful and regular attention. Experience has shown that students working at a distance benefit greatly from on-line interactions, using e-mail and the Blackboard/Campus discussion forums, with their fellow students as well as the instructors. Asking questions, trying to answer questions of your fellow students, and reading the answers (of both other students and the instructors) is a very important part of the distance learning process. When the dynamics of a distance learning group are good, these interactions can be both effective in teaching and satisfying on a personal level. For this to work it is important for you every student to take an active role, and not to sit back and wait for others to ask and answer the questions. A student with all of the above positive characteristics is likely to be successful, whether working on campus or at a distance.

Ideally, you should already have taken the prerequisite courses in distance mode. Given such experience, you should already be very familiar with the Blackboard (TM) system ( campus.fsu.edu) and the administrative details of study and submitting assignments at a distance. However, if this is your first distance-learning course in Computer Science at FSU you will need to spend extra time learning these skills, which are not specifically covered in the Web-based materials for this course. The following on-line resources are provided:

Before Taking This Course

The prerequisites for this course (COP 4530, CDA 3101, and their own prerequisites) imply a high level of computer programming skill and knowledge, including experience using the C++ or C language and the Unix operating system. In particular you will need to be able to do the following, not specifically taught in this course, to succeed:

Organizing Your Time

To succeed in this course you will need to organize and budget your time. Since individuals will start with different sets of prior knowledge and work at different speeds, no one can tell you exactly how long you will need to spend on each activity. It is not unusual for students to report spending 20 hrs per week, and some have reported spending more. You will have to find out what works for you.

The Instructional Staff

Instructor

The course has an instructor, who has overall responsibility for the course, and is the content expert and arbiter on matters of policy, including grading standards.

Mentor

The Mentor is responsible for grading programming assignments, and answering questions pertaining to the assignments.

Communication

As explained in the Syllabus, the primary channel for communication for students with the instructor, mentor, and other students in this course is the Blackboard Discussion Board for this course, which is organized into various forums related to topics. Please use this for all questions related to the course that are not of a personal nature, and whose answers may be of value to other members of the course. Examples of such questions include:

Open communication betweens student using the BlackBoard forums for this course is encouraged, even required. However, all work is individually graded, and there are no team projects or assignments in this course. For the sake of equity and fairness, it is essential that all student-to-student communications and instructor-student communications about the course, which might be of benefit to other students in learning, completing programming assignments and taking examinations, should be visible on an equal basis to all the students in the course. Therefore, private communications between students about the course, especially about programming assignments, is forbidden, and considered a violation of the Academic Honor Policy.

Please use direct e-mails to the instructor and mentor (only) for issues that would not be appropriate for sharing with other members of the course, such as a request for approval of excuses not being able to take an exam during the scheduled window, and questions or disputes about the how your specific quiz, project, or examination was graded.

The Course Website

The website for this course is http://www.cs.fsu.edu/~baker/opsys. This is maintained directly by the instructor for this course, in the Department of Computer Science. To get into some copyrighted material you may need to enter a userid and password, which will be provided to the class on the Campus/Blackboard course home page; that will be the same for everyone in the class, and will not be the same as your CS userid and password, or your Campus/Blackboard userid and password. You should explore the course website, and become adept at navigating among the different sections as soon as possible.

Syllabus

The course Syllabus summarizes what students should expect from the course and what the instructors will expect of students in the course. Some of the important topics covered include:

The Honor Code & Plagiarism

Most students are honest, have a well developed ethical sense, and don't need to be given detailed instructions on what is allowed and what is not. However, because of University policy and a few students who tried to excuse cheating by complaining that the rules were not stated clearly enough, it has become necessary to go into detail on this subject.

As stated in the Syllabus, you are required to read the FSU Academic Honor Policy and abide by it. The Academic Honor Code not only puts you on your honor not to cheat. It requires that you report any cheating that you observe. The purpose of this section of the Study Guide is to clarify what is allowed and what is not allowed with respect to the kind of cheating that gives us the most trouble in CS courses, i.e., plagiarism.

By turning in work for a grade in this course you are representing it as being entirely your own individual work. Unless otherwise specified in writing, all homework (including all programming assignments) is expected to be individual work. If any assignment permits teamwork, it will be explicitly stated so in the assignment, and then the work is required to be only the work of the people on the team.

You may well ask "What does `individual work' mean? Shouldn't I make sensible use of references and prior art?". When a person has a question or a problem it is normal to search publications (including the web) for information, ideas, and sometimes even code. However, there are intellectual property laws and academic ethics that restrict what you can do with the work of other people, and some still stronger restrictions on what you can do for programming assignments for this course. The following paragraphs are intended to explain these restrictions. These distinctions can sometimes appear to be fuzzy. If, after reading this section, you are still in doubt about whether something you are considering doing would be a violation of intellectual property law, academic standards, or the rules of the course, you should either refrain from doing it, or consult the instructor for a ruling. Likewise, if you are unsure whether something you have observed other students doing is allowed, please do not hesitate to consult the instructor.

All citizens, especially future writers and software development professionals, need to understand the basics of intellectual property law. Computer software is subject to both copyright and patent law. Copyright law protects the representation of a written work, whether it be a photograph, drawing, diagram, text, or computer code. Copyright law says that all such works start out as owned by the original author and cannot be copied legally without permission of the owner. If you have permission to copy, you generally required to give credit to the copyright holder and a note saying that the work is reproduced with her/his permission. There is an exception for copying small amounts of text without permission, if you identify such quotations and give credit to the author, under a vaguely defined principle called "fair use". Patent law protects the ideas behind a work. It restricts what you can do with ideas you get from other people. If an idea is patented, you cannot use it at all without a license.

Unfortunately, simple statements about law -- like the ones above -- always turn out to be oversimplifications. That is the nature of the legal system. The laws are complex and are continually being modified by the actions of legislatures and courts. Every lawyer I've ever asked for legal advice has ended by saying he cannot predict the outcome if a case comes to trial, since the ultimate decisions are in the hands of the specific judge or jury. So, what should a person do? Do your best to gradually become better informed of the law, by reading one or more of several tutorial's on the Web. Then, exercise conservative judgment. If you are in doubt about whether what you are about to do would be a violation of intellectual property law, you should either refrain from doing it, or consult a lawyer to get clarification.

Scholarly ethics start with the law, and go further. Academic ethics require that if you use information or ideas obtained from the work of another person you must at least give proper credit to the original author, identifying what you have used, where you obtained it, and who is the person to whom credit is due. Failure to give proper credit or properly indicate uses of someone else's work is plagiarism. Giving credit means citing the source of the information in the body of the paper (or program) at the point where it is used, and then including a full citation for the source in a list of references at the end of the paper (or program). Further, if any material -- and this includes diagrams and computer code, as well as text -- is used verbatim, it must be clearly identified as quoted text and include a citation of the original source. You must use quote-marks around each section of quoted text in a paper (and special delimiting comments for code), with a number or abbreviation for the in-line citation, referring to an entry in a list of the full citations at the end of the document. For a more detailed explanation of plagiarism, look at one or more of the tutorials posted by the FSU Library, at http://guides.lib.fsu.edu/plagiarism.

In the context of this course --- because programming assignments are used to assess what you have learned, and because even a few lines of code may represent a great deal of creative thought --- you are held to a higher standard for originality and independence of programming assignments than you may have found for the work in some other courses.

Failure to follow these rules will be considered a violation of the Academic Honor Code.The first detected violation will result in a grade of "F" or zero for the work in question. A second detected violation will result in a grade of "F" for the course, with no possibility of taking the course for grade forgiveness.

The instructor may use the services of turnitin.com or other electronic automated techniques to assist in enforcing these rules.

Programming Assignments

As mentioned in the Syllabus, there will be several individual programming assignments. The Grading section of the Syllabus tells how the programming assignment grades will be weighted in the computation of the term grade, and the course Calendar gives the deadlines for all the assignments, along with links to details on each assignment. This section of the Study Guide provides other information and advice regarding those assignments.

Grading Criteria for Programming Assignments

Programs grades will be assigned according to the following general guidelines, unless specified differently in the instructions for the specific assignment.

[0-59]
program not turned in, appears copied, or too incomplete to determine whether principles behind the assignment were understood
[60-69]
program turned in and indicates some understanding of principles behind assignment, but does not work correctly on public test data/cases supplied by the instructor
[70-79]
program works correctly on public test data/cases, is based on correct algorithms, and shows understanding of most of the principles behind the assignment
[80-89]
program works correctly on public test data and also on other data that may be used by the instructor in grading, and indicates understanding of all the principles behind the assignment
[90-100]
program is correct and is also well written, in an economical clear style. (This includes use of efficient algorithms and data structures, and adequate documentation explaining the data structures used and the effect of each subprogram in terms of its parameters and any global variables it uses.)

Within these bands, the grade will depend on matters such as style and documentation. Programs that go beyond the minimum requirements in some respect may occasionally be forgiven a few errors without lowering of the grade, but students are cautioned against writing overly ambitious programs, since this grading scheme is harsh on non-working programs.

In other words: Most of the grade will be determined by how your code performs on tests. The tests will include both normal use cases and cases of detectable error conditions. They will not only test that the code works correctly under simple normal usage conditions, but they will attempt to stress your implementation. Solutions that work correctly on normal use cases will be eligible for a grade of "C". For grades in the range "B" through "A", a higher standard will be applied. Most detectable error conditions should be detected and handled correctly. (Correctness here means following the specifications in the assignment, or if nothing is specified in the assignment, exercising sound judgement as to what would be most useful, least surprising, and least harmful). The implementation should not be inefficient, either in terms of the amount of execution time it takes, or the amount of object code. (Here, we only interested in inefficiencies that make significant differences in execution time or object code size.)

More specific guidelines may be provided for individual assignments. In some cases, there may be optional parts that must be completed to earn a higher grade.

Submitting Assignments

Programming assignments must be submitted electronically. Each assignment will specify any details about how it is to be turned in that are specific to that assignment. The instructions here cover just the principles that apply to all assignments. The details in the specific assignment always take precedence over anything that is stated here.

If an assignment calls for you to use a shell script to submit your work, take care of the following:

Make your Own Backups:We will try to arrange for the submission mechanism to provide a positive confirmation of receipt. However, students are responsible for retaining electronic back-up copies of all work that is turned in, in case network or equipment failure causes loss of the copy that was turned in. Regardless of how an assignment is submitted, before you submit it you should always save a copy of your work to the hard drive of your personal computer. You will then have a backup copy of your work should your assignment be lost or scrambled during the electronic submission process. While you are working on the project, it is advisable to use a revision control tool, such as RCS, CVS, SVN, or gimp to keep track of your changes, in case you want to back up to an earlier version.

How to Work on Programming Assignments

*Apply the above in an incremental way. Implement functionality in stages, testing at each stage to verify that what you have written is correct (modulo interactions with code not yet written) before going on. It is much easier to isolate and correct errors in smaller pieces of code than in a large and complex system, especially when there are multiple errors interacting with and potentially masking or distorting the effects of one another. This typically requires writing some tests that exercise internal functions of your code that would otherwise not be called directly from outside.

Programming Environment

You will need a CS Department computer account for this course. This allows you to send and receive e-mail at a cs.fsu.edu address, and to log in using ssh to the programming servers used for this course. If you are registered for this course and do not already have a CS account, you can obtain this login on line, by following instructions at https://system.cs.fsu.edu/index.php/newusers/newaccount.

The assignments for this course will generally be expected to be able to compile and run correctly on both of the following two programming environments:

No matter which of the above systems you log into, you will be able to access your home directory, which contains all of your files. That is because your home directory is stored on a network fileserver, which serves all of the above machines, as well as most of the other machines in the CS teaching labs.

The above machines cannot receive or send e-mail, or access the fileserver that contains your CS homepage. They are just for coding, testing, and debugging programs.

Those are the only machines in the CS Department you are allowed to use for testing programs for this course. If you choose to read your e-mail using your cs.fsu.edu address, you can read it on shell.cs.fsu.edu. If you choose to maintain a web page as cs.fsu.edu you will log into ww2.cs.fsu.eduto maintain your web pages.

Since some of the system calls you will be making, and the network traffic you may be generating, can cause denial of service to other users of the system, you should never test programs for this course on those e-mail and web server machines. If you do, and your program behaves (even accidentally) in a way that denies service to other users, your computer usage privileges may be suspended, which in turn may case you to miss deadlines for assignments and cause your grades to suffer. This is serious. The kinds of programs you will write for this course, if they have bugs in them, can easily cause a system to hang or crash. That is why the department provides pools of computers for student programming, to minimize the risk of one student locking out everyone.

If you think your program or that of another student has caused one of the Program or Linprog pools to hang: First, if it is your own program that has run amok try to kill your runaway processes using the kill shell command (will be explained further in class and notes). Then, if that does not work, or the problem is with another person's program, or you simply cannot connect to the machine, please notify the System Support Group of the problem so that they can perform a reboot operation.

For questions and assistance related to the CS Department computing facilities, including new account and password problems, and reporting any malfunction of the computers, printers, or network managed by the department, contact the CS Systems Support Group. If the system is working well enough to use the Web, use the Helpdesk on-line problem reporting service. Otherwise, you can call the system group at 644-4019.

Please do not ask the Systems Support Group for help doing the assignments for this course. That is not their job, and they will not be familiar with the specifics of the assignments. Questions related to the content and assignments for this course should only be addressed the instructor or TA for the course.

Of course, you may also use computers outside the CS Department to write and debug your software. If you have a Linux system of your own maywork fine for initial development. You may also be able to do some of the preliminary programming on an Apple system running Mac OS X, which is Unix-based, if you have installed Xcode along with MacPorts or one of the other open source Unix development environments.

In any case, before you turn in an assignment you are responsible for checking that it will run correctly on the system or systems specified for that assignment. Students who chose to start development on their own systems in previous terms discovered that it took them longer to iron out system differences than they expected. In some cases they ended up turning in programs that earned failing grades because they would not compile or would not run on the system where they were tested by the grader. Making sure the assignment is debugged on the right system is the student's responsibility. "It compiled and ran fine on my system!" is not an acceptable excuse.

Portabiity & Coding Standards

In this course we will emphasize portability, security, and readability in coding. Portability is achieved through adherence to widely supported standards, and avoiding dependence on implementation-specific features of the execution platform, compiler, libraries, and operating system. Security is achieved through defensive design, including adherence to safe coding standards. Readability is achieved through a combination of techniques, including a consistent style of coding, approprite indentation and use of whitespace, good choice of identifiers, and explanatory documentation for information not immediately apparent from the code.

Another important consideration is inter-operability between software components written by different authors. This requires adherence to well designed and documented interfaces between components, as well as consistency of style across the individuals working on any given component. While you will be working only as individuals on your course assignments, in many cases you will be modifying exiting code modules, interfacing to provided code modules, or implementing or using interfaces defined in header files that are provided to you.

Code modules that you write may be tested by linking them with other modules and test programs designed by the instructor. The interface to such modules will generally be defined in a C header ( .h) file. There will be instructions not to modify this header file, or comments indicating limitations on what may be modified. Adhere to these constraints, or risk your module failing to compile or failing to run correctly when it is tested for grading.

For the above reasons, you will be expected to honor the following rules, and should expec a reduction in your score on an assignment of you fail to adhere to them:

  1. Shell scripts must be written for the standard POSIX Bourne shell (/bin/sh).
  2. Makefiles should only use features of the standard POSIX make.
  3. Program code must be written in the C language.
  4. Files turned in for assignments should be plain text files, in 8-bit ASCII or UTF-8 encoding, with no non-printing characters other than blank and newline, and with newlines encoded as line-feeds (LF, a.k. Ctrl-J). If an assignment specifies the name of a file, you must use exactly that name; if the name is not specified in the assignment, you may choose the filename subject to standard C naming conventions (".h" for header/interface files and ".c" for implementation code files).
  5. Programs must compile with the gcc compiler (no g++), using the compiler flags and feature-test macros specified for the assignment. For most assignments, the compile-flags will include -Wall -Wextra -pedantic.
  6. Unless specified to the contrary for a specific assignment, makefiles, shell scripts, and code wil be expected to work equally well on both the linprog (Linux) and program (SunOS) systems.
  7. If an assignment calls for you to modify a provided file, your changes must be consistent with the coding style established by the given file. You must also add lines to the file header comment, indicating who modified it, when it was modified, and a short high-level explanation of the "why" and "how".
  8. If an assignment specifies that you are not to modify a given code file or makefile, you may not modify it.
  9. If the assignment calls for you to write an entire new file, you may choose your own coding style, subject to some general rules listed further below, but it must be consistent within the file. You should include a who/when/what/why header comment as specified further in the notes coding standards.
  10. You should avoid insecure coding practices, or in other words, you code should be robust against potential attacks. See the notes on secure coding as well as the notes on robust coding for more information on this.

See the notes on coding standards for more details.

Examinations & Quizzes

As mentioned in the Syllabus, there will be several quizes, two midterm examinations, and a final examination. This section of the Study Guide provides additional information and advice regarding examinations, along with links to places you can find other relevant information.

General Advice on Taking Exams

The following simple rules will help you get a better score on any examination:

Easy Questions

Each examination will contain a mix of questions of different degrees of difficulty. A large fraction of each exam will be intended to be "easy". The intent is that a person who earns all the easy points should be able to earn a grade of C- or better. There will be some questions that require deeper knowledge, either to get full credit on the question, or perhaps to answer the question at all. The intent is that for a person to earn a high grade, such as A or B, the person must be able to earn some of the harder points.

A good place to begin studying for the examination is to make sure you will get all the easy questions correct. A question is easy if one only needs a superficial knowledge of the relevant topics to get the question right, or at least to get substantial partial credit on the question. A question is also easy if it is approximately a repeat of a question on a quiz, or examination earlier that term (in the case of the Final Exam). Be sure you can define and use the Terms listed at the end of each of the chapters you have been assigned to study. Questions about the meanings and usage of those terms are considered easy. Also be sure you are able to answer the Review Questions at the ends of those chapters. These also will be considered easy questions. Don't just memorize answers, but make sure you really understand the facts and reasoning behind the question. If an examination re-phrases questions from a quiz or earlier exam, in a different format, those will still be considered to be easy questions.

Note that quizzes will be left open for a period of several days, and are allowed to be retaken, so that even though the questions are chosen randomly from a fairly large test bank, and differently for different students, by retaking a quiz you can expose yourself to a broader range of questions.

Harder Questions

Among the harder questions you should expect more emphasis on topics that e readings, and especially the programming projects.

Another Way of Looking at Examinations

The following is another way of looking at how the level of detail and depth of analysis you are expected to be able to provide on the exam relates to how you learned the material:

Calendar

The Course Calendar summarizes the important dates for the term, including examination and assignment due dates for all students in the course, and class meeting times. It will be updated, as necessary, throughout the term.

T. P. Baker. ($Id)