CS 111
Operating Systems

Winter 2016
Taught by: Paul Eggert
Scribe Notes written by: Marvin McClain Jr.

Lecture I - January the 4th, 2016


=======

Red Star 3.0 - An operating system developed in North Korea.
This operating system has been recently reverse-engineered.
It has been found to be merely a derivative of the Fedora operating system, albeit with a GUI that resembles OS X by Apple Inc.

One feature of Red Star 3.0 is the automatic watermarking of files.
This creates a hidden signature onto files that have been accessed by the operating system.
The practice of concealing information in this way, within computer data, is known as steganography.

Another feature of Red Star 3.0 forces tamper-resistant software installation of any programs onto the operating system.
This is an example of an OS modification.
The North Korean developers of Red Star 3.0 do not allow for unauthorized modifications to their operating system.
Only a number of "approved" programs are allowed to be installed by the OS kernel.

=======

For this course:

The Prerequisites for CS 111 include:
CS 32 - C++ Programming (as well as the even more superior programming language, known simply as C ;-) )
CS 33 - Machine Code, Assembly Language - How to read it, how to debug code written in it.
CS 35L - Software Constrution - Linux shell commands, scripting, etc.

Courses that are also helpful to have taken prior to CS 111 include:
CS M151B - Computer Architecture
CS 131 - Programming Languages
CS 118 - Networking

Unfortunately, many of the helpful courses listed above have CS 111 listed as requisites...
So it would be a little difficult to have taken them prior to this course ;-) .

According to the Registrar's website, the workload breakdown of CS 111 is as follows:
4 hours of lecture;
2 hours of lab; and
9 hours of outside study.

But... realistically...
Lab!? What lab? This course, in reality, has discussions, not labs. And also...
Only 9 hours of outside study? Prof. Eggert finds this low number laughable!

The following is a more accurate reflection of what the workload breakdown will really entail:
3.7 hours of lecture;
1.7 hours of lab discussion; and
n hours of outside study, where n is any number much, much larger than 9.

Of course, your mileage may vary-- the amount of time spent studying and working on CS 111 coursework will depend on:
- Amount of prior knowledge/experience in computer programming/OS design; and
- How well you retained the material presented in CS 35L (or whatever equivalent course you took for the university you transfered from).

The course webpage may be found HERE.

=======

The title of the course textbook is Principles of Computer System Design,
by Saltzer & Kaashoek.

The assigned readings from the course textbook, to be fully read, re-read, and comprehended, prior to the following lecture, consist of:
- All of Chapter 1; and
- Chapter 2, Sections 1 through 3.

This course will be organized and graded as follows:
- 17 total lectures;
- 1 midterm, held during lecture time, on February the 3rd. You are given 100 minutes to complete it, and it's worth 1/9 of the total grade;
- 1 final exam, 180 minutes long, worth 2/9 of the total grade;
- 4 labs, which can be completed individually, or in teams of two:
Each lab is worth 1/12 of the total grade, for a grand total of 1/3 the total grade.
The labs are somewhat tentative, but they will focus on the following areas:
	- Writing a shell;
	- Kernel hacking;
	- File system code; and
	- Networking code.
- 2 minilabs, which must be done individually:
These are smaller, more focused labs. Each one is worth 1/15 of the total grade, for a grand total of 2/15 of the total grade.
These minilabs will focus on the following areas:
	- Scheduling; and
	- Virtual memory.
- A design problem, considered an extension of one of the labs (of your choice):
You build on one of the labs, using one of the suggestions given in the lab spec, or create one of your own (with your TA's approval).
The design problem requires a written report. Like the labs, these can also be done in groups of 2.
This is worth 1/12 of the total grade;
- 1 Two- to Three-page paper, written on the subject of a contemporary operating system topic of your choosing, worth 1/15 of the total grade; and
- Scribe notes of a lecture of your choosing. This can be done in groups of up to 4 students, and is due a week after your chosen lecture.
Worth 1/20 of the total grade. (All the fractions in bold should add up to 1 :-) )

The exam guidelines for this course is as follows:
OPEN BOOK, OPEN NOTES. But that doesn't mean that the exams will be easy!
You must apply what you've learned through the text and your notes in order to do well!

The lateness penalty for assignments in this course are:
A loss of 2^(n - 1) points for each day (24-hour period) an assignment is submitted after the due date.
The deadline will always be at 11:55 PM; if you submit at 11:56, it's still considered a day late!
This penalty system is forgiving if you're submitting an assignment ; However, the penalty gets steeper the more days that go by.
After a week, don't even bother submitting--you'd get negative points for your submission! You wouldn't want to hurt your grade in the course, would you!?

Just kidding... You'd just get no points for the assignment at all. Which I guess would hurt your total grade also.

=======

The following is a quote taken from The Economist, some obscure European magazine:

"We don't offer a ready-made program, but an entire operating system." - Marina Weisband, member of Germany's Pirate Party
The entire article may be found HERE, for those who are adventurous.

It is a curious sight indeed to witness politicians using computer science terminology...
Marina Weisband mentioned the term operating system, which, incidentally, is the focus of this course. However...
It'd probably be more accurate to say that the focus of this course is operating system !

=======

So, what exactly is a system? How is it defined?

The Oxford English Dictionary (1928 Volume) states the following:
"I. An organized or connected group of objects.
 II. A set of principles, etc., a scheme, a method."

Fun fact: J.R.R. Tolkien was one of the editors of this edition of the OED! :-D

- When 'etc.' is used in a definition, that typically means that the writers weren't sure how to define the word either. ^_^
- Scheme? Method!? Aren't these computer science terms?!?
How could the writers, back in 1928, know to use those terms when they came up with the definition for a system?
Were they perhaps visited by... computer engineers from the future?
Of course not!
It is us, the modern-day computer engineers, who have taken these terms from them!

The course textbook has its own definition of system--Here it is:
"A set of interconnected components that has a specified behavior, observed at the interface with its environment."
	Think of a system as a large (or maybe small) set of individual pieces, working together.
	Outside of the system is the environment that it runs in.
	The system has a membrane, or skin, separating it from its environment. 
		This is called its interface.
	For a person also within the environment, the system cannot be seen; 
		only the interface can been seen and interacted with.
The word system comes from the Greek word sistema (spelled σύστημα). Its original meaning is:
"Organized whole, government, constitution, a body of people or animals, a musical interval..."
- The root itself is Indo-European in origin, meaning "set up with".
- These early ideas of a system seem to indicate a sort of arrangement, or design.
- Well, that's exactly what the modern-day, computer science version of system means!
- It, essentially, is the ways to arrange software (by using an operating system) on a computer!

=======

Well then, what is an operating system?

The American Heritage Dictionary (2000 Edition) states the following:
"Software design to control the hardware of a specific data processing system, in order to allow users and application programs to make use of it."

- Control seems to be the key word here.
- The use of the word hardware is outdated slightly, as operating systems are designed to control software as well as hardware these days.
- The word specific is definitely outdated;
Gone are the days when operating systems were tailor-made to run on specific hardware... They're much more portable now.
- Users and application programs (commonly known in the 21st Century simply as apps) do indeed still make use of OSes.

Let's look at another definition... from the mind of Bill Gates himself! As stated in the Encarta Encyclopedia (2007 Edition):
"The master control program in a computer."

There goes that word control again! That seems to be a pattern...
Finally, let's have a look at what Wikipedia says on its 'Operating system' page (v.698216816, 2016-01-04):
"A collection of smaller programs and software that is used to control and operate the computer system."

You know a definition is lousy when it uses the exact term (operate) that it attempts to define! And, once again, the word control appears.
This seems to be a consistent depiction of what an OS does, from across time.
But it's wrong!
Control is NOT the focal point of operating systems--especially now, in the 21st Century.

Here are some major missing issues in all of the definitions of operating system mentioned above:
- Resource Management (keeping track of memory, processes, etc., and regulating resources between users);
- Reliability & Error Handling (because the bulk of time and energy spent coding is on errors and debugging, not the actual feature implementations);
And lastly,
- Security !

=======

Here are some problem areas in OS design:

- Incommensurate Scaling: Not everything scales at the same rate! Extensional files, for example, don't scale nearly as well as intensional ones!
	Economies of Scale would be a good example of incommensurate scaling:
	The cost per unit of an item grows down as the system grows.
	In Adam Smith's scenario, there are a village of self-sufficient people.
	If any one of the villages desired a pin, they would have to cut a wire and sharpen it manually each time.
	It would be much "cheaper" to have one villager (a blacksmith) that mass produces pins for all of the villagers.
	Unfortunately, the downside to this scenario is that it can cause waste if too many pins are created.
	
	Diseconomies of Scale is another example:
	The cost per unit of an item grows up, not down, as the system grows.
	An example of this would be a star network.
	The downside to this idea is that it can cause breakage.
- Emergent Properties: Larger systems have properties that smaller prototypes don't!
	The Tacoma Narrows Bridge disaster is an example of an emergent property
		manifesting itself with increases in scale.
	The bridge was built to the most advanced engineering specifications of the day.
	However, the designers did not account for the resonance effects of multiple gusts of wind,
		blowing against the bridge, one after the other.
	These effects were negligible in the smaller prototypes of the bridge, but they had to be
		accounted for in the full-sized version.
		
	Operating systems, of course, are much more complicated than bridges...
	Plus, the OS attackers have "wind generators" ;-) .
	
	A significant episode of emergent properties occurred right here at UCLA!
	The internet access newly made available for students in the dorms (this was around the year 2000),
		became quickly overrun with music pirating using Napster!
- Propagation of Effects:
	A number of years ago, Microsoft endeavored to create a file system that accepted Japanese characters as filenames.
	Their first attempt failed--due to the Shift JIS character encoding used on Japanese computers.
	This encoding used two bytes to represent characters. Each byte, individually, appeared very similar to an
		ASCII character, except that the most significant bit in the first byte was a 1.
	Ex of Shift JIS: 11001010 | 01011001 . The most significant bit is a 1. This denotes a Japanese character.
	
	However, Microsoft Windows only recognized the second byte (which has a leading zero like ASCII). This led
		to Japanese files and directories being mis-named and lost on the system!
	This led to Microsoft's switch to UTF-8 character encoding, which is still used today. This compromise leads
		to the next problem area in OS design,
- Tradeoffs:
	UTF-8 requires 3 bytes instead of 2, which makes it slightly more expensive.
	Filenames take up more disk space when UTF-8 encoding is used.
	But it's necessary to ensure that filenames in Windows written in other languages are interpreted
	correctly by the OS.

	Another example exists in the realm of security: the use of 2-factor authentication.
	This can occur by requiring both a password as well as a key fob (providing RSA encryption), rather than relying solely on passwords.
	But what if a user's key fob gets lost? Or... it gets programmed wrong!? Or..... the batteries fail!?!?!
	This is yet another tradeoff! Extra security vs. the risk of something going wrong with the key fob.

Remember to read Chapter 1 and Chapter 2.1-2.3 of the textbook before moving on the next lecture! Thanks for reading!

=======

Sources/HTML Links:
Red Star OS, Wikipedia, https://en.wikipedia.org/wiki/Red_Star_OS
Fedora (operating system), Wikipedia, https://en.wikipedia.org/wiki/Fedora_(operating_system)
Steganography, Wikipedia, https://en.wikipedia.org/wiki/Steganography
Everything is connected: Can internet activism turn into a real political movement?, The Economist,
http://www.economist.com/news/briefing/21569041-can-internet-activism-turn-real-political-movement-everything-connected
Star network, Wikipedia, https://en.wikipedia.org/wiki/Star_network
Shift JIS, Wikipedia, https://en.wikipedia.org/wiki/Shift_JIS
UTF-8, Wikipedia, https://en.wikipedia.org/wiki/UTF-8

BACK TO TOP