CENG 328 Operating Systems
Summer 2004

Most recent announcement: Aug 4

Announcements

Watch this space for the latest updates. Last updated: 4.Ağustos.2004 17:52The distribution of the grades are given.

August 3, 2004 18:34 The grading of the final exam is completed. Quiz4 grades is available, see Course Schedule.

August 2, 2004 15:42 The lab grades are available, see Course Schedule. The grading of the first midterm is completed.

July 25, 2004 17:02The solutions for the Midterm Exam is given.

July 19, 2004 19:31 The dates and places for the midterm and final exams are announced, see the Course Schedule. Quiz3 grades is available, see Course Schedule.

July 12, 2004 19:14 The date and place for the final exam are rearranged, see the Course Schedule. Quiz1 and Quiz2 grades are available, see Course Schedule.

July 7, 2004 17:01 The dates and places for the midterm and final exams are announced, see the Course Schedule.

June 30, 200416:08 Lab schedule is rearranged. See the Course Schedule. Tutorial link is active. See the Text Book.

June 26, 2004 12:43 In the first lecture, there will be first metting. The lecturing starts also.

• The all lecture notes as two-pages-in-one file is available.

• Anyone wants to get KNOPPIX_V3.4-2004-05-17-EN.iso may ask to me.

• Necessary information for compiling your modified java codes in Sun Lab is given. Anyone can ask to the technician for studying in the Sun Lab during Free Hours including weekends. For any problems about Free Hours in Sun Lab please inform me.

• The code examples in C language for the first four labs are available, you are advised to study these codes for better understanding and exam purposes. Extract with the command “tar -zxvf lab1-4.tgz” in Unix then compile with the command “gcc -o dosya dosya.c”. For the codes including threads, compilation is as the following: “gcc -o dosya -lpthread dosya.c”. For problems, see me at the office hours.

• For laboratory studies, see Course Schedule section. Modern Operating Systems Simulators is a collection of Java-based simulation programs which illustrate key concepts presented in the text Andrew S. Tanenbaum,   Modern Operating System, Second Edition (Prentice-Hall, 2001). The software is designed for students and instructors using this text.

• The tutorial link is active.

Overview

Ceng 328 is intended as a general introduction to the techniques used to implement operating systems and related kinds of systems software. Among the topics covered will be;

• basic operating system structure

• process and thread synchronization

• process scheduling and resource management

• process management (creation, synchronization, and communication);

• deadlock prevention, avoidance, and recovery;

• memory management techniques, main-memory management, virtual memory management

• control of disks and other input/output devices;

• file-system structure.

This course assumes familiarity with basic computer organization (e.g., processors, memory, and I/O devices). You will need to be able to program in Java / C (or C++) to perform the assignments in the course.

Lecture Information

There are two groups for lecturing and three groups for lab sessions, you may attend any one of the lecture hours but not for lab sessions. Please attend your predefined lab sessions regularly. The UNIX operating system will be introduced to you first in the lab sessions , later some java or C codes will be executed to study the operating system features and you will be responsible for writing codes, to be graded.

In the beginning of the each lecture hour, you will have a quiz (15 minutes) for the previos week's subjects. There won't be any make-up for these quizes and they will have weight for the final grading.

Important announcements will be posted to the Announcements section of this web page above, so please check this page frequently. You are responsible for all such announcements, as well as announcements made in lecture.

Course Outline

• Contents

• List of Tables

• List of Figures

• Introduction

  • What is Operating System?

    • Functionalities in OS:

  • History of operating Systems

    • Mainframe Systems

    • Batch and Multiprogrammed Systems

    • Time Sharing

    • Personnel Computers

    • Parallel Processing Systems

    • Distributed Systems

    • Clustered Systems

    • Real-Time

    • Embedded, Smart-Card and Handheld

  • Computer Hardware Review

    • Processor

    • Main Memory

    • I/O Modules and Structure

    • System bus

    • Storage Structure and Hierarchy

    • Protection

  • Interrupts and Traps

    • Accessing OS Services

  • Operating System Components

  • Bootstrapping

  • System Structure

  • Why Study Operating Systems?

    • Problems in building OS

• Processes and Threads

  • Processes

    • The Process Model

    • Context Switch

    • Dispatcher

    • Process Creation

    • Process Termination

    • Process States

  • Threads

    • The Thread Model

    • Implementing Threads in User Space

    • Implementing Threads in the Kernel

  • Interprocess Communication

    • Race Conditions

    • Critical Regions

    • Mutual Exclusion with Busy Waiting (Software approach)

    • Sleep and wakeup

    • Semaphores

    • Monitors

  • Classical IPC Problems

    • The Dining Philosophers Problem (see Fig. 2.17)

    • The Readers and Writers Problem (see Fig. 2.19)

    • The Sleeping Barber Problem (see Fig. 2.20)

  • Scheduling

  • Introduction to Scheduling

  • Scheduling in Batch Systems

  • Scheduling in Interactive Systems

  • Policy versus Mechanism

• Deadlock

  • Resources

  • Introduction to Deadlocks

    • Conditions for Deadlock (See Fig. 3.1)

    • Deadlock Modeling (See Fig. 3.2)

  • The Ostrich Algorithm

  • Deadlock Detection and Recovery

  • Deadlock Avoidance

    • Resource Trajectories (See Fig. 3.4)

    • Safe and Unsafe States (See Fig. 3.5)

    • The Banker's Algorithm for Deadlock Avoidance

  • Deadlock Prevention

  • Summary of Deadlock strategies

• Memory Management

  • Basic Memory Management

    • Monoprogramming without Swapping or Paging (see the Fig. 4.3)

    • Multiprogramming with Fixed Partitions (see the Fig. 4.4)

    • Relocation and Protection (see the Fig. 4.5)

  • Swapping

    • Memory Management cont.

  • Virtual Memory

    • Paging (see the Fig. 4.8)

    • Page Tables (see Fig. 4.12)

    • Inverted Page Tables

    • Basic policies

    • Page Replacement Algorithms

    • Page Replacement Cont.

  • Segmentation

    • Segmentation with Paging

    • Segmentation with Paging: MULTICS

    • Segmentation with Paging: The Intel Pentium (see Fig. 4.18)

• INPUT/OUTPUT

  • Principles of I/O Hardware

    • Device Controllers (see Fig. 5.1)

    • I/O Devices

    • Characteristics (see Table 5.2) and Differences in I/O Devices

    • Evolution of the I/O Function (see Fig. 5.2)

    • Memory-Mapped I/O (see Fig. 5.3)

    • Direct Memory Access (DMA)

    • Interrupts Revisited (see Fig. 5.6)

  • Principles of I/O Software

    • Programmed I/O (see Fig. 5.7a)

    • Interrupt-Driven I/O (see Fig. 5.7b)

    • Direct Memory Access (see Fig. 5.7c)

  • Operating System Design Issues

  • I/O Software Layers (see Fig. 5.8)

    • Interrupt Handlers

    • Device Drivers (see Fig. 5.9)

    • Device Independent I/O Software(see Fig. 5.10)

    • User Level Software

  • Disks (see Fig. 5.13)

    • Disk Hardware

    • Disk Formatting

    • Disk Arm Scheduling Algorithms (see Fig. 5.18)

    • Error-Handling

• File Systems

  • Files

    • File Naming

    • File Structure; From OS's perspective

    • File Types

    • File Access

    • File Attributes(see Fig. 6.4)

    • File Operations

    • An Example Program Using File System Calls (see Fig. 6.6)

    • Memory-Mapped Files (see Fig. 6.7)

    • File Organization and Access; Programmer's Perspective

  • Directories

    • Path Names

    • File Sharing

  • File System Implementation

    • File System Layout

    • Implementing Files (see Fig. 6.13)

    • Implementing Directories

    • Shared Files (see Fig. 6.17)

    • Disk Space Management (Free space management)

    • Other file system implementation issues

  • UNIX File Management

  • vita

• About this document ...

Text Book

Required

Readings will be assigned in Modern Operating Systems, Second Edition by Andrew S. Tanenbaum, Prentice Hall, 2001.

Recommended

Another recently used text book that covers the same material is Applied Operating Systems Concepts, Sixth Edition by Abraham Silberschatz, Peter Galvin, and Greg Gagne, John Wiley and Sons, 2003.

This text is only recommended rather than required. This book is useful for reference, for an alternative point of view.

Online References

Some materials and tutorials are given. Please inform me about the usefullness of the materials. Check this place for updates.

Some useful C++ links can be found here and here.

Notes on Java. The following references are available online at the Java home site.

• The Java Tutorial

• The Java Language Specification

• Code Conventions for the Java Programming Language

• Java API Documentation

Grading Criteria

• There will be a midterm and a final exam, will count 20% and 40% of your grade, respectively.

• Quiz: 15% (worst of the quizes will be discarded)

• Lab: 15% (worst of the labs will be discarded)

• Attendance is required and constitutes part of your course grade; 10%

Policies

• Attendance is not compulsory, but you are responsible for everything said in class.

• I encourage you to ask questions in class. You are supposed to ask questions. Don't guess, ask a question!

• You may discuss homework problems with classmates (although it is not to your advantage to do so).

• You can use ideas from the literature (with proper citation).

• You can use anything from the textbook/notes.

• The code you submit must be written completely by you.

Course Schedule

The following schedule is tentative; it may be updated later in the semester, so check back here frequently.