CENG 328 Operating Systems
Spring 2011

Most recent announcement: June15

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:

Çarşamba 15.Haziran.2011 14:58 Distribution of the grades is given.

Cuma 10.Haziran.2011 15:30 The evaluation of final exam papers is completed. Your final exam grades are available, check your sql server.

Çarşamba 8.Haziran.2011 15:28 Make-up exam is postponed to June 14, 2011 Tuesday at 16.00.

Pazartesi 6.Haziran.2011 18:54 There will be a make-up exam on Jun 08, 2011 Wendesday at 15: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 (to be announced);

• Arınç Köktürk – Midterm

• Özgür Ozan Şen – Midterm

• Çağlar Yalın – Midterm

• Tuğba Gümgör Yeğin – Midterm

• Nail Orkun Baycık – Final

• Onur Erecek – Final

• Fuat Özergil - Final

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

Perşembe 26.Mayıs.2011 00:42 Quiz3,4,5 grades are available, see Course Schedule section.

Cuma 20.Mayıs.2011 15:34 Additional lecture will be held on INT2 at 17:30.

Cuma 20.Mayıs.2011 15:34 The evaluation of midterm exam papers is completed. Your midterm exam grades are available, check your sql server.

Salı 17.Mayıs.2011 11:06 The laboratory notes for thirteenth week is published, see Course Schedule section.

Pazartesi 16.Mayıs.2011 13:30 Quiz2 grades are available, see Course Schedule section.

Salı 10.Mayıs.2011 10:14 The laboratory notes for twelfth week is published, see Course Schedule section.

Pazartesi 9.Mayıs.2011 17:52 The third assignment is given, see Course Schedule section. Assignment 3 is due to May 25, 2011 11:55pm . 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 prepare a report according to the given report guideline. Otherwise your assignment will not be evaluated.

4. You should submit your code and results (tables, plots, comments,...) via webonline.cankaya.edu.tr . Otherwise your assignment will not be evaluated.

5. 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 11:55pm. There will be no extension. But, you may submit your reports on paper next day.

Çarşamba 4.Mayıs.2011 10:05 The laboratory notes for eleventh week is published, see Course Schedule section.

Çarşamba 27.Nisan.2011 13:59 There will be NO LECTURES on Thursday and Friday due to 4. Mühendislik ve Teknoloji Sempozyumu 28-29 Nisan 2011. Attendencies will be taken at symposium halls. A MAKE-UP LECTURE WİLL BE ON APRİL 29, FRİDAY AT 16.00 O'CLOCK AFTER SYMPOSİUM. Lecture hall will be announced later.

Salı 19.Nisan.2011 14:47 I will be not available at April 21-22, 2011 due to BBÇ2011, İkinci Bozok Bilim Çalıştayı: Hesaplamalı Kimyasal Fizik. There will be NO LECTURES on Thursday and Friday. But, There will LAB sessions. Additional lectures for make-up of these lecture hours will be announced later.

Salı 19.Nisan.2011 14:46 Assignment and Quiz grades are corrected, see Course Schedule section.

Pazartesi 18.Nisan.2011 19:18 The laboratory notes for tenth week is published, see Course Schedule section.

Perşembe 14.Nisan.2011 10:30 Assignment2 and Quiz1 grades are available, see Course Schedule section.

Çarşamba 13.Nisan.2011 09:38 The laboratory notes for nineth week is published, see Course Schedule section.

Salı 29.Mart.2011 10:53 The laboratory notes for seventh week is published, see Course Schedule section.

Pazartesi 28.Mart.2011 00:59 The second and bonus assignments are given, see Course Schedule section. Assignment 2 is due to April 4, 2011 11:55pm and Bonus Assignment is due to April 11, 2011 11:55pm.

Perşembe 24.Mart.2011 19:42 Assignment1 grades are available, see Course Schedule section. We have a password protection mechanism (username: cankaya password: cankaya).

Salı 22.Mart.2011 18:12 There will be additional laboratory hours as follows:

Section 2 & 5: 26 Mart, 11:00

Section 3 & 6: 25 Mart, 17:00

Pazartesi 21.Mart.2011 17:37 The laboratory notes for sixth week is published, see Course Schedule section.

Perşembe 17.Mart.2011 10:11 There will be additional lecture hours at lab. sessions on Friday at 12:30 (Thursday section) and 14:30 (Friday section).

Salı 15.Mart.2011 09:50 The laboratory notes for fifth week is published, see Course Schedule section.

Pazartesi 7.Mart.2011 18:40 The laboratory notes for fourth week is published, see Course Schedule section.

Cuma 4.Mart.2011 17:42 The first assignment is given, see Course Schedule section. It is due to March 14, 2011 11:55pm.. Read the following lines very carefully;

Perşembe 3.Mart.2011 10:09 There will be NO LECTURE for friday section. Make-up time and hall will be announced later.

Salı 1.Mart.2011 12:30 The laboratory notes for third week is published, see Course Schedule section.

Pazartesi 21.Şubat.2011 14:04 The lecture hall for Friday section is changed, see weekly schedule.

Pazartesi 21.Şubat.2011 11:55 The laboratory notes for the second week is published, see Course Schedule section.

Pazar 13.Şubat.2011 23:42 In the first lecture, there will be first metting and lecture for Introduction/Overview. The lecture and laboratory notes for the first week are published, 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.

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

• 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

• 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

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

  • 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

• 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

    • 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

• 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

• 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

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