# Lösungsvorschlag Operating Systems And Computer Networks FS11

Solutions provided without any guarantees.

# 1 Network performance

## Question 1.1

• Propagation delay (time to travel through medium)
• Time to transmit data (bits/bandwith)
• Queueing delays (e.g. in routers)
• Processing time (in routers, hosts,...)

## Question 1.2

Total Latency

```= transmission delay + propagation delay
= (MsgSize / bandwith) + propagation delay
= (50Kb / 1000Kb/s) + 10ms
= 50ms + 10ms
= 60ms
```

## Question 1.3

bandwith becomes the greatest factor when

packet size / bandwith > propagation delay

-> packet size > propagation delay * bandwith

in our case:

packet size > 0,01 s * 1000KB/s = 10 KB

## Question 1.4

formula

```= Msg transmission delay + propagation delay + Acknowledgement transmition delay + progagation delay
= (Msg Size / bandwith) + (200 bytes / bandwith) + 2 * propagation delay
= (Msg Size + 0,2) /1000 + 0,02 Seconds
= (Msg Size + 20.2) Milliseconds
```

(Message Size in KB)

## Question 1.5

Utilization U = (Msg size / (transfer time of msg + transfer time of acknowledgement)) / (Bandwidth)

```             = (msg size / (2 * propagation delay + (msg size + acknowledgement size) / Bandwidth)) / Bandwidth
= (msg size / 0,02s + (msg size + 0,2kb) / 1000KB/s)) / 1000KB/s
```

# 2 HyperText Transfer Protocol

## Question 2.1

When the client initiates an HTTP request without presenting a cookie number, it receives one from the server with a response message "set cookie: COOKIENO.". The server then can associate your user preferences, previous choices and your previous authetication to the given cookie number, i.e keep "state". When the client sends a new HTTP request at a later time to the server, he can present the cookie to the server,which will restore your "state" of the previous session.

The three important attributes of a cookie are:

1. Expiration: When the cookie no longer is valid and can be thrown away.
2. Domain: To which domain this cookie should be presented to.
3. Path: Which URL to present this cookie with.

## Question 2.2

• Non-persistent connection: The server parses request, responds and closes the TCP connection. This process is repeated for every requested object the server has to fetch. This leads to more RTT. In addition, each transfer suffers from TCP's initial slow start connection. Therefore, many browsers open multiple parallel connections. Standard for HTTP/1.0
• Persistent connection: The server parses request, responds and directly parses the next requests without closing the TCP connection. This way, the client can request all referenced objects once it has received the base HTML. This leads to fewer RTT and a less slow start.

# 3 Reliable Transfer

## Question 3.1

Check slides here on page 9. Note that low level actions like make_pkt does not need to be included into the solution.

## Question 3.2

Check slides here on page 15. Note that low level actions like make_pkt does not need to be included into the solution.

# 4 TCP

## Question 4.1

How actual tranmission rate is calculated:

min(CC, FC) where CC/FC means the sending rate, proposed by the congestion control/flow control algorithm

Problems solved by choosing transmission rate in that way:

1. Congestions
3. Changes in connection quality: Fast reaction

## Question 4.2

• Initially, we have absolutely no idea, which sending rate is suitable. If we start too slow, we lose performance. If we start too fast, we lose packets and therefore lose performance.
• The solution is an exponential increase of the congestion window, until we lose packets, or the threshold is reached.

Isn't this more about slow start after packet loss?

# 5 Routing

## Question 5.1

When node A routes paths to some receivers over node B, and node B routes a subset of this receivers over node A, then it is routed for eternity, or until the conditions have changed (compare: count to infinity).

## Question 5.2

Poisoned reverse: If A's connection to C is over B, then A tells B, if asked, that its connection to C has weight infinity. This avoids loops between two nodes, and no more. This leads to an ever increasing amount of unnecessary load on the network.

## Question 5.3

A------B------C

1. B=>C breaks
2. B looks for a new connection to C and chooses the connection over node A.
3. A has to update its connection because it has been notified by node B
4. B has to update its connection because it has been notified by node A

Result: A and B never know that C is unreachable, A and B count to infinity.

## Question 5.4

The path to the receiver is memorized with the table entry. If a new path contains a broken path, it's invalid. Obviously it's not possible to have the count to infinity problem.

# 6 Network Layer

## Question 6.1

Why does every network or network type have its own MTU?

1. Circuit switched networks do not have a MTU! :)
2. The chance of corruption is different for different networks
3. The speed is optimized if the MTU is as big as possible for a certain network
4. MTU enforces fairness => no one can send for an arbitrary amount of time
5. The buffer size of the switches in between limits the MTU => different for different networks

What is the MTU?

Packets in a network are not allowed to be bigger than a networks maximum packet size (MTU).

What are the problems being addressed by fixing a maximum size?

see first question

## Question 7.1

Interpret the polinomial as a binary String: x^3 + 1 => 1001

Take the message and concatenate as many zeroes as the degree of the CRC generator polynomial, then do the following binary-polinomial division.

``` 100101101 000 / 1001 = 1
00001101 000          0
0001101 000          0
001101 000          0
01101 000          0
1101 000          1
100 000          1
00 100          0
0 100          0
remainder: 100
```

with remainder 100 => 100 is the CRC checksum.

Check: 100101101 100 / 1001 => remainder 0 respectively 1001 * 100001100 = 100101101100

## Question 7.2

see Chapter9 on slide 10 and following

## Question 8.1

1. A timer interrupt arrives
2. Processor switches to kernel mode and executes the interrupt handler
1. Save the registers in processes kernel stack
2. Call scheduler to determine the next process
3. Load registers from the new processes kernel stack
3. Switch to the new process

## Question 8.2

1. A timer interrupt arrives
2. Processor switches to kernel mode and executes the interrupt handler
1. Save the registers in processes user-mode stack (calculate address)
2. Call scheduler to determine the next process
3. Load registers from the new processes user-mode stack
3. Switch to the new process

## Question 8.3

The answers wouldn't be modified at all. The only difference is the scheduler.

## Question 8.4

1. Cheap to create and destroy
2. Fast to context switch

1. Easier to schedule
2. nicely handles blocking

# 9 Scheduling

## Question 9.1

1. Fairness
2. Power consumption
3. Policy (Responsiveness, different kind of real-time scheduling )
4. Balance (between io-bound, cpu-bound, ...)

## Question 9.2

1. 1/2 Context switch (A to kernel)
2. Scheduling
3. 1/2 Context switch (kernel to B)

Response time: time between an action and its corresponding reaction.

If we never do a context switch, scheduling overhead is 0, but response time may be infinite for some processes.

If we optimize response time, scheduling overhead grows.

## Question 9.3

Unix has a set of priority levels. For each priority level, there may be a certain amount of threads. The scheduler executes the threads with higher priority first. If a thread uses its quantum entirely, it loses priority. If the time of last schedule for a process grows, this process gains priority. On the same priority level, processes are scheduled by another scheduling algorithm (RR, FCFS).

It tries to prefer I/O-bound before CPU-bound processes.

# 10 Virtual Memory and Demand Paging

## Question 10.1

Belady's anomaly: More frames ${\displaystyle \nRightarrow }$ less or equal amount of page faults

Algorithm: FIFO

## Question 10.2

1 2 4 3 2 3 4 6 7 1 2 4 7

frame 1 frame 2 frame 3 frame 4
1
2
4
3
2
3
4
6
7
1
2
4
7

Result: 9 page faults (red)

## Question 10.3

Working set: Set of page references a process has used in the last k instructions (or time interval)

Useful to minimize thrashing and optimize parallelism

# 11 Input/Output

## Question 11.1

1. Interrupt handler
3. User process

Problem that it attempts to solve: Mediation between interrupt-driven hardware and blocking user processes.

## Question 11.2

1. User process blocks (System call)
2. Wait
3. NIC transfers packet to kernel memory via DMA, usually using a ring buffer
4. NIC sends interrupt to OS