COP5611 - Advanced Operating Systems

Spring 2009

Class description:

The organization of this class reflects its “Advanced” status.

The textbook provides some background material; additional material will be

       discussed in class.

 

  1. Review of Basic Concepts (8 weeks): 
    1. The “big picture;” OS concepts and their relations with

other disciplines; enduring problems;        

    1. Structure and functions of operating systems.
    2. Process and threads;
    3. Memory hierarchies;
    4. Storage management;
    5. Security.
  1. Distributed and parallel systems.

(4 weeks)

    1. System architecture and challenges for OS design; clusters; high-performance systems; peer-to-peer systems.
    2. Interconnection networks; Bandwidth, Latency, Fault-tolerance;
    3. Concurrency;
    4. Consistent global state;
    5. Synchronization;
    6. Deadlocks;
    7. Coordination.
  1. Resource Management. Scheduling. Performance evaluation.

(2.5 weeks)

    1. Scheduling algorithms.
    2. Performance evolution.

                                                             i.      Measurements.

                                                          ii.      Simulation

                                                        iii.      Queuing models.

  1. Cyber-Physical systems; real-time and embedded operating systems (2.5 weeks).
    1. Problems and basic principles for the design of operating systems for real-time and embedded systems.
    2. Case studies: the Android; the iPhone OS; Juniper OS, Cisco OS.
  2. A look back at the big picture.

 

The amount of time dedicated to each topic is tentative.

 

 

 

Instructor:

Dan C. Marinescu

Teaching assistant:

TBD

 

 

Office:

HEC  - 439 B

Communication

Assignments and announcements will be posted on the course web site.

Communication through Email and office hours questions are encouraged.

Slides will be used in class occasionally.

Audio or video recording of lectures is not permitted.

E-mail:

dcm@eecs.ucf.edu 

Web Site:

http://www.cs.ucf.edu/~dcm

Classroom:

HEC - 0118

 

 

Class Hours:

Monday, Wednesday 6:00 - 7:15  PM

Office Hours:

Monday, Wednesday 3:00 - 4:30  PM

Pre-requisites:

Undergraduate operating systems class (COP 4600, EEL 4881 or equivalent).

Fluency in Java.

Recommended readings:

Operating System Concepts (8th Edition) by A. Silberschatz, P. Galvin and G. Gagne

Papers from the literature.

Miscellaneous

The students are expected to attend classes and to actively participate: study carefully the reading assignments, ask questions, answer questions, and express opinions.

All exams are open-book and open notes.

Projects:

I am still debating if a project for this class is feasible…

Grading:

Assignments: 50%
Exams: 50% (Midterm 20%, Final 30%)

 

Syllabus

Lecture

Date

Topic

 Readings, Homeworks

 

1

week 1

Wednesday

January 7

Class overview.

 

1. Basic concepts

-         abstractions and models

-         universal computers

-         resource sharing models

-         resource virtualization

-         concurrency

-         state (of a system, process, computation)

-         cyber physical systems – time the great challenge

 

2. The “big picture”. OS concepts and relations with concepts from:

-         computer architecture

-         computer networks

-         algorithms

-         databases

-         parallel and distributed systems

-         performance evaluation

-         applications (embedded systems, multi-media)

 

Reading assignments:

1. On computable numbers, with an application to the  Entscheidungsproblem (Turing)

2. The first draft  on the EDVAC (von Neumann)

3. Hints for Computer System Design (Butler W. Lampson)

4. My recollections of operating systems design (E. W. Dijkstra)

 

HW 1 (due Wednesday January 21)

 

P1 (20 points)  Based upon a careful reading of papers (1) and (2)

      discuss the effect of Turing’s ideas upon the practical design of the

       EDVAC.  Can you find in von Neumann’s paper any hint

      regarding the feasibility or the need for an operating system?

 

P2. (20 points) “Make it fast, rather than general or powerful.”

Discuss important applications of this corollary from paper (3) in

computer architecture and operating systems design.

 

P3. (20 points)  Discuss in some depth two innovations in THE operating system discussed in paper (4).

 

P4. (40 points)  Come up with a list of milestones in operating systems

design. For each milestone describe using at most 5 sentences:  what it is,

who introduced it and when, and what is the importance of it.

 

 

 

2

week 2

Monday

January 12

    1. The relationship between physical systems and  models

    2. Layering

    3. Virtualization.

 

Reading assignment: Chapter 1 in the text book

 

 

3

week 2

Wednesday

January 14
  1. Resource sharing models: multiprogramming and multitasking
  2. Operating Systems Structures
  3. The complexity of computing and communication systems
  4. State
  5. Butler Lampson’s hints for system design

 

Reading assignment: Chapter 2 in the text book

 

 

 

Monday

January 19

Martin Luther King's day

No class

 

 

4

week 3

Wednesday

January 21

 

1.    Butler Lampson’s hints for system design

2.    The complexity of computing and communication systems

3.    State

4.    Processes

 

HW1 due today.

Reading assignment: Chapter 3 in the text book

 

 

HW2 due Wednesday February 4

 

P1 (40 points)  To correct the problem  with the CONNECT system call in TENEX discussed in class one could modify: (i)  the implementation of CONNECT;

(ii) the implementation of a system call in general; (iii) the  parameter passed between the user to the kernel.

Discuss each one of these alternatives, show how your solution corrects the problem,

And compare the advantages and the drawbacks of each.

     

P2. (40 points)   Locate the most relevant papers discussing message passing versus shared-memory.  Provide a one page summary of the paper you consider the most relevant.

Provide your own analysis of the relative merits of each strategy.

 

P3. (20 points)  Analyze different semantics for the Remote Procedure Call and their relative merits. Discuss the vulnerability posed by incorrect  implementations of RPC.

 

 

 

5

week 4

Monday

January 26

Chinese New Year

1.    Process handling by the kernel

2.    Inter-process communication

3.    Threads

 

Reading assignment: Chapter 4

 

 

6

week 4

Wednesday

January 28

1.    More about threads

2.    Process synchronization

 

Reading assignment: Chapter 6

 

 

7

week 5

Monday

February 2

1.    Discussion of a problem regarding threads and I/O

2.    More about condition variables and monitors

3.    Discussion of a problem about condition variables and monitors

 

Reading assignment: Chapter 7

 

Homework 2 due on Wednesday

 

 

 

8

week 5

Wednesday

February 4

1.    Discussion of homework assignment 3

2.    Process synchronization leftovers

3.    Atomic transactions

4.    Discussion of a problem about atomic transactions

 

Reading assignment: Chapter 7

 

Homework 2 due today.

 

Homework 3.

 

 

 

9

week 6

Monday

February 9

2        Three-way handshake

3        Deadlocks

 

 

 

10

week 6

Wednesday

February 11

2        Problem solving

3        More about deadlocks

4        Consumable resources

5        Elements of queuing theory

6        Arrival and service processes

7        Little’s law

8        Problem

 

 

 

11

week 7

Monday

February 16

1.    Elements of queuing theory

a.    Arrival and service processes

b.    Little’s law

c.     Problem

 

 

Reading assignment: Chapter 5.

Homework 3 is due on Wednesday February 18

 

 

12

week 7

Wednesday

February 18

1.    Birth-death processes

2.    M/M/1 systems

3.    CPU Scheduling

4.    Scheduling Algorithms

Homework 3 due today

Homework 4

Reading assignment: Chapter 5

 

 

13

week 8

Monday

February 23

1.    CPU Scheduling

2.    Scheduling Algorithms

3.    M/M/m systems

 

Reading assignment: Priority Inheritance Protocols

 

 

14

week 8

Wednesday

February 25

1.    M/M/m systems

2.    Scheduling Algorithms

3.    Memory management

 

Reading assignment Chapter 

 

 

15

week 9

Monday

March 2

Review. Q and Q session.

 

 

16

week 9

Wednesday

March 4

Midterm

 

 

 

Monday

March  9

Spring break

No class

 

 

 

Wednesday

March  11

Spring break

No class

 

 

17

week 10

Monday

March 16

Discussion of the midterm.

 

Memory management

a.    Architectural background

b.    Swapping

c.     Contiguous memory allocation

d.    Paging

e.    Segmentation

f.      Case studies:

                                                 i.      The Intel Pentium

                                              ii.      Linux

 

Lecture 15 slides

 

18

week 10

Wednesday

March 18

1.    The structure of address spaces

2.    Memory management leftovers

3.    Virtual memory

 

Architectural support for

memory hierarchies

 

 

 

Homework 4 due today

 

Homework  5

 

19

week 11

Monday

March 23

1.    Page replacement algorithms

2.    Working set model 

 

Homework 5 due on Monday March 30.

 

 

20

week 11

Wednesday March 25

1. Cache

2. Introduction to I/O Sub-system

Homework 6 due Wednesday April 8

 

 

21

week 12

Monday

March 30

1.    I/O subsystem

2.        2. File System Implementation

 

Lecture 19 slides

 

22

week 12

Wednesday

April 1

 1 NFS

 2. Distributed File

Reading assignments:

   A log structured file system

   Extensible file systems

 

 

 

23

week 13

Monday

April 6
  1. Andrew File System
  2. Network and Distributed Operating Systems
  3. Multiple Access Networks

Reading assignment

 

 

 

24

week 13

Wednesday

April 8
  1. Communication Networks. Local and Wide area Networks
  2. Local Area Networks. Multiple access algorithms Scheduled and non-scheduled access for Multiple Access Channels.

 

 

 

25

week 14

Monday

April 13
  1. Distributed coordination; algorithms for sharing a communication channel

·        Aloha.

·        Tree algorithm.

·        The stack algorithm.

 

 

 

26

week 14

Wednesday

April 15
  1. Distributed coordination; algorithms for sharing a communication channel
    1. FCFS algorithm
    2. Token passing rings.
    3. Asynchronous communication
  2. Process Models
    1. States and events; local and communication events
    2. Local history
    3. Local and global states
    4. Process coordination and the global predicate evaluation problem

 

Reading assignment: Distributed snapshots by Mani Chandy and Leslie Lamport

 

Class notes

 

27

week 15

Monday

April 20

 

 

 

28

week 15

Wednesday

April 22

Project Presentation -

Joseph Rocco – The iPhone Project

 

29

Monday

April 27

Class Review. Looking again at the Big Picture

 

 

 

Wednesday April 29 4 PM

Final exam