3 of 51

Why this course?

“An operating system (OS) is a program that manages computer hardware. And although today's commercial-off-the-shelf desktop operating systems appear to be an integral part of PCs and workstation to many users, a fundamental understanding of the algorithms, principles, heuristics, and optimizations used is crucial for creating efficient application software. Furthermore, many of the principles in OS courses are relevant to large system applications like databases and web servers.”

A. Polze (U.Potsdam)

· 3

02.09.2021

OS gives upper layers abstraction over available HW.�learning OS is learning principles of how app is structured.�organization of OS not just relevant for OS, but other large applications.

4 of 51

Computer Hardware

· 4

02.09.2021

AWS EC2 instance types

5 of 51

Why this course?

“C has the power of assembly language and the convenience of … assembly language.”

D. Ritchie

”Learn at least one programming language every year.” A.Hunt and D.Thomas, The Pragmatic Programmer.

· 5

02.09.2021

C is a mess. syntactic sugar on top of assembly (Linus Torvalds quote)�why learn C: to understand how computers work. (C and Linux)

care about security, performance, resource utilization? C gives control.

high-level PLs abstract away many issues.

learn a PL each semester. this semester: C.

6 of 51

Why this course?

The success of the UNIX system stems from its tasteful selection of a few key ideas and their elegant implementation. The model of the Unix system has led a generation of software designers to new ways of thinking about programming. The genius of the Unix system is its framework, which enables programmers to stand on the work of others.
Ken Thompson also created an interpretive language called B, based on BCPL, which he used to re-implement the non-kernel parts of Unix. Ritchie added types to the B language, and later created a compiler for the C language. Thompson and Ritchie rewrote most of Unix in C in 1973, which made further development and porting to other platforms much easier.

· 6

02.09.2021

ACM citation:

C has a rich history. UNIX - C

7 of 51

Why this course?

https://github.com/torvalds/linux

https://gcc.gnu.org/

linux written in C. extremely successful OS.

compiled using gcc. open-source movement.

8 of 51

What is in it for you?

· 8

02.09.2021

You want to become a software engineer?

You want to become a programmer?

You want to become a data engineer?

You want to get your Bachelor?

9 of 51

What is in it for you?

Deep understanding of how computer systems impact software design
Way to learn a new programming language
Proficiency in shell, Linux, vim
(First) experience with system programming

Security | Performance

General knowledge: history, (geo-)politics, business

· 9

02.09.2021

linux written in C. extremely successful OS.

compiled using gcc. open-source movement.

10 of 51

Outline

Part I: Overview

Why this course?
What is in it for you?

Part II: What is this class about?

Computer Systems
Operating Systems
C Programming Language
Take-away

Part III: Logistics

02.09.2021

11 of 51

Model of Computation

Computers implement a model of �computation ("mechanized arithmetic").

Many models of computation exist.

Turing Machine, Counter Machines, …

Why current computation model?�(CISC, RAM, Von-Neumann Arch., …)

(choice seems arbitrary!)

performance
cost, convenience�

· 11

program

Marvin Minsky, �1967

Alan Turing, �1937

Turing Machine

Minsky�Machine

systems research:�manage trade-offs!

12 of 51

Systems

A system is a set of interconnected components with a well-defined behavior at the interface with its environment.

Coping with system complexity:

Modularity, Abstraction, Layering, Hierarchy

· 12

02.09.2021

13 of 51

Computer Systems

3 fundamental abstractions for computer systems:

Interpreter
Memory
Communication

· 13

02.09.2021

14 of 51

Memory Abstraction

· 14

02.09.2021

Source: Saltzer and Kaashoek

Associativity

Layer

Location-addressed Memory

WRITE(name, value)

WRITE(address, value)

READ(address)

READ(name)

Associative Memory

yes,�memory �is an abstraction

15 of 51

Interpreter Abstraction

· 15

02.09.2021

Source: Saltzer and Kaashoek

Instruction repertoire

Memory

Instructions

Data

Retrieve next instruction

Interpret

instruction

Interrupt

signal?

Change instruction and environment reference

Instruction reference

Environment reference

Yes

Interpreter

Instruction reference: where to find next instruction

Repertoire: set of actions associated to an instruction

Environment reference: where to find the current state �on which the interpreter should perform the actions of the �current instruction

16 of 51

Communication Abstraction

· 16

02.09.2021

Source: Saltzer and Kaashoek

Communication Link

SEND(link_name, outgoing_message_buffer)

RECEIVE(link_name, incoming_message_buffer)

17 of 51

Layered view of a Computer System

· 17

02.09.2021

Processor

Operating System

Application Programs

Main Memory

I/O Devices

Software

Hardware

Firmware

OS is a layer on top of hardware.�OS manages HW, provides abstractions to apps

18 of 51

Computer Hardware

· 18

02.09.2021

Main

memory

I/O

bridge

Bus interface

ALU

Registers

CPU

System bus

Memory bus

Disk

controller

Graphics

adapter

USB

controller

Mouse

Keyboard

Display

Disk

I/O bus

Expansion slots for

other devices such

as network adapters

hello executable

stored on disk

19 of 51

How does a CPU work?

· 19

02.09.2021

I/O

bridge

CPU

System bus

Memory bus

A single core CPU can be seen as one interpreter

Retrieve next instruction

Interpret

instruction

Interrupt

signal?

Change instruction and environment reference

Yes

Instructions

Data

Main memory

Instruction repertoire:

CISC / RISC

20 of 51

How does a CPU work?

· 20

02.09.2021

Regs

d-cache

i-cache

L2 unified cache

Core 0

Regs

d-cache

i-cache

L2 unified cache

Core 3

…

L3 unified cache

(shared by all cores)

Main memory

Processor package

21 of 51

The situation is getting more complex

· 21

02.09.2021

https://newsroom.intel.com/wp-content/uploads/sites/11/2019/11/intel-oneapi-info.pdf

22 of 51

How does main memory work?

Main memory is an array of bytes.
Each byte has a unique address.
Address space is linear.

Technology:

DRAM, SRAM: transient
3D Xpoint: persistent

· 22

02.09.2021

…

0x000000000000

0x000000000001

0x000000000002

0xFFFFFFFFFFFF

0xFFFFFFFFFFFE

0xFFFFFFFFFFFD

0xFFFFFFFFFFFC

23 of 51

Memory Hierarchy

· 23

02.09.2021

Regs

L1 cache

(SRAM)

Main memory

(DRAM)

Local secondary storage

(local disks)

Larger,

slower,

and

cheaper

(per byte)

storage

devices

Remote secondary storage

(distributed file systems, Web servers)

Local disks hold files retrieved from disks on remote network servers.

Main memory holds disk

blocks retrieved from local

disks.

L2 cache

(SRAM)

L1 cache holds cache lines retrieved from the L2 cache.

CPU registers hold words retrieved from cache memory.

L2 cache holds cache lines

retrieved from L3 cache

L0:

L1:

L2:

L3:

L4:

L5:

Smaller,

faster,

and

costlier

(per byte)

storage

devices

L3 cache

(SRAM)

L3 cache holds cache lines

retrieved from memory.

L6:

24 of 51

Latency Numbers Every Programmer Should Know

· 24

02.09.2021

https://colin-scott.github.io/personal_website/research/interactive_latency.html

in the last years:�only SSD have sped up significantly.

25 of 51

Outline

Part I: Overview

Why this course?
What is in it for you?

Part II: What is this class about?

Computer Systems
Operating Systems
C Programming Language
Take-away

Part III: Logistics

02.09.2021

for now, remember �fundamental abstractions:

interpreter,
memory,
communication

26 of 51

Operating Systems

An operating system (OS) is a program that manages computer hardware.

· 26

02.09.2021

27 of 51

OS Abstractions

· 27

02.09.2021

Processor

Main memory

I/O devices

Processes

Files

Virtual memory

process represents processor in HW,�virtual memory represents main memory in HW,

file represents IO devices

28 of 51

Processes

A process:

OS Abstraction of a running program
An interpreter

On multi-core CPUs:

Multiple processes run simultaneously

On each core:

Multiple processes can execute concurrently. �They share the same physical core
Need to switch from one interpreter to another.

· 28

02.09.2021

29 of 51

Virtual Memory

· 29

02.09.2021

Kernel virtual memory

Memory mapped region for

shared libraries

Run-time heap

(created by malloc)

User stack

(created at runtime)

Memory

invisible to

user code

Read/write data

Read-only code and data

Loaded from the

hello executable file

printf function

Program

start

30 of 51

I/O Devices

In Linux, files are a universal abstraction for all I/O devices.

A file is an array of bytes.

A file has a unique name (file descriptor).

Basic operations on files are create/delete, open/close, read/write

· 30

02.09.2021

31 of 51

Outline

Part I: Overview

Why this course?
What is in it for you?

Part II: What is this class about?

Computer Systems
Operating Systems
C Programming Language
Take-away

Part III: Logistics

02.09.2021

for now, remember �Operating System abstractions:

process,
virtual memory,
file

32 of 51

System programming

How to write programs that manage computer hardware?

OS kernel
Embedded systems
Infrastructure software that must tightly control its use of hardware resources:

Compilers, Database systems, Version control,

· 32

02.09.2021

33 of 51

C for system programming

More portable than assembly.

Efficient enough to give programmers full control/responsibility over processes, virtual memory and file abstractions

Alternatives: Rust (Mozzilla), C++

Extensions: OpenCL, OneAPI

· 33

02.09.2021

34 of 51

C as a Programming Language

Chapter 7 (specially section 7.5 in Programming Languages Concepts)

C is an imperative programming language.

C is a permissive statically typed language.

· 34

02.09.2021

Programming Language Concepts,�"Programs as Data" course

35 of 51

Compilation phases

· 35

02.09.2021

Pre-

processor

(cpp)

hello.i

Compiler

(cc1)

hello.s

Assembler

(as)

hello.o

Linker

(ld)

hello

hello.c

Source

program

(text)

Modified

source

program

(text)

Assembly

program

(text)

Relocatable

object

programs

(binary)

Executable

object

program

(binary)

printf.o

$ gcc -save-temps hello.c

https://github.com/gcc-mirror/gcc

DEMO

36 of 51

The C Standard Library

“The standard library provides a variety of functions, a few of which stand out as especially useful.” K&R

“By the way, printf is not part of the C language; there is no input or output defined in C itself. There is nothing magic about printf ; it is just a useful function which is part of the standard library of routines that are normally accessible to C programs.” K&R

· 36

02.09.2021

http://www.gnu.org/software/libc/manual/pdf/libc.pdf

http://ws3.ntcu.edu.tw/ACS099133/cheatsheet/c-libraries-cheatsheet.pdf

C language itself very minimal. even printing is part of stdio library.�when learning C, you must be acquainted w/ C library.

37 of 51

The C Standard Library

· 37

02.09.2021

38 of 51

Design Goals

“C is quirky, flawed, and an enormous success. While accidents of history surely helped, it evidently satisfied a need for a system implementation language efficient enough to displace assembly language, yet sufficiently abstract and fluent to describe algorithms and interactions in a wide variety of environments. “

· 38

02.09.2021

http://csapp.cs.cmu.edu/3e/docs/chistory.html

language trusts you to do the right thing (what needs to be done).�trade-off between fast and reliable/definite/portable.

if not careful, you might write programs w/ unintended consequences

39 of 51

Spirit of C

Trust the programmer.
Don't prevent the programmer from doing what needs to be done.
Keep the language small and simple.
Provide only one way to do an operation.
Make it fast, even if it is not guaranteed to be portable.
Make support for safety and security demonstrable

· 39

02.09.2021

40 of 51

Coding Style

“Coding style is all about readability and maintainability �using commonly available tools.” L. Torvald

Indentation
Breaking long lines
Placing Braces and Spaces
Naming
Typedefs
Functions
Centralized exiting of functions [goto considered helpful]
Commenting
Function return values and names

· 40

02.09.2021

https://github.com/torvalds/linux/blob/master/Documentation/process/coding-style.rst

41 of 51

Key Features

Imperative language

Static (but permissive) type checking

Minimal run-time support:

Explicit memory management
Explicit threads programming
Efficient mapping to assembly code

· 41

02.09.2021

42 of 51

Standards

Current standard: C11

Unicode support, threads.h, stdatomic.h, � type generic expressions

Past standards: C99, C95, C90, C89

Removed features from K&R C (such as implicit int

or partial function prototypes). Introduced long, � variable length arrays, and many library headers.

Future standard: C2X (charter), planned for 2023 (C23)

Latest version of gcc released July 2020: gcc 11.2�https://gcc.gnu.org/gcc-11/

· 42

02.09.2021

http://www.open-std.org/jtc1/sc22/wg14/

Q: what if the standard does not define a behavior?

A: then it's up to the compiler writer. (anything could happen. ex:)

43 of 51

Undefined Behavior

“In a safe programming language, errors are trapped as they happen. Java, for example, is largely safe via its exception system. In an unsafe programming language, errors are not trapped. (…)

[In C], anything at all can happen; the Standard imposes no requirements. The program may fail to compile, or it may execute incorrectly (either crashing or silently generating incorrect results), or it may fortuitously do exactly what the programmer intended.”

John Regehr

· 43

02.09.2021

https://blog.regehr.org/archives/213

http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html

44 of 51

Undefined Behavior

What happens if we add 1 to the largest integer?

This is undefined behavior.

· 44

02.09.2021

#include <limits.h>

#include <stdio.h>

int main (void)

{

printf ("%d\n", (INT_MAX+1) < 0);

return 0;

}

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1705r1.html�^-- core undefined behavior

45 of 51

Outline

Part I: Overview

Why this course?
What is in it for you?

Part II: What is this class about?

Computer Systems
Operating Systems
C Programming Language
Take-away

Part III: Logistics

02.09.2021

46 of 51

Take-aways

You will learn how the hardware infrastructure impacts software with a focus on either performance or security.

We will cover in details programming issues related to the three fundamental abstractions provided by operating systems:

Processes are interpreters
Memory is an array of bytes
I/O devices are seen as files

· 46

02.09.2021

47 of 51

Take-aways

4 compilation phases: preprocessing, compiler, assembler, linker

The C standard library contains collections of useful functions

The C standard creates undefined behaviours. Beware!

· 47

02.09.2021

48 of 51

Outline

Part I: Overview

Why this course?
What is in it for you?

Part II: What is this class about?

Computer Systems
Operating Systems
C Programming Language
Take-away

Part III: Logistics

02.09.2021

49 of 51

Logistics

(learnit;) github.itu.dk; slack [show]
textbooks: CS:APP, LCTHW
lectures (2hr), exercises (2hr)
assignments (next slide)
exam (take-home, based on assignments)

· 49

02.09.2021

50 of 51

Logistics - You

3 assignments:

datalab

perflab | attacklab

malloclab

Exam: 4 questions – 25% each (datalab, perflab|attacklab, malloclab, topics from the class)

*: SD (a master program) has a � higher passing criteria on the� assignments.

2 assignments:

datalab

perflab

Exam: 3 questions – 33% each (datalab, perflab, topics from class)

SWU, SD*

· 50

02.09.2021

two tracks!

hardest so far

don't underestimate the labs!

1 of 51

2 of 51

3 of 51

4 of 51

5 of 51

6 of 51

7 of 51

8 of 51

9 of 51

10 of 51

11 of 51

12 of 51

13 of 51

14 of 51

15 of 51

16 of 51

17 of 51

18 of 51

19 of 51

20 of 51

21 of 51

22 of 51

23 of 51

24 of 51

25 of 51

26 of 51

27 of 51

28 of 51

29 of 51

30 of 51

31 of 51

32 of 51

33 of 51

34 of 51

35 of 51

36 of 51

37 of 51

38 of 51

39 of 51

40 of 51

41 of 51

42 of 51

43 of 51

44 of 51

45 of 51

46 of 51

47 of 51

48 of 51

49 of 51

50 of 51

51 of 51