GBS

BS Tasks

Abstraktion, Resource management

Betriebsarten

• Batch procession (no user interaction)

• Transaction system (processes short, atomic (transactions) that must be completed fully and correclty)

• Time sharing (interactions between users and OS)

• Real-time system (hard vs soft deadlines)

Prozess

Ein Programm in ausführung

Groupiert und verwaltet Ressourcen (zB CPU Zeit, Speicher, Dateien, etc)

Konzeptuelle hat jeder Prozess eine CPU und ein virtueller address raum

Has at least 1 thread

Thread

Definiert einen Kontrolfluss

Abstraktion eines physischen Prozessors

Threads eines Prozesses teilen sich dessen Adressraum

Jeder Thread besitzt seinen eigenen Befehlszähler (each thread must have its own stack, PC, reigster values, etc)

Ressourcen things to consider

• Anzahl der Nutzungen (einmal vs widerholt benutzber. Eg mouse click vs speicher)

• Parallelität

• Dauerhaufigkeit (unterbrechbar vs ununterbrechbar Eg CPU ist unterbrechbar)

• Zentrale vs Peripherie Ressource

• Aktive vs Passive Ressourcen (aktiv: können selbstständig handeln oder steuern. EG. Aktiv: CPU, passiv: Hauptspeicher)

File descriptor

Referenz auf eine Datei für Ein- / Aus-gabe (0 stdin, 1 stdout, 2 stderr)

Benutztermodus

Kein direkter Hardware Zugriff (Zugrif nur über das BS)

Keine priviligierten Befehle (wie zB Ein-Ausgabe)

Kein oder nur lesender Zugriff auf Systemcode oder Systemdaten

Zugriff nur auf virtuelle Adressen

Systemmodus (kernel)

Priviligierte Befehle (e.g. direkter Hardware zugriff)

Exklusiver Zugriff auf Szstemcode und Systemdaten

Systemaufrufe

Allow users to request services from the OS (which they cannot do directly since they are unpriviledged)

A controllerd way for a program to ask the OS to perform a task on its behalf
CPU switches from usermodus into systemmodus and switches back when done

Monolitisches System

BS arbeitet vollständig im Kernel Mode

BS-Kern ist permanent im Arbeitsspeicher

(-) Ein monolithischer BS-Kern besitzt (oft) wenig Struktur

(-) Dadurch meist schwer wart- und erweitbar

Mikrokerne

BS in kleine Module aufteilen = eigenständige Systemprozesse

Nur ein Modul, der Mikrokern, läuft im Kernel Mode

(+) Kleinerer Kern: leichter wartbar

(+) Isolation von Fehlern

Binär stuff and Decimal stuff

Kbi: 2¹⁰

Mebi: 2²⁰

Gibi: 2³⁰

Tebi: 2⁴⁰

Kilo: 10³

Mega: 10⁶

Giga: 10⁹

Tera: 10¹²

Compiler

C → Assembler

Assmebler

Assembler → Machine Code

Linker (Binder)

Combines object files and libraries into a single executable

Loader

Loades the executable into memory to run

Order from C to running

Compiler → Assembler → Linker → Loader

Memory build up

Stack: Local vars, funktionsaufrufe

Heap: Dynamic memory (malloc)

BSS: Uninitialized global vars

Data: Initialized global vars

Text: Code

Zustände für Prozesse

ready (rechenwillig)

running (rechnend)

blocked (wartend)

swapped out (ausgelagert)

Thread Zustände

ready

running

blocked

(CanNOT auslagern)

Per-thread vs per-process items

Per thread:

• PC

• Registers

• Stack

• State

Per process: (all threads within the same process have to share these)

• Address space

• global vars

• open files

• child processes

• signal and singal hanlders 

• … 

Pros of multithreading

Swapping between threads in the same process is more lightweight (so lower overhead). BUT note: swapping between threads in different processes is just as expensive as swapping between processes

Simlple communication between threads in the same process

Faster to create threads than processes (so higher efficiency)

PCB

Data structure in the Kernel.

Describes what resources belong to the process.

Necessary because the CPU can only run 1 proc at a time per core. So needs to continuously switch between processes, and we have to save the information so we can continue later.

Saves:

• State

• PID

• PPID

• UID (user id)

• Stack pointer

• Program counter

• List of open Dateien

• (Priority)

• (Registers)

Does not save Dateiberechtigungen!

Creating a process

Can be done:

• During Sysinitialisierung

• Durch andere Proc

• Durch benutzter

• durch BS

Creating a proc command

POSIX “fork” system call

Parent creates a copy of itself. 

Fork returns the PID of the child to the partnt and returns 0 to the child.

Child also inherits filedescriptors for open Dateien.

Terminating a proc

Can be done

• Freiwillig (exist sys call w status code)

• BS terminates (e.g. seg fault)

• Through another proc (e.g. CTR+C in shell)

Zombies

Dead child, parent alive.

Child proc terminates before parent so parent has not read the child’s exit status yet (parent has not yet called wait()).

When child terminates, its resources are freed but the entry remains in the process table and PCB until parent calls wait(). Once wait() is called, no more zombie and PCB is deleted from process table.

Waisen (orphans)

Dead parent, child alive.

Parents terminate before child proc.

Child is reassigned (adpoted) by the init process.

Can be come a Dämon (proc must lösen from groupID and userID)

Use wait or waitpid to prevent orphans

Dispatching

Realisiert process Zustände Übergänge (scheduler chooses, and dispatcher performs the actual switch)

Orchestrates Kontext switches (e.g. running → ready)

Little vs Big Endian

little: LSB @ smallest address

NOTE: BYTES (so e.g. hex pairs) ARE STILL ALWAYS IN ORDER. DO KNOT JUST READ BACKWARDS!

Scheduling types
(for batch vs interaktiven Sys vs Echtzeit sys)

Batch Sys:

• FCFS (nicht unterbrechend)

• SJF (nicht unterbrechend)

• SRTN (unterbrechend if new proc arrvie)

Interaktiven Sys:

• RR (unterbrechend)

  • Issue of choosing right zeit quantum: too low short and the overhead is too high cuz switch proc often, but too large and it’ll act like FCFS

  • + Don’t need to know Rechenzeiten

• Priority Scheduling (unterbrechend)

  • - Risk verhungern if static prios

Echtzeit sys:

• Earliest Deadline First (EDF) (kann unterbrechend oder nicht-unterbrechend implementiert sein)

  • + No need to know rechenzeiten

• Rate Monotonic Scheduling (RMS) (unterbrechend)

Eigenschaften von parallele Sys

• Determinierheit

• Störungsfreiheit

• Wechselseitiger Ausschluss

• Verklemmungsfreiheit

• Kein Verhungern

Warten types

Aktives, passives, spin lock

Deadlock Bedingungen
(notwendig und hinreichend)

• Exclusive resources

• Hold and wait

• No preemption (res nicht entziehbar)

• Circular wait (zykl warten)

Lebendig

• Every single transition is still potentially able to schalten

• Lebendig → Verklemmungsfrei

• Verklemmungsfrei NOT → lebendig

• Wenn für alle Transitionen gilt: Es existiert für alle Belegungen M1, die von M0 erreichbar sind, eine Belegung M2, die es erlaubt, dass t schalten kann und diese von M1 erreichbar ist

• Von jeder erreichbaren Belegung kommen wir

  zu einer Belegung in der jede andere Transi-

  tion mindestens einmal schaltet nach endlich

  vielen Schaltvorgängen

Verhungern (Petri)

Whenever I have 2 trans that dep on same stellen (cuz then non-deterministisch, so could be that 1 trans always schalten and the other never although they’re always Schaltbereit at the same time)

OR

if there is a trans with no vorbedingungen cuz then that can just schalten infinitely and all other verhungern

Fairness

If for every single trans it holds: it does not verhungern

NOT fair, if there is a trans with no vorbedingungen cuz then that can just schalten infinitely and all other verhungern

Sync vs Async comm

Sync: Proc waits to recv and send msg (blocking)

Async: Non-blocking, but I have to worry about collecting the answer (puffern von msg). Entkopplung von Sender und Empfänger

Meldung/Ereignisse

vs

Auftrag/Request

Meldung/Ereignisse:

• Unidirectional (msg sender → empfänger)

• Wenige Daten wurden übertragen

Auftrag/Request:

• Bidirectional (send msg to receiver who should send smth back)

• Both can be sync or async

Async + & -

+ Good for Echtzeit & when I want non-blocking

+ Ermöglicht parallele Abarbeitung
- Verwaltungsoverhead im BS (cuz puffern msgs. write them to OS buffer)
- Behandlung von errors is harder

Kommunikationsformen

Schmal vs Breitbandig (e.g. signals vs pipes/sockets/sharedmem)

Explizit vs implicit (exp: programmer uses specific commands to move data such as write(), send(). impl: data is moved ‘automatically’ by wiriting to a shared mem addr that both proc can see)

Sync vs Async

Nachrichtenbasiert vs Datenstroeme: (data sent in distinct separate packages/chuncks where boundaries are preserved (e.g. msg queues, UPD sockets) vs data is a continuous flow of bytes (e.g. pipes, TCP sockets))

Rendevous problem

• Occurs in sync comm cuz there is no buffer

• CON: Wastes CPU time. Ineff

• Blocking / waiting

Signale (bandw, type, (a)sync, N/S, more details)

1. Schmal

2. Explizit

3. Async

4. Just the ID

5. Used to notify a proc of an event. only carries the signal ID

Shared mem (bandw, type, (a)sync, N/S, more details)

1. Breit

2. Implizit

3. Async

4. -

5. + very fast, -requires manual synchronization to avoid race conditions

Unnamed pipes (bandw, type, (a)sync, N/S, more details)

• Breit

• Explizit

• Async

• Datenstroeme

• Unidirectional.

DIFF TO NAMED:

• Only works between related processes (e.g. parent and a child)

• Existieren nur solange Prozesse darauf zugreifen

• Haben keinen Namen im Dateisystem

Named pipes (bandw, type, (a)sync, N/S, more details)

1. Breit

2. Expl

3. Async

4. Datenstroeme

5. Unidirectional.

DIFF TO ANONYMOUS:

• Can be used by unrelated proc.

• Haben einen Eintrag im Dateisystem (Exists as a special file on the file system)

• Persistieren auch ohne offene Deskriptoren (bis explizit gelöscht)

Sockets (bandw, type, (a)sync, N/S, more details)

1. Breit

2. Expl

3. Depends (TCP can be both, UDP async)

4. Depends (TCP: Datastreams, UDP: messagebased)

5. Comm betwe proc on the same or diff machine. Addressing using IP and port. Bidirectional. Are closed if one of the comm-partners terminates. Socket descriptors are file descriptors

Ports

• Work even as the process #s change

• Can have multiple ports per process

• A port belongs eindeutig to a process

• Allows a process to communicate with multiple partners gleichzeitig

Passive port: Eg a server. Resgister themselves on a port # and wait for incoming conns / msgs

Active port: Eg a client. Initiate interactions w passive procs by opening a new conn or sending a msg. Erhalten for this dynamically a port # from the OS (on which they also receive data)

Daemon proc

Ein Hintergrudprozess (and is not waiting for user interactions). They usually wait for specific events / requests to occur

Translating code → english

Go right first, then left. Interior to exterior.

[n] → array of n (just [] → array of)

* → pointer to

(<args>) → function taking <args> as arguments returning <type>

• (void) = no args

• () = beliebige args

Accessing in C (. vs →)

var.prop: when var is not a pointer

var→prop: when var is a pointer

Precendence in C

1. [] (array), () (function), →, ., x++

   1. Read left to right

2. * (pointer / deref.), & (addr), !, ++x

   1. All unary the same: Right to left

3. Binary mul and div

4. Binary add and sub

arr[n] equiv

*(arr+n)

(cuz adds (n*sizeof(ele) bytes, not just n bytes!)

If i first cast to void pointer, then it will just add n bytes, so I need to manually say * sizeof()

nice

• Starts a prog w a modified scheduling prio.

• Higher nice. value = be nicer to others = lower prio

• Default: 0

• betw -20 and 19

renice

Like nice but changes the prio of an already running proc. I need to know the proc’s PID

htop

Shows CPU and RAM usage visually (and lets me kill / renice proc)

strace

• Sys call trace

• Runs a program and prints every system call it makes (and also traces signals)

• E.g. used for debugging

time

Measures ho long a program takes to execute

Logischer Addrraum

Die menge von addressierbarem Speicher

(log addr = virt addr)

To execute multiple progs

Extensives swapping: Always only 1 prog in mem. If OS wants to exectue a diff prog copy everything Speicherinhalt of A to Festplatte and everything of B from festplatte to mem. (CON: slow)

Realocation: Progs werden an diff Stellen im Sp geladen. Beim laden I have to change the addresses (so that they are pointing to the right place in speicher) (CON: aufwendig and progs could stoeren each other)

Direkte vs basis addr vs segment addr

Direkte:

• Instruction contains exact memory addr

• + simple

• - proc can mess w each other and can korrumpieren Hauptsp

Basis:

• physical addr = logische addr + basis

• + BS can prog im Hauptsp verschieben (realocation)

• + BS can load multiple proc at the same time in Hauptsp

• - Aufwendige additions operation

Segment:

• Split addrraum into logische segmente of diff lens

• Seg anfangs addr = basis addr (and I also gotta know the length of each segment)

• CPU stellt segment-reg bereit

Frei speicher verwaltung Datenstructuren

Bit map

• (0=free, 1=belegt)

• - Find perfect block size: too small → big bitmap, too big → waste mem

• + Simple and fast

• - ineff to find k aufeinander folgende 0s to place a new proc

Verkettete Liste

• Each entry (F or B, start bit, # of bits, reference to next entry)

• - Lineare Suche

• + More flexible sp aufteilung

Belegungsstrategien + & -

First: + simple & quick (esp initially), - overtime will probs need to traverse more fo list cuz beg will just have v small mem blocks. no assumption on whether the specific sp block is good

Next: + solves issue of first. -no assumption on whether the specific sp block is good

Best: + leaes over little mem, so lower waste. -creates many v small speicher blocks that are unlikely to be usable. Slow

Worst: + Leftover sp is probs still nutzbar (unlike in best fit). - slow and large blocks are split up

Buddy Algo + & -

(+) easy to implement

(+) fast mem all and deall

(-) Internal frag: if not pow 2, so sp unused

(-) External frag: “loecher” im Hauptsp. Might have enough free mem in sum but not enough adk. (would need to shift around = slow)

grep

Searches for patterns in files
grep <options> “search_pattern” <file(s)_to_search>

-i: case insensitive

-r / -R: search recursively

-v: inverse match (all lines that do not match)

Piping

cmd1 | cmd2
takes the output of the first command and feeds it directly as input to the second

ls | grep ".jpg"

cat

concatenates and displays the file contents

cat file1 file2 file3

wc

word count

wc -l

line count

ps

Process snapshot

displays a snapshot of the processes currently running on the system (eg. process hierarchy tree)

exec()

• process replacement. it completely overwrites the current process’s memory with a new program loaded form the disk.

• If exec() is successful, the old program is gone forever, so the next line of code in my original C file will never run, because that code has been replaced by the new program’s code. (Destructive operation! Never call it in the main program!)

• PID does not change

• Often used after fork() to run a diff prog

• A system call

pthread stuff

int pthread_create(pthread_t *thread,

const pthread_attr_t *attr,

void (start_routine)(void *),

void *arg);

1. Pointer to a pthread_t where the thread ID will be stored

2. attributes

3. Function the new thread will execute

4. 1 Argument passed to the function it will execute (if none, write NULL)
   

pthread_join()
pthread_exit()

Creating a pipe command

• pipe()

• Returns 2 file descriptors: one for reading and one for writing

• Creates an ANONYMOUS UNIDIRECTIONAL pipe

create a socket

socket()

• creates an endpoint for communication

bind()

Assigns an address (IP and port) to a socket. Usually used on the server side

listen()

marks a socket as passive, read to accept incoming connections.

server-side.

accept()

extracts the first connection request from the queue of pending connections.

server side.

blocks until a client connects.

connect()

initiaites a connection to a socket. client side

send() / recv()

sends / receives messages from a socket

write() / read()

writes / reads data to/from a file descriptor

close()

closes a file descriptor

mmap()

Maps files or devices into memory.

Used to create shared memory

sbrk() / brk()

Changes the data segment size (heap) of a process.

Used internally by malloc

signal()

A C system call.

Allows a program to register a reaction (handler) to a specific signal.

“If this specific signal comes in, pause what I am doing and run this function instead”

signal(sig_to_catch, func_to_run)

EG: (SIGINT is Ctrl+C)

signal(SIGINT, sighandler)

kill()

A C system call.

It does not necessairly kill a process. It sends a signal to a process.

• Default: If I don’t specific a signal, it sends SIGTERM (terminate) which does ask the process to stop

kill(PID, SIG_TO_SEND)

Traps types

Trap in general: Types of events that cause the CPU to set aside ordinary execution of instructions and force a transfer of control to a special code that handles the event

System Call: ecall Program asks the kernel to stop execution so that it can do something for the program
Exception: An instruction (user or kernel) does something illegal / causes an error
Interrupt: A device signals that it needs attention. Forces the CPU to stop what it is doing to handle something urgent. External event needs attention.

gets

Reads a line from stdin into a buffer until new line

char gets(char buffer);

- No length check → Buffer overflow

User fgets instead: fgets(buffer, size, stdin);

atoi

- No error reporting

- Undefined behavior on overflow

• Use strtol instead

int atoi(const char *str);

scanf

• Reads formatted input from stdin and stores it in variables

scanf("format", &var1, &var2, ...);

Example:

int x;

scanf("%d", &x);

FOR STRINGS ONLY AUTOMATICALLY ADDS A TERMINATOR CHARACTER AT THE END! (so must be 1 less than buffer size!)

Live Lock

Wenn 2+ Prozesse/Threads ständig ihre Zustände ändern, aber trotzdem keinen Fortschritt erzielen
(und auf die Aktionen der anderen reagieren)

Nachteile von Parallelisierung

• Komplexität

  • Schwierige Fehlersuche bei Race Conditions, Deadlocks und Synchronisationsproblemen

• Overhead

  • Zusätzlicher Aufwand für Thread-Erstellung, Kontextwechsel und Kommunikation/Synchronisation

• Race conditions

• Deadlocks

Scheduler vs Dispatcher

Scheduler:

• Entscheidet gets CPU next (e.g. wenn Zeitwuantum abgelaufen ist or Prozess terminiert)

• Wählt aus der Ready Queue das nächste Prozess

Dispatcher:

• When Scheduler decides we need to switch process to a different one

• Führt den Kontextwechsel durch

• Speichert den Zustand des alten Proc im PCB und lädt den Zustand des neuen Proc aus dessen PCB

• Only activates when sitching between processes (NOT between threads of the same process!!!!)

SIGKILL, SIGSTOP

Können vom empfangenen Prozess nicht abgefangen oder blockiert werden.

So they always have their Standardwirkung

SIGKILL: immediately kills the proc. The proc cannot even aufräumen (e.g. dateien schliessen, speicher freigeben)

SIGSTOP: immediately stops the proc. Can only be aufgeweckt durch SIGCONT

(+) of user scheduling

• More flexibility (scheduling Strategie can be angepasst to specific bedürfnisse)

• Performance: Kontextwechsel is quicker cuz no need to switch into kernel mode (weniger overhead)

Conflicting scheduling Ziele

Durchsatz vs Antwortzeit:

• High Durchsatz needs wenige Kontextwechsel (lange Zeitscheiben)

• But quick Antwortzeit needs häufiges wechseln (kurze Zeitscheiben)

Fairness vs Priorität:

• Fairness: aims to grant every process equal access to the CPU to prevent starvation

• Priority aims to favor important processes

Nebenläufig Petri

Wenn 2 Transitionen unabhängig von einander schalten können, ohne sich gegenseitig zu beeinflussen

copy-on-write

After fork() child should have an exact copy of the parent’s code and memory. Oftentimes the memory is only changed in small parts or exec is called. So duplicating the entire memory is expensive and a waste of memory.

copy-on-write: The OS does not create a copy of the memory (child and parent see the same one). When one of the 2 tries to write to a page, the OS creates a copy of that page only

strategies used in multicore scheduling (to decide how processes are assigned to different CPUs)

time sharing vs

space sharing vs

gang scheduling

Time sharing

• Take first proc from ready queue and

• + good for not related/dependent proc

• + simple

• - slow for dependent proc

Space sharing

• Abhängige Prozesse werden gemeinsam gescheduled und belegen die zugewiesene Ressourcen bis zum Terminieren

• + Erlaubt abhängigen Prozessen direkten Austausch

• + Keine Kontextwechsel während der Laufzeit

• - mitunter hohe Wartezeiten, #abhängiger Prozesse limitiert auf #Ressouren, meistens können nicht alle Ressourcen genutzt werden

Gang scheduling

• Kombination von Time und Space Sharing

• Abhängige Prozesse bilden Gang und werden als eine Einheit behandelt

• Gangs bekommen Zeitscheiben zugewiesen

Optimierungsziele

ALL:

• Fairness: Jeder Prozess soll einen fairen Anteil der CPU erhalten

• Balance: Alle Teile des Systems (CPU, I/O) möglichst effektiv auslasten

Batch:

• Durchsatz: Maximiere Anzahl der Aufträge pro Zeit, Maß für Systemauslastung

• Ausführungszeit: Minimiere Ausführungszeit

• CPU Belegung: Konstante Belegung der CPU

Interaktive:

• Antwortzeit: Minimiere die Antwortzeit für eingehende Anfragen

• Proportionalität: Berücksichtige die Erwartungshaltung der Benutzer

Echtzeit:

• Deadlines einhalten: Vermeide Datenverlust (Soft-Deadlines). Umgang mit Hard-Deadlines

• Vorhersagbarkeit: Vermeide Qualitätsverlust z.B. in Multimediasystemen

brk & sbrk (common things)

System calls

Used under the hood by malloc

Expensive

Control the size of the data segment (heap)

sbrk(delta) = brk(sbrk(0) + delta)