Transcript Course Overview

CS-213
Introduction to Computer
Systems
Aleksandar Kuzmanovic
3/27/2006
Topics:



Staff, text, and policies
Lecture topics and assignments
Class overview
CS 213 S ’06
Teaching staff

Instructor
 Prof. Aleksandar Kuzmanovic (Wed 10:00-12:00, Tech L457)

TA
 David Choffnes (Tu, Th 1-2:30, Ford 2-217)
 Recitation (Tu, 5-6:30, Tech MG28)

Undergraduate assistant
 TBA (TBA)

Location and Time
 Lecture: MW 2-3:20, Tech LR3
 Recitation: Tu, 5-6:30, Tech MG28
–2–
CS-213, S’06
Prerequests

CS211 (Fund. of comp. program.) or eq.
Experience with C or C++
CS311 (Data structures and mgmt)

CS213 is required CS course


Required
Required
Useful
 It is prerequisite for CS 343 (Operating Systems)
 It is also prerequisite for ALL systems courses
» See http://nsrg.cs.northwestern.edu for a current list
–3–
CS-213, S’06
Textbooks
Required:
Randal E. Bryant and David R. O’Hallaron,


“Computer Systems: A Programmer’s Perspective”, Prentice
Hall 2003.
csapp.cs.cmu.edu
Recommended:
Brian Kernighan and Dennis Ritchie,

“The C Programming Language, Second Edition”, Prentice
Hall, 1988
Richard Stevens,

–4–
“Advanced Programming in the Unix Environment”,
Addison-Wesley, 1992
CS-213, S’06
Homeworks, Labs, and Exams

4 labs, 4 homeworks, 2 exams
 Grading




10% Homeworks (2.5% per homework)
50% Programming labs (12.5% per lab)
20% Midterm (covers first half of the course)
20% Final (covers second half of the course)
 Final grades: >90 (or 90th percentile): A


>80 (or 80th percentile): B,
>70 (or 70th percentile): C, etc.
 Late Policy


–5–
After 1 day, maximum score is 90%
After 2 days, maximum score is 80%, etc.
CS-213, S’06
Policies: Assignments
Work groups

You must work in groups of 2 for all labs
 Let me and the TA know the groups by the end of the week
Handins


–6–
Assignments due at 11:59pm on specified due date.
Electronic handins only.
CS-213, S’06
Course Components
Lectures

Higher level concepts
Recitations

Applied concepts, important tools and skills for labs,
clarification of lectures, exam coverage
Labs




–7–
The heart of the course
1 or 2 weeks
Provide in-depth understanding of an aspect of systems
Programming and measurement
CS-213, S’06
Getting Help
Web



http://cs.northwestern.edu/~akuzma/classes/CS213-s06/
Copies of lectures, assignments, handouts
Clarifications to assignments
Newsgroups




cs.213.announce and
cs.213.discuss
Clarifications to assignments, general discussion
Can’t reply immediately!
Personal help


–8–
Professor, Wednesdays 10-noon
TA: Tu, Th 1-2:30
CS-213, S’06
Cheating
What is cheating?

Sharing code: either by copying, retyping, looking at, or
supplying a copy of a file.
What is NOT cheating?



Helping others use systems or tools.
Helping others with high-level design issues.
Helping others debug their code.
Penalty for cheating:

–9–
Removal from course with failing grade.
CS-213, S’06
Facilities
TLAB (Tech F-252: the Tech end of the bridge that
connects Tech and Ford)
- a cluster of Linux machines
- (e.g., TLAB-11.cs.northwestern.edu)
You should all have TLAB accounts by now;
-if not, contact Scott Hoover ([email protected])
For accessing the TLAB facilities
- contact Carol Surma
([email protected])
Should you have other problems
- contact the TA directly
– 10 –
CS-213, S’06
Programs and Data (8)
Topics


Bits operations, arithmetic, assembly language programs,
representation of C control and data structures
Includes aspects of architecture and compilers
Assignments



– 11 –
L1: Manipulating bits
L2: Defusing a binary bomb
L3: Hacking a buffer bomb
CS-213, S’06
The Memory Hierarchy (2)
Topics


– 12 –
Memory technology, memory hierarchy, caches, disks,
locality
Includes aspects of architecture and OS.
CS-213, S’06
Linking and Exceptional
Control Flow (3)
Topics



– 13 –
Object files, static and dynamic linking, libraries, loading
Hardware exceptions, processes, process control, Unix
signals, nonlocal jumps
Includes aspects of compilers, OS, and architecture
CS-213, S’06
Virtual memory (2)
Topics


Virtual memory, address translation, dynamic storage
allocation
Includes aspects of architecture and OS
Assignments

– 14 –
L4: Writing your own malloc package
CS-213, S’06
I/O, Networking, and
Concurrency (3)
Topics



– 15 –
High level and low-level I/O, network programming, Internet
services, Web servers
concurrency, concurrent server design, threads, I/O
multiplexing with select.
Includes aspects of networking, OS, and architecture.
CS-213, S’06
Lab Rationale
Doing a lab should result in new skills and concepts



– 16 –
Data Lab: computer arithmetic, digital logic.
Bomb Labs: assembly language, using a debugger,
understanding the stack
Malloc Lab: understanding pointers and nasty memory bugs.
CS-213, S’06
Course Theme

Abstraction is good, but don’t forget reality!
Courses to date emphasize abstraction


Abstract data types
Asymptotic analysis
These abstractions have limits


Especially in the presence of bugs
Need to understand underlying implementations
Useful outcomes

Become more effective programmers
 Able to find and eliminate bugs efficiently
 Able to tune program performance

Prepare for later “systems” classes in CS & ECE
 Compilers, Operating Systems, Networks, Computer
Architecture, Embedded Systems
– 17 –
CS-213, S’06
Coarse Goal
Must understand system to optimize performance



How programs compiled and executed
How to measure program performance and identify
bottlenecks
How to improve performance without destroying code
modularity and generality
Implementations change, but concepts don’t
– 18 –
CS-213, S’06
Course Perspective
Most Systems Courses are Builder-Centric

Computer Architecture
 Design a processor

Operating Systems
 Implement large portions of operating system

Compilers
 Write compiler for simple language

Networking
 Implement and simulate network protocols
– 19 –
CS-213, S’06
Course Perspective (Cont.)
This Course is Programmer-Centric

Purpose is to show how by knowing more about the
underlying system, one can be more effective as a
programmer

Enable you to
 Write programs that are more reliable and efficient
 Incorporate features that require hooks into OS
» E.g., concurrency, signal handlers

– 20 –
Cover material in this course that you won’t see elsewhere
CS-213, S’06
Hello World
In a sense, the goal of the course is to help you
understand what happens and why when you run
“hello” on your system?
/*hello world*/
# include <stdio.h>
int main()
{
printf(“hello, world\n”);
}
Goal: introduce key concepts, terminology, and
components
– 21 –
CS-213, S’06
Information is Bits + Context
“Hello” is a source code



Sequence of bits (0 or 1)
8-bit data chunks are called Bytes
Each Byte has an integer value that corresponds to some
character (ASCII standard)
 E.g., ‘#’ -> 35


Files that consist of ASCII characters -> text files
All other files -> binary files (e.g., 35 is a part of a machine
command)
Context is important



– 22 –
The same sequence of bytes might represent a character
string or machine instruction
Machines put everything in bits!
Chapter 2 -> machine representations of numbers
CS-213, S’06
Programs Translated by Other Programs
unix> gcc –o hello hello.c
printf.o
hello.c
Source
program
(text)
Prehello.i
processor
(cpp)
Phases:

Compiler hello.s
(cc1)
Modified
source
program
(text)
Assembly
program
(text)
Assembler hello.o
(as)
Relocatable
object
programs
(binary)
Linker
(ld)
hello
Executable
object
program
(binary)
Pre-processing
 E.g., #include <stdio.h> is inserted into hello.i

Compilation
 hello.s -> each statement is an assembly language program

Assembly
 hello.o -> is a binary file whose bytes encode machine language
instructions

Linking
 E.g., hello.c uses printf(), it resides in a separate precompiled
– 23 –
object file printf.o
CS-213, S’06
Why do We Care about This?
 Optimizing program performance


To write efficient code -> we do need a basic understanding
of how a compiler translates different C statements into
assembly language
How to tune C programs to help compiler
 Understanding link-time errors


Why does it matter what order we list libraries?
Why some link-errors do not appear before run time?
 Avoiding security holes

– 24 –
Buffer overflow bugs
CS-213, S’06
Shell
unix> ./hello
hello, world
unix>
Shell
a command-line interpreter that
- prints a prompt
- waits for you to type command line
- loads and runs hello program
- prints a prompt
– 25 –
CS-213, S’06
Hardware organization
Buses

CPU
Register file

PC
ALU
System bus
Memory bus
Main
memory
I/O
bridge
Bus interface
I/O bus
USB
controller
Mouse Keyboard
– 26 –
Graphics
adapter
Transfer fixed-sized
chunks of data
(WORDS)
Intel Pentium ->
4Bytes bus
Disk
controller
Display
Disk
Expansion slots for
other devices such
as network adapters
hello executable
stored on disk CS-213, S’06
Hardware organization
I/O Devices

CPU

Register file
PC
ALU

System bus
Memory bus
Main
memory
I/O
bridge
Bus interface
I/O bus
USB
controller
Mouse Keyboard
– 27 –
Graphics
adapter
System connections
to external world
Mouse, keyboard
(input)
Display, disk device
(output)
Disk
controller
Display
Disk
Expansion slots for
other devices such
as network adapters
hello executable
stored on disk CS-213, S’06
Hardware organization
Main Memory

CPU

Register file
PC
ALU
System bus
Memory bus
Main
memory
I/O
bridge
Bus interface
I/O bus
USB
controller
Mouse Keyboard
– 28 –
Graphics
adapter
Temporary storage
device
Holds both a
program and the
data it manipulates
with
Disk
controller
Display
Disk
Expansion slots for
other devices such
as network adapters
hello executable
stored on disk CS-213, S’06
Hardware organization
CPU
Register file
PC
ALU
System bus
Bus interface
Control Processor Unit (CPU)


– 29 –
Executes instructions
stored in main memory
Program Counter (PC or
Register) contains the
address of some machinelanguage instruction from
memory
Memory bus
Main
memory
I/O
bridge
CPU



Reads the instruction
from memory
Performs simple
operation (load, store,
update)
Updates the PC to point to
next instruction
CS-213, S’06
Running the Hello Program
Reading the hello command from the keyboard
Register file
PC
ALU
System bus
Memory bus
Main "hello"
memory
I/O
bridge
Bus interface
I/O bus
USB
controller
Mouse Keyboard
– 30 –
Graphics
adapter
Disk
controller
Expansion slots for
other devices such
as network adapters
Display
Disk
User types "hello"
CS-213, S’06
Running the Hello Program
Shell program loads hello.exe into main memory
Register file
PC
ALU
System bus
Memory bus
"hello,world\n"
Main
memory
hello code
I/O
bridge
Bus interface
I/O bus
USB
controller
Mouse Keyboard
– 31 –
Graphics
adapter
Disk
controller
Display
Disk
Expansion slots for
other devices such
as network adapters
hello executable
CS-213, S’06
stored on disk
Running the Hello Program
The processor executes instructions and displays “hello…”
Register file
PC
ALU
System bus
Memory bus
Main "hello,world\n"
memory
hello code
I/O
bridge
Bus interface
I/O bus
USB
controller
Mouse Keyboard
– 32 –
Graphics
adapter
Disk
controller
Display
"hello,world\n"
Disk
Expansion slots for
other devices such
as network adapters
hello executable
stored on disk CS-213, S’06
Caching


A system spends a lot of time moving information from one
place to another
Larger storage devices are slower than smaller ones
 Register file ~ 100 Bytes
 Main memory ~ millions of Bytes

It is easier and cheaper to make processors run faster than it
is to make main memory run faster (SRAM – Static RAM)
CPU chip
Register file
L1
cache
ALU
(SRAM)
Cache bus
L2 cache
(SRAM)
– 33 –
System bus
Bus interface
Memory
bridge
Memory bus
Main
memory
(DRAM)
CS-213, S’06
Storage Devices Form a Hierarchy
Storage at one level serves as cache at the next level
L0:
Registers
Smaller,
faster,
and
costlier
(per byte)
storage
devices
L1:
L2:
L3:
Larger,
slower,
and
cheaper
(per byte)
storage
devices
L4:
On-chip L1
cache (SRAM)
L1 cache holds cache lines retrieved
from the L2 cache.
Off-chip L2
cache (SRAM)
Main memory
(DRAM)
L2 cache holds cache lines
retrieved from memory.
Main memory holds disk
blocks retrieved from local
disks.
Local secondary storage
(local disks)
Local disks hold files
retrieved from disks on
remote network servers.
L5:
– 34 –
CPU registers hold words retrieved from
cache memory.
Remote secondary storage
(distributed file systems, Web servers)
CS-213, S’06
Operating System (OS)
OS – a layer of software interposed between the
application program and the hardware
Application programs
Software
Operating system
Processor
Main memory
I/O devices
Hardware
Two primary purposes


– 35 –
To protect the hardware from misuse by applications
To provide simple and uniform mechanisms for manipulating
low-level hardware devices
CS-213, S’06
OS Abstractions
Files are abstractions of I/O devices
Virtual Memory is an abstraction for the main memory
and I/O devices
Processes are abstractions for the processor, main
memory, and I/O devices
Processes
Virtual memory
Files
Processor
– 36 –
Main memory
I/O devices
CS-213, S’06
Processes
The OS provides the illusion that the program is the
only one in the system
Process

OS’s abstraction of a running program
Context switching


Saving the context of one process
Restoring the process of the new process
Time
shell
process
hello
process
Application code
OS code
Context
switch
Application code
OS code
– 37 –
Application code
Context
switch
CS-213, S’06
Virtual Memory
 Illusion that
each process
has exclusive
use of main
memory
 Example

0xffffffff
0xc0000000
Kernel virtual memory
Memory
invisible to
user code
User stack
(created at runtime)
0x40000000
The virtual
address space
for Linux
Memory mapped region for
shared libraries
printf() function
Run-time heap
(created at runtime by malloc)
Read/write data
Read-only code and data
Loaded from the
hello executable file
0x08048000
– 38 –
0
Unused
CS-213, S’06
Networking
Computers do more than execute programs
They need to get data in and out

I/O system critical to program reliability and performance
They communicate with each other over networks
Because of the Internet, copying info from 1 machine to
another has become important
– 39 –
CS-213, S’06