Transcript Introduction - BYU Computer Science Students Homepage Index

CS 345 – Operating Systems

Winter 2017


Section 001, 11:00 – 11:50 am MWF
130 MARB

Instructor: Paul Roper
Office: TMCB 3370, 422-8149
Email: [email protected]

Office Hours: 9-10:50 am MWF
BYU CS 345
Introduction to Operating Systems
1
Monday, January 9, 2017

National Apricot Day

Announcements…


“Operating Systems Internals and Design
Principles” by William Stallings, 6th (or later)
edition, Chapters 1-12
http://students.cs.byu.edu/~cs345ta/








Information
Syllabus
Schedule
Content: slides, homework
Projects
Presentations
Reference
Learning Suite Grades
BYU CS 224
Introduction to Computer Systems
2
William Stallings
• Authored 17 titles, and counting revised editions, a total of 40 books on
various aspects of these subjects.
• In over 20 years in the field, he has been a technical contributor, technical
manager, and an executive with several high-technology firms.
• Currently he is an independent consultant whose clients have included
computer and networking manufacturers and customers, software
development firms, and leading-edge government research institutions.
• Bill has designed and implemented both TCP/IP-based and OSI-based
protocol suites on a variety of computers and operating systems, ranging
from microcomputers to mainframes.
• He has received the award for the best Computer Science textbook of the
year from the Text and Academic Authors Association three times.
• Dr. Stallings received his B.S. in electrical engineering from University of
Notre Dame and his PhD in computer science from Massachusetts Institute
of Technology.
BYU CS 345
Introduction to Operating Systems
3
Prerequisites




CS 124, CS 235, CS 236, CS 240.
CS 345 is a recommended prerequisite to
CS 360.
Knowledge of C.
Or, instructor’s consent.
BYU CS 345
Introduction to Operating Systems
4
CS 345 Learning Outcomes


CS 345 is an introduction to the principles underlying the
design and the implementation of contemporary computer
operating systems.
At the end of the course, the student should have…





Demonstrated a basic understanding of design and
implementation issues of an operating system by
implementing a cooperative OS.
Discussed, analyzed, and implemented many of the
concepts of process, multithreading, symmetric
multiprocessing, and microkernels.
Implemented memory management techniques,
including virtual memory.
Programmed various approaches to process scheduling.
Programmed an OS management of files.
BYU CS 345
Introduction to Operating Systems
5
Organization and Grading

Weighted contribution to your final grade:




Homework/Quizzes: 10%
Programming Labs: 55%
Midterm Exams: 20%
Presentation / Final: 15%
A
AB+
B
BC+
BYU CS 345
=
=
=
=
=
=
93%
90%
87%
83%
80%
77%
Introduction to Operating Systems
C =
C- =
D+ =
D =
D- =
E =
73%
70%
67%
63%
60%
below 60%
6
Homework / Quizzes (10%)




Homework assignments are designed to reinforce class
material and help in exam preparation.
Homework is assigned for every 4 lectures and is due at
the beginning of class.
Any homework submitted after the due date will lose 50%
per week.
You are welcome and encouraged to discuss the
homework with your classmates and others. However, you
are to do and submit your own work. Submitting
someone's work is considered cheating for which you will
receive an E grade for the class and be reported to the
Honor Code Office.
BYU CS 345
Introduction to Operating Systems
7
Programming Assignments




Programming assignments can be found on the CS345
web site (http://students.cs.byu.edu/~cs345ta/).
The programming assignments build upon each other.
Programming assignments must be passed off by a TA
during regular TA hours in the TA offices or class
programming labs.
Programming assignments can be passed off on school
computers or personal laptops.
BYU CS 345
Introduction to Operating Systems
8
Programming (continued…)



To receive full credit, programming assignments must
be completed and passed off with a “Date Modified”
timestamp on or before the due date.
 NOTE: Timestamps cannot be used for extra credit
points and cannot be more than two days delinquent.
Any assignment completed and passed off after the due
date will lose 10% per school day. (After 2 weeks, an
assignment has no grading value!).
As an incentive to get your assignments done early,
assignments passed off at least one day before the
due date (timestamps do not count) with a TA, will
receive an additional 10% extra credit.
BYU CS 345
Introduction to Operating Systems
9
Programming (continued…)




All six programming assignments must be completed to
receive and “A” or “A-” grade.
Everyone who completes all six programming
assignments (regardless of their scores) and passes the
final exam (non-normalized 70% or better) will pass the
class with at least a “C-” grade.
Any grade points earned on assignments above the
allotted percentage may apply to your overall grade.
All assignments MUST BE COMPLETED, PASSED
OFF AND SUBMITTED on or before the final day of
class.
BYU CS 345
Introduction to Operating Systems
10
Midterm Exams (20%)




Two midterms will be administered during the course of
the semester.
Midterm exams will be administered in the testing center
and be available from Friday until closing on Saturday.
You should plan at least 1-2 hours for each exam.
Any exam taken after the scheduled exam days will be
worth (at maximum) half credit unless prior
arrangements have been made with the instructor.
BYU CS 345
Introduction to Operating Systems
11
Presentations (15%)


At the end of the semester, each student (in a small
group setting) is given the opportunity to present a
specific OS topic with respect to an assigned
contemporary operating system.
Your presentation will be peer graded and should be




complete (ie., self-contained, concise, relevant, adequately
addressed topic),
insightful (ie., researched, thoughtful, shows effort), and
presented well (ie., materials, slides, handouts, examples, stage
presence, well organized, intro/summary).
Your presentation along with submission of your OS
source code will be the final exam for the course.
BYU CS 345
Introduction to Operating Systems
12
CS 345 Overview
Stalling’s Chapter
#
Project
1: Computer System Overview
2: Operating System Overview
4
P1: Shell
3: Process Description and Control
4: Threads
4
P2: Tasking
5: Concurrency: ME and Synchronization
6: Concurrency: Deadlock and Starvation
6
P3: Jurassic Park
7: Memory Management
8: Virtual memory
6
P4: Virtual Memory
9: Uniprocessor Scheduling
10: Multiprocessor and Real-Time Scheduling
6
P5: Scheduling
11: I/O Management and Disk Scheduling
12: File Management
6
P6: FAT
Student Presentations
8
BYU CS 345
Introduction to Operating Systems
13
Lab Grading

Programming Labs: (55%)






Lab 1: Shell (CLI) – 7%
Lab 2: Tasking – 10%
Lab 3: Jurassic Park – 10%
Lab 4: Virtual Memory – 10%
Lab 5: Scheduling – 6%
Lab 6: FAT – 12%


BYU CS 345
FAT 1 – 4%
FAT 2 – 8%
Introduction to Operating Systems
14
OS345 Labs


Lab 1: Shell. Write a Shell (Command
Language Interpreter) to parse textual
commands entered from the user’s keyboard,
malloc argument variables, handle signals, and
execute programs directly or as child processes.
Lab 2: Scheduler. Write a five-state task
scheduler capable of simultaneously executing
up to 128 tasks in a preemptive, prioritized,
round-robin manner. Implement binary and
counting semaphores and schedule your CLI as
its first task with pseudo-interrupt driven
character input. Add timer semaphores and
tasks to validate your implementation.
BYU CS 345
Introduction to Operating Systems
15
OS345 Labs

Lab 3: Jurassic Park. Jurassic Park is an interprocess communication and synchronization
problem between multiple tasks. Visitors to the
park purchase a ticket, wait to take a ride on a
park tour car to see the dinosaurs, and then visit
the museum and gift shops before leaving the
park. Since the park is on a limited budget,
drivers must perform double duty when not
sleeping by selling tickets and driving the tour
cars. Visitors, drivers, and cars are represents
by concurrent tasks while an additional task is
used to display the park status every second.
BYU CS 345
Introduction to Operating Systems
16
OS345 Labs

Project 4: Virtual Memory. Add a Memory
Management Unit (MMU) to your OS that
translates virtual LC-3 addresses to physical
addresses in a restricted memory space.
Validate your implementation by successfully
executing up to 10 LC-3 crawler and/or memory
test programs concurrently in 2 frames of
physical memory (128 words).
BYU CS 345
Introduction to Operating Systems
17
OS345 Labs

Lab 5: FSS Scheduling. Add a Fair Share
Scheduler (FSS) to your OS scheduler to
maximize overall CPU utilization while also
maximizing interactive performance. Instead of
using run queues, implement a “fair” timeline of
future task execution.
BYU CS 345
Introduction to Operating Systems
18
OS345 Labs

Lab 6: FAT File Manager. Add a MS-DOS®
FAT-12 file manager to your OS that is able to
traverse file directories, view file data, and
load/execute LC-3 programs from files.
Implement creation, access, and modification of
FAT-12 files by adding file manager functions
and commands that use file system buffering,
basic file I/O, file descriptors, and file pointers to
modify file allocation tables (FAT), directory
structures and cluster chains.
BYU CS 345
Introduction to Operating Systems
19
Miscellaneous









Programming Environments
CS Retake Policy
Academic Honesty
TA’s
Help sessions
Office hours
Student manual
Linux vs Microsoft users
Questions?
BYU CS 345
Introduction to Operating Systems
20
Why CS 345?
BYU CS 345
Introduction to Operating Systems
21
“345 was the first class I took where I felt motivated and
capable (in a CS class) of learning new things quickly. It genuinely
was a turning point for me as a student.
“… applied to the Goldman Sachs technology division, and they
asked me non-stop about CS 345. Well I got a full-time job
offer…”
“… I recently took part in a grueling 3 hour job interview for a
local startup company. The coveted prize was a paid internship
that came with training for my future career as a software
engineer. … Questions were asked about processes/threads,
virtual memory, and scheduling, all three of which are key
components of the operating systems class on campus.”
BYU CS 345
Introduction to Operating Systems
22
“… OSes are the most used pieces of software on any computer,
and being familiar with how they work under the hood is an
essential for anyone who wants to have a successful career in
software development.”
“… Not all CS classes currently in the program are beneficial to all
students' future careers in software development, but I argue
that operating systems is actually very useful to all students
hoping to develop software professionally. … the OS class an
elective ... a great disservice to any CS student hoping to advance
a career in industry and will leave him/her to learn the necessary
OS material later on in their careers, while others competing for
the same jobs will have already learned the material during their
undergraduate studies.”
BYU CS 345
Introduction to Operating Systems
23
Operating Systems

What is an operating system?


Hard to define precisely, because operating systems
arose historically as people needed to solve
problems associated with using computers.
How about…
“Software that makes computing power available to
users by controlling the hardware.”
“Software executes when nothing else is
happening.”
“A collection of software modules including device
drivers, libraries, and access routines.”
BYU CS 345
Introduction to Operating Systems
24
What Does a Modern OS Do?

Provides Abstractions:





Hardware has low-level physical resources with
complicated, idiosyncratic interfaces.
OS provides abstractions that present clean interfaces.
Goal: make computer easier to use.
Examples: Processes, Unbounded Memory, Files,
Synchronization and Communication Mechanisms.
Provides Standard Interface:


Goal: portability.
Unix runs on many very different computer systems.
BYU CS 345
Introduction to Operating Systems
25
What Does a Modern OS Do?

Mediates Resource Usage:


Goal: allow multiple users to share resources fairly,
efficiently, safely and securely.
Examples:





Multiple processes share one processor. (preemptable
resource)
Multiple programs share one physical memory (preemptable
resource).
Multiple users and files share one disk. (non-preemptable
resource)
Multiple programs share a given amount of disk and network
bandwidth (preemptable resource).
Consumes Resources:

Solaris takes up about 8 Mbytes physical memory (or about
$400).
BYU CS 345
Introduction to Operating Systems
26
The Future…




In the future, computers will continue to become
physically smaller and more portable.
Operating systems have to deal with issues like
disconnected operation and mobility.
Media rich information within the grasp of
common people - information with psuedo-real
time components like voice and video.
Operating systems will have to adjust to deliver
acceptable performance for these new forms of
data.
BYU CS 345
Introduction to Operating Systems
27
Finally



Operating systems are so large no one person
understands whole system. Outlives any of its
original builders.
The major problem facing computer science
today is how to build large, reliable software
systems.
Operating systems are one of very few
examples of existing large software systems,
and by studying operating systems we may
learn lessons applicable to the construction of
larger systems.
BYU CS 345
Introduction to Operating Systems
28
BYU CS 345
Introduction to Operating Systems
29
CS 345
Course Overview
Introduction
Course Information

Required Text: “Operating Systems Internals and
Design Principles” by William Stallings



User CS 345 Web Site
 http://students.cs.byu.edu/~cs345ta/


Syllabus, schedule, projects, homework
Learning Suite Grades



6th (or later) edition
Chapters 1-12
Verify scores
DO NOT USE GRADES GRADING SYSTEM!
Complete assigned reading and attend class!
BYU CS 345
Introduction to Operating Systems
32
Syllabus


Computer Science 345 is an
introduction to the principles underlying
the design and the implementation of
contemporary computer operating
systems.
Class designed for students majoring in
Computer Science or in areas having a
strong emphasis in Computer Science.
BYU CS 345
Introduction to Operating Systems
33
Syllabus (continued…)

At the end of the course, the student should have
a basic understanding of:








Design and implementation issues of contemporary
operating systems
Detailed analysis of process, multithreading,
symmetric multiprocessing, and microkernels
Memory management techniques, including virtual
memory
Various approaches to process scheduling
Operating system control of Input/Output
Operating system management of files
Distributed systems
Computer security
BYU CS 345
Introduction to Operating Systems
34
Programming Environments…



Programming of the assignments will be
done in the C programming language.
The choice of the software tools and
programming environment is left to the
student’s discretion.
In any case, it is the student’s
responsibility to present their work to a
TA in the designated CS 345 lab for
pass off. (Downstairs TMCB)
BYU CS 345
Introduction to Operating Systems
35
Programming Environments (continued…)



Windows users can download a very good free C
compiler at the LCC website
(http://www.cs.virginia.edu/~lcc~win32/).
For those wanting to use Linux on their personal
computers, look at the KNOPPIX website
(http://www.knoppix.net/) for a free Linux system
bootable from CD ROM.
For those who do not own a computer or would
just rather do their work using BYU facilities, there
are Linux/Unix labs available in the Computer
Science building using the gcc compiler.
BYU CS 345
Introduction to Operating Systems
36
Grade Verification and Appeals



It is the student’s responsibility to verify that
scores have been correctly recorded in
Gradebook.
Until further notice, do not use Gradebook’s
grading system (including maximum points).
The student can appeal a grade on an exam
directly to their instructor through email.
BYU CS 345
Introduction to Operating Systems
37
Academic Honesty



Academic honesty includes completing your
own homework, labs, midterms, and final.
Students should work together to help each
other understand material, but should always
turn in their own work.
Examples of academic dishonesty include
sharing code for labs with other students,
turning in someone else's writing as your own
report, and cheating on an exam.
BYU CS 345
Introduction to Operating Systems
38
Academic Honesty


The first violation of academic honesty
standards will result in the student failing the
class.
All violations of academic honesty are
documented and reported to the Honor Code
office.
BYU CS 345
Introduction to Operating Systems
39
Grades (continued…)

Grades are assigned on the following
scale from the composite total of above
areas:
BYU CS 345
100-93 A
82-80 B-
69-67 D+
92-90 A-
79-77 C+
66-63 D
89-87 B+
76-73 C
62-60 D-
86-83 B
72-70 C-
59-0 E
Introduction to Operating Systems
40
William Stallings
William Stallings has authored 17 titles, and counting revised editions,
a total of 40 books on various aspects of these subjects. In over 20
years in the field, he has been a technical contributor, technical
manager, and an executive with several high-technology firms.
Currently Bill is an independent consultant whose clients have included
computer and networking manufacturers and customers, software
development firms, and leading-edge government research
institutions. He has designed and implemented both TCP/IP-based
and OSI-based protocol suites on a variety of computers and
operating systems, ranging from microcomputers to mainframes. As
a consultant, he has advised government agencies, computer and
software vendors, and major users on the design, selection, and
use of networking software and products.
Dr. Stallings holds a PhD from M.I.T. in Computer Science and a B.S.
from Notre Dame in electrical engineering.
BYU CS 345
Introduction to Operating Systems
41