CENG 328 Operating Systems
Spring 2010

Most recent announcement: June16

Announcements

Watch this space for the latest updates (If the characters do not show properly, please try viewing this page with Unicode (UTF-8) encoding). Last updated:

16.Haziran.2010 15:57 Distribution of the grades is given.

13.Haziran.2010 14:08 The evaluation of final exam papers is completed. Your final exam grades are available, check your sql server.

7.Haziran.2010 12:35 There will be a make-up exam on Jun 11, 2010 Friday at 14:00 (the exam time is subject to change due to conflicts with other exams). The list of the students that I have Doctor's written excuse;

• Mehmet Zahid Berktaş – Midterm

• Nihat Mert Uzunalioğlu – Final

• Tuğçe Tolluoğlu – Final

• Oğuzhan Alptekin – Final

• Onur Erecek - Final

• Others (not be valid until i received a valid report)

2.Haziran.2010 17:45 Final exam questions are available, see Course Schedule section.

2.Haziran.2010 17:41 Assignment3&4 grades are available, see Course Schedule section.

31.Mayıs.2010 15:02 DO NOT FORGET TO BIRING YOUR CALCULATOR FOR THE EXAM. YOU ARE NOT ALLOWED TO USE ANY OTHER ELECTRONIC EQUIPMENT IN THE EXAM.

25.Mayıs.2010 12:02 Laboratory quiz4 grades are available, see Course Schedule section.

23.Mayıs.2010 01:08 The evaluation of midterm exam papers is completed finally. Sorry for the delay. Your midterm exam grades are available, check your sql server. You can see your exam papers next week in my office. I will not be available on Monday (May 24, 2010).

18.Mayıs.2010 14:33 The lecture notes for the fourteenth week is published, see Course Schedule section.

17.Mayıs.2010 11:49 The fourth assignment is given, see Course Schedule section. It is due to May 24, 2010. Read the following lines very carefully;

1. Compress all files to one file. Name this file as “yourstudentID.zip(/tar/rar/tgz/gz)” otherwise your assignment will not be evaluated.

2. When this file decompressed, all files should reside in a directory named with “yourstudentID”. otherwise your assignment will not be evaluated.

3. You should submit your code and results (tables, plots, comments,...) via e-mail to me and to TA. otherwise your assignment will not be evaluated.

4. You should also submit your code and results (tables, plots, comments,...) in paper to TA. otherwise your assignment will not be evaluated.

Submission deadline for the assignment is at 24.00 o'clock. There will be no extension. You should send your E-mails until this time. But, you may submit your reports on paper next day.

11.Mayıs.2010 14:17 Quiz5 grades are available, see Course Schedule section.

11.Mayıs.2010 14:06 The lecture notes for the thirteenth week is published, see Course Schedule section.

4.Mayıs.2010 14:30 The lecture notes for the twelfth week is published, see Course Schedule section.

27.Nisan.2010 14:31 The lecture notes for the eleventh week is published, see Course Schedule section.

27.Nisan.2010 01:49 The lecture notes in plain format for the eleventh week is published, see Course Schedule section.

21.Nisan.2010 14:35 Third assignment due date is postponed to last day of the classes (May 21, 2010). It is also changed as a BONUS assignment.

21.Nisan.2010 12:21 The list for laboratory groups are rearranged due to mess in laboratory sessions. Please see the file for the list, attend to YOUR session. Otherwise you will be absent.

20.Nisan.2010 14:35 The lecture notes for the tenth week is published, see Course Schedule section

13.Nisan.2010 23:43 Laboratory quiz3 grades are available, see Course Schedule section.

13.Nisan.2010 14:34 The lecture notes for the nineth week is published, see Course Schedule section

13.Nisan.2010 01:40 The lecture notes in plain format for the nineth week is published, see Course Schedule section

10.Nisan.2010 01:52 The third assignment is given, see Course Schedule section. It is due to April 19, 2010. Read the following lines very carefully;

10.Nisan.2010 01:17 The laboratory notes for the sixth week is slightly modified. Assignment2 grades are available, see Course Schedule section.

6.Nisan.2010 21:08 The lecture notes for the eight week is published, see Course Schedule section

6.Nisan.2010 12:10 There will be NO lecture today. The make-up lecture will be held at Thursday 16:40. The classrom will be defined later or at lecture time.

6.Nisan.2010 11:33 The lecture notes in plain format for the eight week is published, see Course Schedule section

5.Nisan.2010 00:56 Quiz3 grades are available, see Course Schedule section.

30.Mart.2010 15:32 AssignmentI grades are available, see Course Schedule section.

26.Mart.2010 09:30 The laboratory notes for the sixth week is published, see Course Schedule section.

24.Mart.2010 00:09 Laboratory quiz2 and quiz2 grades are available, see Course Schedule section.

23.Mart.2010 13:09 The lecture notes for the sixth week is published, see Course Schedule section

23.Mart.2010 10:15 The lecture notes in plain format for the sixth week is published, see Course Schedule section

19.Mart.2010 00:05 The second assignment is given, see Course Schedule section. It is due to March 29, 2010.

18.Mart.201023:55 The laboratory notes for the fifth week is published, see Course Schedule section.

17.Mart.2010 16:06 Quiz1 grades are available, see Course Schedule section.

16.Mart.2010 12:57 The lecture notes for the fifth week is published, see Course Schedule section

16.Mart.2010 00:09 The lecture notes in plain format for the fifth week is published, see Course Schedule section

12.Mart.2010 00:09 The laboratory notes for the fourth week is published, see Course Schedule section.

9.Mart.2010 12:47 The lecture notes for the fourth week is published, see Course Schedule section

9.Mart.2010 00:44 Laboratory quiz1 grades are available, see Course Schedule section. We have a password protection mechanism (username: cankaya password: cankaya).

9.Mart.2010 00:37 The lecture notes in plain format for the fourth week is published, see Course Schedule section

4.Mart.2010 23:08 The first assignment is given, see Course Schedule section. It is due to March 15, 10, 2010.

4.Mart.2010 23:01 The laboratory notes for the second week is published, see Course Schedule section.

2.Mart.2010 11:40 The lecture notes for the third week is published, see Course Schedule section

25.Şubat.2010 16:23 The laboratory notes for the second week is published, see Course Schedule section. There will be NO change in the schedule of class and lab. hours.

20.Şubat.2010 23:05 The lecture notes for the second week is published, see Course Schedule section.

18.Şubat.2010 16:52 The laboratory notes for the first week is published, see Course Schedule section.

15.Şubat.2010 14:29 The lecture notes for the first week is published, see Course Schedule section.

6.Şubat.2010 17:55 In the first lecture, there will be first metting.

• The lecture notes for the second week will be published soon, see Course Schedule section.

• The tutorial link is active.

• For laboratory studies, we will study C codes and students will be encouraged to programming for concepts presented in the class. There will be assignments to be graded in the following laboratory session.

• Anyone wants to get a live cd without installing linux, download from local server or may ask to room 308.

• Ubuntu live cd

• Pardus live cd

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);

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

• file-system structure

• control of disks and other input/output devices;

• deadlock prevention, avoidance, and recovery.

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 C ( or Java / C++) to perform the assignments in the course.

Lecture Information

There are two groups for lecturing and two 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. Your sits in the lab will not be changed there after. The UNIX operating system will be introduced to you first in the lab sessions , later some C codes will be executed to study the operating system features and you will be responsible for writing codes, to be graded.

You MAY have a quiz (10 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. We have a pop-up quiz policy.

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

• First Meeting

  • Lecture Information

  • Overview

  • Text Book

  • Grading Criteria & Policies

• Introduction/Overview

  • What Is An Operating System?

    • User View - The OS as an Extended Machine

    • System View - The OS as a Resource Manager

    • Defining OS and Functionalities

  • Computer-System Organization

    • Computer-System Operation

    • Storage Structure

    • I/O Structure

  • OPERATING SYSTEMS LABORATORY I - UNIX TUTORIAL

    • Login and Logout

    • Commands

    • Simple Commands

    • Working With Files

    • Working With Directories

    • Compiling A C Program

      • Running The Resulting Program

    • Compiling A Multi-Source C Program

    • Exercises

  • OPERATING SYSTEMS LABORATORY I - UNIX Tutorial - Additional

    • The Kernel

    • The Shell

    • UNIX file system

    • History of the UNIX operating system

      • Modern variants of UNIX

    • Debugging C/C++ Programs Using gdb

      • Creating Debug-Ready Code

      • Creating Optimized Code

      • Getting Extra Compiler Warnings

      • Compiling A Single-Source "C++" Program

      • Getting a Deeper Understanding - Compilation Steps

      • Invoking the "gdb" Debugger

      • Running A Program Inside The Debugger

      • Setting Breakpoints

      • Stepping A Command At A Time

      • Printing Variables And Expressions

      • Examining The Function Call Stack

      • Attaching To an Already Running Process

      • Debugging A Crashed Program

  • Evolution of Operating Systems, Computer-System Architecture and Operating-System Structure

    • Mainframe Systems

    • Batch and Multiprogrammed Systems

    • Time Sharing

    • Personnel Computers and Single-Processor Systems

    • Multiprocessor Systems; Parallel Processing Systems - Tightly coupled systems

    • Multiprocessor Systems; Distributed Systems - Loosely coupled systems

    • Real-Time Embedded Systems

    • Handheld Systems

  • Operating-System Operations

    • Dual-Mode Operation

    • Timer

  • Process Management

  • Memory Management

  • Storage Management

    • File-System Management

    • Mass-Storage Management

    • Caching

    • I/O Systems

  • Protection

  • OPERATING SYSTEMS LABORATORY II - C Review I

  • Operating-System Structures

    • Operating-System Services

    • User Operating-System Interface

      • Command Interpreter

      • Graphical User Interfaces

    • System Calls

    • Types of System Calls

      • Example of Standard C Library

      • Process Control

      • File Management

      • Device Management

      • Information Maintenance

      • Communication

    • Operating-System Design and Implementation

      • Design Goals

      • Mechanisms and Policies

      • Implementation

    • Operating-System Structure

      • Simple Structure

      • Layered Approach

      • Microkernels

      • Modules

    • Virtual Machines

      • Examples - VMware

      • Examples - The Java Virtual Machine

  • OPERATING SYSTEMS LABORATORY III - C Review II

    • Using Debugger

    • Assignment I - C Review; Due to March 15, 2010

    • Additional Assignment - C Review (BONUS); Due to March 15, 2010

• Processes

  • Process Concept

    • The Process

    • Process State

    • Process Control Block

  • Process Scheduling

    • Scheduling Queues

    • Schedulers

    • Context Switch

    • Modelling Multiprogramming

  • Operations on Processes

    • Process Creation

    • Process Termination

  • Interprocess Communication

    • Shared-Memory Systems

  • OPERATING SYSTEMS LABORATORY IV - Processes I

• Threads

  • Overview

    • Motivation

    • Benefits

  • Multithreading Models

    • Many-to-One Model

    • One-to-One Model

    • Many-to-Many Model

  • Thread Libraries

    • Pthreads

  • Threading Issues

    • The and System Calls

    • Cancellation

    • Signal Handling

  • Operating-System Examples

    • Linux Threads

• CPU scheduling

  • Basic Concepts

    • CPU-I/O Burst Cycle

    • CPU Scheduler

    • Pre-emptive Scheduling

    • Dispatcher

  • Scheduling Criteria

  • OPERATING SYSTEMS LABORATORY V - Processes II& Threads I

    • Examples&Exercises:

    • Assignment II - Processes; Due to March 29, 2010

  • Scheduling Algorithms

    • First-Come, First-Served Scheduling

    • Shortest-Job-First Scheduling

    • Priority Scheduling

    • Round-Robin Scheduling

    • Multilevel Queue Scheduling

    • Multilevel Feedback-Queue Scheduling

  • Multiple-Processor Scheduling

    • Approaches to Multiple-Processor Scheduling

    • Load Balancing

  • Operating System Examples

    • Example: Linux Scheduling

• Process Synchronization

  • Race Condition

  • The Critical-Section Problem

    • Disabling Interrupts: (Systems approach)

    • Lock Variables: (Software approach)

  • Mutual Exclusion with Busy Waiting

    • Strict Alternation (Software approach)

  • OPERATING SYSTEMS LABORATORY VI - Processes III

    • Examples:

    • CPU Scheduling Simulation

  • Peterson's Solution (Software approach)

  • Semaphores

    • Usage

    • Implementation

    • Deadlocks and Starvation

    • Mutexes

  • Classic Problems of Synchronization

    • The Bounded-Buffer Problem

    • The Readers-Writers Problem

    • The Dining-Philosophers Problem

  • Monitors

    • Usage

  • OPERATING SYSTEMS LABORATORY VII - Semaphores, Mutual Exclusion

    • Semaphores and Mutual Exclusion

    • Dining Philosophers Simulator

    • Assignment III - Scheduling; Due to April 19, 2010

• Deadlocks

  • System Model

  • Deadlock Characterization

    • Necessary Conditions

    • Resource-Allocation Graph

  • Methods for Handling Deadlocks

  • Deadlock Prevention

    • Mutual Exclusion

    • Hold and Wait

    • No Preemption

    • Circular Wait

  • Deadlock Avoidance

    • Safe State

  • Deadlock Detection

    • Single Instance of Each Resource Type

    • Several Instances of a Resource Type

    • Detection-Algorithm Usage

  • Recovery From Deadlock

    • Process Termination

    • Resource Preemption

• Main memory

  • Background

    • Basic Hardware

  • OPERATING SYSTEMS LABORATORY VIII - LABORATORY REVIEW

    • Process Scheduling

    • Dining Philosophers

    • Address Binding

    • Logical Versus Physical Address Space

    • Dynamic Loading

    • Dynamic Linking and Shared Libraries

  • Swapping

  • Contiguous Memory Allocation

    • Memory Mapping and Protection

    • Memory Allocation

    • Fragmentation

  • Paging

    • Basic Method

    • Protection

    • Shared Pages

  • Segmentation

    • Basic Method

    • Hardware

• Virtual Memory

  • Background

  • Demand Paging

    • Basic Concepts

    • Performance of Demand Paging

  • Copy-on-Write

  • Page Replacement

    • Basic Page Replacement

    • FIFO Page Replacement

    • Optimal Page Replacement

    • LRU Page Replacement

  • Allocation of Frames

    • Allocation Algorithms

    • Global versus Local Allocation

  • Thrashing

    • Cause of Thrashing

• File-System Interface

  • File Concept

    • File Attributes

    • File Operations

    • An Example Program Using File System Calls

    • File Types

    • Internal File Structure

  • Access Methods

    • Sequential Access

    • Direct (Random) Access

    • Other Access Methods

  • Directory Structure

    • Storage Structure

    • Directory Overview

    • Single-Level Directory

    • Two-Level Directory

    • Tree-Structured Directories

    • Acyclic-Graph Directories

  • File-System Mounting

  • File Sharing

    • Multiple Users

  • Protection

    • Types of Access

    • Access Control

  • OPERATING SYSTEMS LABORATORY XI - Memory Management, Files and Directories

    • Memory Management

      • Examples & Exercises:

    • Files and Directories

• File System Implementation

  • File-System Structure

  • File-System Implementation

    • Overview

    • Partitions and Mounting

    • Virtual File Systems

  • Directory Implementation

    • Linear List

    • Hash Table

  • Allocation Methods

    • Contiguous Allocation

    • Linked Allocation

    • Indexed Allocation

  • Free-Space Management

    • Bit Vector

    • Linked List

    • Grouping

    • Counting

  • Log-Structured File Systems

  • OPERATING SYSTEMS LABORATORY XII - Files and Directories II

    • Examples & Exercises:

    • MOSS File System Simulator

  • Assignment IV; Due to May 24, 2010

• Mass-Storage Structure

  • Overview of Mass-Storage Structure

    • Magnetic Disks

  • Disk Structure

  • Disk Attachment

    • Host-Attached Storage

    • Network-Attached Storage

    • Storage-Area Network

  • Disk Scheduling

    • FCFS Scheduling

    • SSTF Scheduling

    • SCAN Scheduling

    • C-SCAN Scheduling

    • LOOK Scheduling

  • Disk Management

    • Disk Formatting

  • RAID Structure

    • Improvement of Reliability via Redundancy

    • Improvement in Performance via Parallelism

    • RAID Levels

  • OPERATING SYSTEMS LABORATORY XIII - Laboratory Review

    • Processes

    • Memory

    • File Operations

• References:

• Vita

• About this document ...

Text Book

Required

Readings will be assigned in Operating System Concepts, 8th Edition by Abraham Silberschatz, Peter Baer Galvin, Greg Gagne, John Wiley and Sons, January 2008. Complementary on-line contents

Recommended

Another frequently used text book that covers the same material with a different approach is Modern Operating Systems, 3rd Edition by Andrew S. Tanenbaum, Prentice Hall, 2008.

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

Grading Criteria

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

• Quiz: 15%

• 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.