MCA204/BCS301: OPERATING SYSTEM CONCEPTS
(EVEN SEMESTERS)
(updated
July 2007)
Course Credits : 04
Assessment : Periodical Tests, Assignments, Semester Examination
Contact Hours : 04 per week
Meeting Times : Tuesday & Friday 11.10 A.M. – 12.40 P.M.
Location : Computer Centre Classroom No. 1
Overlaps with : BCS301- Operating System Concepts (New)
Course Objectives & Prerequisites:
The course aims to introduce Operating System Concepts with emphasis on foundations & design principles.
It comprises of 10 modules. Module 1 traces the evolutionary history of Operating Systems and introduces
concepts of Batch processing, Multiprogramming & Timesharing. Module 2 dwells into structures & functions
of operating systems. Different components of operating system like Process Management, Concurrency
mechanisms, Deadlock handling, Memory Management techniques, Virtual Memory, File System and
Secondary Storage Management, Security & protection etc. are covered in modules 3 to 9. The course concludes
with Module 10 which presents a case study of UNIX & WINDOWS Operating Systems and an overview of
recent trends and current research in Operating Systems.
The course does not require any special prior study except a basic understanding of Digital Computers.
A prior course in Computer Organization & Architecture and Computer Programming will help increase
the pace of learning.
Introduction: Defining an Operating System, Design Goals, Evolutionary history of operating systems;
Concept of User, job and Resources; Batch processing, Multi-programming, Time sharing; Structure and
Functions of Operating System.
Process Management: Process states, State Transitions, Process Control Structure, Context Switching,
Process Scheduling, Threads.
Memory Management: Address Binding, Dynamic Loading and Linking Concepts, Logical and Physical
Addresses, Contiguous Allocation, Fragmentation, Paging, Segmentation, Combined Systems, Virtual Memory,
Demand Paging, Page fault, Page replacement algorithms, Global Vs Local Allocation, Thrashing, Working Set Model,
Pre-Paging.
Concurrent Processes: Process Interaction, Shared Data and Critical Section, Mutual Exclusion, Busy form
of waiting, Lock and unlock primitives, Synchronization, Classical Problems of Synchronization, Semaphores,
Monitors, Conditional Critical Regions, System Deadlock, Wait for Graph, Deadlock Handling Techniques: Prevention,
Avoidance, Detection and Recovery.
File and Secondary Storage Management: File Attributes, File Types, File Access Methods, Directory Structure,
File System Organization and Mounting, Allocation Methods, Free Space management; Disk Structure, Logical
and Physical View, Disk Head Scheduling, Formatting, Swap Management.
Protection
& Security.
UNIX/ LINUX and WINDOWS as example systems.
1.
Silberschatz & Galvin, Operating System Principles, John Wiley 7th
Ed (Asia Student Edition).
Reference Books:
1. William Stallings, Operating Systems: Internals & Design Principles, Pearson Education, 5th Ed.
2. A. S. Tanenbaum, Modern Operating Systems 2/e, Pearson Education
3. Gary Nutt, Operating Systems 3/e, Pearson Education.
4. M. J. Bach, The Design of the UNIX Operating System, Pearson Education.
5. Vijay Mukhi, The C Odessy, BPB Publications.
Students are encouraged to visit Portals/ Journals of ACM, Operating System Reviews and USENIX conference
proceedings. Local copies of few suggested readings are available at this page only for academic reference purposes.
Following are representative portals/ journals/ SIGs reporting research in Operating Systems:
ACM
Transactions
on Computer Systems (TOCS)
ACM
Operating Systems Review (SIGOPS-OSR)
Proceedings
of the nth ACM symposium on Operating Systems Principles (SOSP)
USENIX
Symposium on Operating Systems Design and implementation (USENIX)
Course Modules & Suggested Readings:
|
1. Introduction to Operating
Systems and their evolution: 03
Contact
Hrs |
|
Layered View of a Computing System, Design Goals of Operating System, Evolution of Operating System, Batch Processing, Multi programming, Timesharing.
Suggested Reading: (a). [Stalling] Sections 2.1 to 2.4
(b).
(c). [Tanenbaum] Section 1.1 to 1.3
(d). S. Rosen, Electronic Computers: A Historical
Survey, ACM Computing Surveys, Vol.1 No.1 (March 1969) (e). P. J. Denning, Third Generation Computer System, ACM Computing Surveys, Vol.3 No.34 (Dec. 1971) (f). A. Moumina, History of Operating Systems
|
|
2. Structure
& Functions of Operating System:
03 Contact Hrs. |
|
Operating System as Software, Kernel & Shell, System Calls, Functions of Operating System, System Structure.
Suggested Reading:
(a). [Silberschatz] Chapter 2
(b). [Tanenbaum] Section 1.5 to 1.7
Check your progress (Currently disabled)
|
|
3. Process Management: 04 Contact Hrs. |
|
User Job, Resources, Process Concept, Process Control Block, Process States, State Transition, Context Switching,
Process
Scheduling: Scheduling
Queues, Scheduling Criteria, Scheduling Algorithms; Threads.
Suggested Reading:
(a). [Silberschatz] Section 3.1 to 3.3, 5.1 to 5.7, 4.1 to 4.5
(b). [Stalling] Section 3.1 to 3.4 & 4.1 (c). [Tanenbaum] Section 2.2 (d). P. B. Hansen, The Nucleus of a Multiprogramming System, Communications of ACM, Vol.13 No.4 (April 1970)
(e). M. Ruschizka & R.S. Fabry, A Unifying Approach to
Scheduling,
Communications of ACM, Vol.20
Check your progress (Currently disabled)
|
|
4. Memory Management: 08 Contact Hrs. |
|
Address Binding, Dynamic Loading & linking concepts, Logical & Physical Address, Contiguous Allocation, Fragmentation, Paging, Segmentation, Combined Systems, Virtual Memory, Demand paging, Page fault, Page Replacement & Page Replacement Algorithms, Global vs. Local Allocation, Thrashing, Working Set Model,
Pre-paging.
Suggested
Reading:
(a). [Silberschatz] Chapter
8 & 9
(b). P.J. Denning, Virtual
Memory, ACM Computing Surveys Sep. 1970
(c). P.J. Denning, The Working Set Model for Program Behavior, Communications of ACM Vol.11 No.5 (May 1968) (d). P.J. Denning, Working Sets Past & Present, IEEE Transactions on Software Engineering Vol.SE-6 No.1 (Jan.1980)
Check your progress 1 Check your Progress 2
*****************************
PERIODICAL TEST NO 1 DUE
***************************** |
|
5.
Concurrent Processes: 08 Contact Hrs. |
|
Process Interaction: Competition, Cooperation & Message Passing; Mutual Exclusion, Shared Data, Critical Section, Busy Form of Waiting, Lock & Unlock Primitives, Synchronization, Classical Problems of Synchronization, Semaphores,
Monitors,
Conditional Critical Regions.
Suggested Reading:
(a). [Stalling] Chapter 5
(b). L. Lamport, The Mutual Exclusion Problem,
Journal of ACM, Vol.33 No.2 (1986) (c). L. Lamport, The Mutual Exclusion Problem has been Solved, Communications of ACM, Vol.34 No.1 (Jan. 1991) (d). E.W. Dijkstra, Cooperating Sequential Processes, Technical Report EWD-123 Technological University Einahoven
The Netherlands (1965) (e). E.W. Dijkstra, Solution of a Problem in Concurrent Programming Control, Communications of ACM, Vol.8 No.9 (Sep.1965)
(f). L. Lamport, Concurrent
Reading and Writing, Communications of ACM, Vol.20 No.11 (Nov. 1977)
(g). P. B. Hansen,
Concurrent Programming Concepts, ACM
Computing Surveyes Vol.5 No.4 (Dec. 1973) (h) C. A. R. Hoare, Monitors: An Operating System Structuring Concept, Communications of ACM, Vol.17 No.10
(Oct. 1974) erratum Vol.18 No.2 (Feb.1975)
Check your progress
|
|
6.
System Deadlock: 03 Contact
Hrs. |
|
Necessary Conditions, Resource Allocation Graph, Wait for Graph, Deadlock Handling methods: Prevention, Avoidance,
Detection & Recovery.
Suggested Reading:
(a). [Silberschatz] Chapter
7 (b). E.W. Dijkstra, Cooperating Sequential Processes, Technical Report EWD-123 Technological University Einahoven
The Netherlands (1965) (c). R.C. Holt, Some Deadlock Properties of Computer Systems, ACM Computing Surveys Vol.4 No.3 (Sep.1972)
(d). J.W. Havender, Avoiding
Deadlocks in Multitasking Systems, IBM Systems Journal Vol.7 No.2 (1968) (e). A.N. Haberman, Prevention of System Deadlocks, Communications of ACM Vol.12 No.7 (July 1969) (f). E.G. Coffman M.J. Elphick & A. Shoshani, System Deadlocks, ACM Computing Surveys Vol.3 No.2 (June 1971)
(g). S. Isloor & T.
Marsland, The Deadlock Problem: An Overview, Computer Vol.13 No.9 (Sep.1980)
Check your progress
|
|
7. File Management: 04 Contact Hrs. |
|
File Concept, File Attributes, File Types, Operations on Files, Access Methods, Directory Structure,
File System Organization & Mounting,
Allocation Methods, Free Space Management.
Suggested Reading:
(a). [Silberschatz] Chapter 10 & 11
(b). USENIX Association Proceedings of File System Workshop. (c) FAT32 and NTFS
Check your progress
|
|
8. Disk Structure & Scheduling: 02 Contact Hrs. |
|
Disk
Structure, Logical & Physical View, Disk Head Scheduling, Formatting, Swap
Space Management.
Suggested Reading:
(a). [Silberschatz] Section 12.1 to 12.6 (b). R. Geist S. Daniel, A Continuum of Disk Scheduling Algorithms, ACM Transactions on Computer Systems Vol.5No.1 (Feb.1987) (c). T.J. Teorey & T.B. Pinkerton, A Comparative Analysis of Disk Scheduling Policies, Communications of ACM Vol.15 No.3 (March 1972) (d). B.L. Worthington G.R. Ganger & Y.N. Patt, Scheduling Algorithms for Modern Disk Drives, Proceedings of 1994 ACM Sigmetrics Conference on Measurement & Modeling of Computer Systems May 1994
Check your progress
|
|
9. Protection
& Security: 02
Contact Hrs. |
|
Goals of Protection, Access Matrix, Capability based systems, The Security
Suggested
Reading:
a. [Silberschatz] Chapter 17 & 18
Check your progress
|
|
10.
Case Studies & Miscellaneous
Topics: 03
Contact
Hrs. |
|
UNIX/ LINUX & Windows as Example Systems, UNIX-C Interface, UNIX Shell Programming, Recent trends in Operating Systems, Current areas of research in Operating Systems.
Suggested
Reading:
a. [Silberschatz] Chapter 21 & 22
b. [Bach]
c. [Mukhi]
d. Cooke et al, UNIX and Beyond, An interview with Ken Thompson
Check your progress
|
1. Write a C program to print the schedule for the following example using FCFS, SJF and RR Scheduling Algorithm.
Also compute the average turnaround and waiting times.
|
Process |
Arrival Time |
Burst Time |
|
P1 |
0 |
8 |
|
P2 |
1 |
4 |
|
P3 |
2 |
9 |
|
P4 |
3 |
5 |
2. Write a C program to implement FIFO Page replacement algorithm. The program should compute the number of page
faults for a given page reference string with a given number of frames. Assume local allocation/ replacement policy is used.
3. The Sleeping - barber Problem : A barbershop consists of a waiting room with n chairs and a barber room with n chairs and a
barber room with one barber chair. If there are no customers to be served, the barber goes to sleep. If a customer enters the
barbershop and all chairs are occupied, then the customer leaves the shop. If the barber is busy but chairs are available, then
the customer sits in one of the free chairs. If the barber is asleep, the customer wakes up the barber. Write a program to
coordinate the barber and the customers.
4. Write a multithreaded program that implements the Banker's algorithm for Deadlock Avoidance. Create n threads that
request and release resources from the bank. The banker will grant the request only if it leaves the system in a safe state.
Use either Pthreads or Win32 threads. Access to shared data should be safe from concurrent access.
Final/ Semester End Examination is expected to be held sometime around Third week of March' 2008.
The question papers for previous years can be downloaded from the link given below
|
|
||
|
(PDF Files, Acrobat Reader will be required to view these files) |
||