I HAVE MOVED

Hello friends who came across this website by accident or by referral, 
I am no longer updating this website anymore. 
All new notes have been moved to another website here

Please visit that website for newer notes

CS2106 - Lecture 8: Disjoint memory schemes

Now we are under the assumption that everything is fixed sized partition
1. The physical memory is large enough to contain one or more processes

#Paging scheme

##Introduction

The physical memory is split into region of  **fixed size ** 

- Known as physical frames

- Frames size decided by hardware

> Memory designers or hardware designers decide the size? -> CPU decides the frame size as it is the component that does the translation.

The logical memory of a priccess is split to

- Same size

- Logical page

At the exe time, the pages of process are loaded into any available memory frame

- Logical is contiguous

- Occupied physical memory region is disjoint

### Page Table: Look Up mechanism

Contiguous:

- Simple to keep track of the usage of process

    - Starting address and size of process

    - Using simple link list storing mem context information for all process

Paging scheme:

- Logical page <-> Physical frame mapping is no longer straightforward

- Need lookup table to translate

- This is page table

*Physical memory is divided into frames where each page in the logical memory is mapped into a frame.* 

> What is the physical address in memory that will be access when the process is loaded. -> 

Given page size is N = 1000B,

 if the address is loaded is 

                          load r1, [2106] 

It will be in page 2 since it is in 2000's memory where

page 0 -> 0 to 1000

page 1 -> 1000 to 2000

page 2 -> 2000 to 3000

> As you can see there is no reference about the physical memory nor the amount of byte we are accessing since each page is the same size. 

## Logical Address Translation

It is easy to compute the physical address given the size of the page and the logical address.

Physical address = **frame_number X sizeof(PhysicalFrame) + offset**

Logical memory address :

- Page (m)
- Offset (o)

e.g 

given logical address of 1110 where m = 4, o = 2

11 -> frame number

10 -> Offset

Look at the frame number 11 (3) and see what address it is map to.

*assume page 3 maps to 110*

Physical memory of this address will be -> 110 + offset = 110 + 10

### Tricks

- Keep frame size (page size) as power of 2 

- Physical frame size == logical page size

> If a size of a page is 2^n then we need n bits to identify

### Observation

- There are no external fragmentation -> There is no contiguous memory

- There are internal fragmentation -> We can have a process memory that use not the entire page (internal fragmentation)

> It is common but it is not a big issue as page is normally allocated to be larger than whar a process need. It is better than fix partitioning as for page, internal fragmentaion only happen to the last page

- Clean seperation of logical and physical address space

  - great flexibility

  - Simple address translation

### Implementation

- OS stores page table in PCB

- Memory contact of a process == page table

> We do not store the entire of the memory nor copy it into the PCB. 

Issues:
- Requires 2 memory access for every memory reference

   - Page

   - Physical

> inc src uses 6 memory access 

  - Instructions

  - Get value from register

  - Translation

(disjoin p1_

## Hardware Support

- TLB (Translation  look aside buffer)

Instead of going to memory and do translation multiple times, we just check the cache.

TLB cache page table entries and is very small and fast (<=1 clock cycle)

> It is one if the fastest structures in the computer

- Logical address translation with TLB

   - Use page number to search TLB associatevely

   - Entry found (TLB-HIT)

Frame number is retrieved

   - Entry not found (TLB-Miss)

 

Memory access to access the full page table. Retrieve frame number is use to generate physical address and page table

#### Translation

**Without**

1. CPU generate page number and offset

2. Use the P to index the table and the frame number

3. Go to the physical memory and get the memory using the frame and offset

** With (Hit)**

1. CPU generate page number and offset

2. Pypass the memory and go straight to the cache

3. Access using the offset

AMAT (Average mem access time) 

**= P(TLB hit) X latency (TLB hit) +  P(TLB miss) X latency (TLB miss)**

> There is a hidden time which is not considered which is the time taken to fill the TLB

#### During Context Switch:

Phy:

- No difference

- No saving

Log:

- No change

- They are pointing

PT

- Reside in OS memory

- The OS will not save and restore it all the time

- OS will use a reg in the CPU that record the PT starting index

*Sort of like loading a stack*

TLB:

- Hardware optimisation that help with optimisation

- They are invisible to the software/application

- The TLB might be misguided to some memory that does not belong to that process and cause seg fault after context switch thus we need to do TLB flushing that will be done by the OS.

> TLB is not part of the hardware context of a process although the OS must know about it.

> It is one TLB per CPU core

## Protection and Page Sharing

- Access right bits

Is the page exist and whether the page is readable, writable or executable bits. Memory access is checked against these access right bits.

- Valid bit

> Logical memory range is usually the same for processes.

Only pages that can be use have the bit set, if we try to translate any page that has 0 bit set, then it will thrown an exception

### Page sharing

- Page table can allow several process to share the same physical memory frame:

Some code is shared within multiple processes (syscall) 

**Copy on write**

- Create the a new page of a child process only when the child wants to write. Accessing (reading) will use the same page table as the parent

# Segmentation Scheme

Instead of fitting the process in variable size partition, we break the process to fit into multiple variable size partition

## Motivation

Each process has a distinct number of logical memory regions (stack, data, text, heap)

We just need to have a distinct section to access

- text : Read

- Data: RW

- Heap/Stack: R/W

However, some regions may grow and shrink at execution time and this is not good for paging due to potential internal fragmentation.

Usage and permission within a segment are usually the same.

## Basic Idea

Manage memory at the level of memory segments

- Logical memory space of proccess is a collection of segments

- Mapped into contiguous physical partitions of the same size

Each memory segment:
- Has a name

- Has a limit (How far it can grow)

All (Logical) memory reference is specified as:
- Segment name + offset

- Neither the compiler nor the compiler needs to know where the segments are located, only that it exist. The compiler does not need to know about the logical address associated with the address.

The os will place the segment into an available space in pjysical address and this is when it is known (Base address)

## Logical Address translation

Each segment mapped to a contiguous physical memory region

- Base address

- Limit

The segment name is represent as a single number

- seg id

Logical address <segID, Offset>

- segID is use to look up base and limit of the segment in a segment table

- Physical address is base + Offset

- Offset < limit for valid access ( Cause of seg fault if it is above limit)

> Looking up the segment table using the segID where we will check the limit.

e.g <2,500>
Segment 2 has the base address of 2400

Our lookup -> 2400 + 500 in physical address

## Hardware support

We need to lookup memory twice for each lookup

1. Segment table

2. Access after doing translation

> This is much more efficient

## Differences

###Pros:

- Each segment is independent continguous memory space

More efficient bookkeep and segments can be protected/shared independently

This also matches a programmer's view of memory

> Depends on the size of the memory, it determines the number of factor if to go for segmenting or paging

### Cons:

- Can cause external frag due to variable size contiguous memory

# Segmentation with Paging scheme

Problems with segmentation: We are still trying to fit a segment into a fix size partition.

Instead we break every segment into pages 

## Basic Idea

- Every segment have its own page table

- Mapping each pages into physical memory

Pros:
- Easy to shrink and grow segments

1. Process generate the logical address -> <Segment, pagenumber, offset>

2. Get the memory in segment table

3. Get the page number from the segment

4. Add the offset to get the physical memory

> There are alot of strcuture for the OS to work with

<disjoint>

CS2106: Lecture 7 - Memory Abstraction

# Basic of Memory

## Hardware

- Physical memory storage: 

    - Random access memory (RAM)

    - Can be treated like an array of AU

    -  AU = addressable unity =  1 byte

    - Each byte has an unique index known as a physical address

<Insert slide 4>

### Actual Execution

The compiler does not know where the address is when a code is runned requesting access to an memory. Sometimes the compiler needs to store data as well, how does the compiler know which memory is free.

The OS will allocate the memory that is requested.

## Transient Data

Stack

## Persistent data

heap/global

## Managing memory

The OS

- Allocate to new process

- Manage space for process

- Protect memory space of process from each other

- Provides memory related syscalls

- Manage for internal use

# Memory abstraction

Memory abstraction is useful as it ensure protection for a memory space. 

Some embedded system however, does not use memory abstraction. This allow full control of the memory and allow the system to directly access (No OS in between)

However, this is bad as might as two process might fight for the same physical address if run together.

*We can fix this issue by adjusting the address base on what is given (Offset)*

- Recalculate the memory reference during loading

Problems:

  - It might be slow to load

  - Not easy to distinguish memory reference from normal integer constant

- Base + Limit register

Write my code such that every code is relative from the starting point of my code

- Base register: Stores starting address of my program

> The address is computed at runtime

- Limit register : tells if the address generated is outside of my range (Compiler can do)

Problems:

  - Memory has to be one big chunk (Contiguous)

  - Every memory access is an addition and comparison

<Limitation can be bypass if there are more registers>

However, this idea is very useful

  - Segmentation mechanism

  - Provides a crude memory abstraction

* Address 4096 in process A and B are no longer the same physical location *

## Logical Address

- Embedding actual physical address in program is a bad idea

   - Give idea to the logic of logical address

We want to involve the operating system but we do not want to pay the price of it

# Contiguous memory abstraction

## Assumptions

- Process must be in memory during execution

   -  Store memory concept

   - Load-store Memory execution model

1. Each process occupies a contiguous memory region

2. The physical memory is large enough to contain one or more processes with complete memory space

### Multitasking, Context Switching, Swapping
 To support multitasking
  - Allow multiple processes in physical memory at the same time
 When physical memory is full
  - Remove terminated process
  

## Memory partitioning

Contiguous memory region allocated to a single process

### Fixed size partition

   - Physical memory is split into fixed number of partitions

   - Process will occupy one of the partitions

*Chunk the memory into partitions of equal size, we can fit a process into any of the partitions with no differentiation*

*A process however, may not be able to fit in due to the fix size or it might waste some space*

*This is a waste problem called internal fragmentation*

Advantage:
- Easy managed

- Fast to allocate

    - Due to fixed size, there is no need to choose (No algo run)

Disadvantage

- Internal fragmentation (Smaller process will waste memory space)

- Partition size need to be large to accommodate the process

### Dynamic Partitioning

   - Partition is created based on the actual size of process

   - OS keep track of the occupied and free memory regions

      - Perform splitting and merging when necessary

- Dividing the memory to different sizes

- Assign the needed memory for the processes

- This resolves the problem of internal fragmentation

*However, if a process frees a space, the memory that it frees + the leftover memory is enough to accommodate a process but due to the fragmentation, it is not useable (External Fragmentation)*

Pros:

- No internal fragmentation

- Flexible

Cons:
- There might be external fragmentation

- Need to maintain more info in the OS
- Takes more time to locate appropriate region

*It is much more challenging for OS to manage partitions of many sizes*

*We can have almost infinite number of partitions but it is very hard for the OS to manage. It has to store the partition into a linked list.*

#### Allocation algorithms

- Assuming the OS maintains a list of partitions and holes

- Algo to locate partition of size N

- Variants:

  - First Fit

   

    Pick the first hole that is large enough

   - Best fit

    FInd the smallest Hole that is large enough

   - Worst fit

    

    Find the largest hole

- Split the hole into N and M-N

    - N will be the new partition

    - M-N will be left over space -> a new hole

#### Merging and Compaction

> This are ways to solve external fragmentation after dynamically allocating

When an occupied partition is freed:

  - Merge with adjacent hole if possible

Compaction:

  - Move the occupied partition around to create consolidate holes

  - Cannot be invoked to frequently as it is time consuming

------ 26/3/20

Considering the 3 algorhtims

FF:
Allocation can be constant
Deallocation: Linear

BF:
Go through entire list
Deallocation: Linear

WF:
Go through entire list
Deallocation: Linear

#### Multiple Free List
- Seperate free list of free holes from list of occupied partitions
- Keep multiple list of different hole sizes
- Take hole from list that most closely matches size of request
   - Faster allocation

> We can directly locate the size needed without needing to search the entire list. It is in power of 2 usually using a hashmap

#### Buddy Blocks
- Every partition is a power of 2
- Each partition in the system has a buddy due to the way it is created recursively
- For each row of address, we will partition it.
- If the partition is still big, we can further partition it.

**Freeing**
- Merge buddy blocks if they are both free


- A block that is too small is not cost effective to manage

**Algorithm**
1. To allocate a block of size N
2. Access A[S] for a free block
3. If its too big, split it more


** Free**
1. Check if buddy free
2. If it is free and exist, remove B and C from the list
3. Merge the two buddies into a bigger partition

> Note that buddy blocks would always have one binary digit difference between each other


Allocation: O(k), where the system has 2^k memory
Deallocation:
O(k) - Finding the buddy
Merging:
O(n) -  Figure out if they are buddies

> However, we do not use this allocation now

CS2103T: Lecture 7 - UML Diagrams and Testing

CS2106: Tutorial 5

CS2105: Tutorial 4

CS2105: Lecture 6 - IP Addressing

Overview of network layer

Transport segments from sending to receiving host

- On sending side encapsulate segments into datagrams

- On receiving side, delivers segment to transport layer

Difference with network and the rest is that this protocol is the core of the internet

Every single component in the network has this layer

- Router examines header fields in all IP datagrams passing though it

Two key network layer

Forwarding:

Moves packets from router input to appropriate router output

e.g Process of getting though single interchange

Routing:
Determine route taken by packets from source to destination

This is for a single router to determine where to go

It will look at the packet header, extract the ip address

Through the forwarding table, it tries to match the ip address with the destination to see which output link to output to

It is determine by the routing algorithm inside the router

The routing algo determines the value in the routing table

e.g process of planning trip from source to destination

Data plane

- Local, per router function

- Determines how datagram arriving on router input port is forward to router output port

- Forwarding function

Control Plane

- Network wide logic

- Determines how datagram is routed among routers along end to end path from source host to destination host

- To control plane:

Traditional (In routers) or software defined networking (Remote server)

<Insert 9>

Network layer have different protocols, there are different type of routing protocols

This is use to determine the content of the forwarding table

The single IP protocol is the most important

IP protocol

- Addressing convention

- Datagram format

- Packet handling convention

IP: Internet protocol

IP address: 32 bit identifier for host, router interface

e.g 233.1.1.1

Interface: Connection between host/router and physical link

The ip address is associated with the interface

- Router typically have multiple interfaces

- Hosts has one or two interface (Ethernet or wireless 802.11)

IPaddress associated with each interface not with a host

A host can have multiple interfaces

Q How are these interfaces actually connected?

A: Wired ethernet interfaces connected by ethernet switches

This is for local internet

A: Wireless WIFI interfaces

//DO not need to worry about how are they connected 

Subnets

Subnet is a network formed by a group of directly connected hosts

- Hosts in the same subnet can physically reach each other without intervening router 

(Physically: Communication between the interfaces does not need a router)

- They can connect to the outside world through a router

- Hosts in the same subnet must have the same network prefix of IP address (the left most bits)

To determine the subnets, detach each interface from its host or router, creating island of isolated networks.

CIDR (Classless interdomain Routing)

<SLide 15>

Ip address comprises of two parts

- Network subnet prefix

- Host ID

Address format: a.b.c.d/x where x is the number of bits in subnet/network portion of address

The routers if they want to route to the host, they only need the first x bits to be able to forward.

The network inside this network will be able to use the host part to identify the host needed to forward.

This helps reduces the number of contents in the routing list.

Subnet mask

Is made by setting all network prefix bits to 1 and host ID bits to 0s 

e.g For IP address 200.23.16.42/23

                                                  <|       Host        |>

11001000    00010111   00010000     00101010

11111111     11111111    11111110     00000000   <= subnet mask

Q: How does ISP gets block of address

A: ICANN (Internet corporation for assigned Names and Numbers)
- Allocates address
- Manages DNS
- Assigns domains names, resolves disputes

<SLide 18 special IP address>

Q: How does an organisation obtain a block of IP address

A: Buy from registry or rent from ISP address space

Hierarchical Address: Route aggregation

Each ISP controls a block of IP addresses

Allows efficient advertisment of routing infomation

Within organisation

The ISP can differentiate which orgnaisation to forward their packet to

<Slide 20>

They use bit by bit to identify which network to forward

What is they want to change one block to another from ISP 1 to ISP2

Under the current internet, ISP 2 will simply add one more entry to the neighbouring routers and update the x.

This is called Longest prefix matching.

It advertises to nearby routers the block of ip address it is handling.

Nearby routers will then route to them instead

The entries must match up to x bits starting from the left.

This will let it determine which is the next hop

Q: How does a host get a IP address

- Hard coded by system admin in a file

Windows: control-panel>network> configuration > tcp/ip >properties

Unix: /etc/rc.config

- DHCP

DHCP: Dynamic Host Configuration Protocol

Dynamically get address from as server

"Plug and Play"

Goal: Allow host to obtain IP address when it joins a network

- Can renew its lease on address in use

- Allow reuse of address (only holds address while connected)

- Support for mobile users who want to join network

DHCP runs using UDP

= DHCP server port number: 67

= DHCP client port number: 68

It does not need to be reliable

DHCP can return:
- Address of first hop router for client

- Name and ipaddress of server

We can use one DHCP server to serve multiple subnets.

These request can be forwarded through the routers.

1. Arriving client construct a new DHCP message

- special IP thats all 0

Destination: 255.255.255.255 (Broadcast)

yiaddr: 0.0.0.0 This field will be filled by servers

Trans ID: For client to differentiates the reply from other clients and its server

2. DHCP offer

If its within the subnet, it is easy.

But if it is in another subnet, the broadcast message have to be broadcast to a router which will then relay the message to another subnet

The DHCP will make the allocation

- Echos the ID

- Life time

- Assigns a address (But it is not used yet)

- Srcs (Its server address)

Server will broadcast it back

3. Receiving the message

Check if the Trans ID is mine, else drop

- Make a formal request to the DHCP server 

But there might be multiple DHCP server, might get multiple offers,

Client choose one and echo back to that DHCP server

- New trans ID

- Source IP still 0

4. DHCP ACK
Confirms by sending an ack back

- Echo the yiaddr back

- The first two times might be optional

- The client does not know the existence of a dhcp server

- The client can skip step 1 and jump to 2 if it already knows where to get the request from

(returning)

IPV4

Network layer services

- Network layer delivers packets to receiving host

- router examine header fields of IP datagrams passing it

- Use of many protocols

Datagram format

The socket is represented by a set of API. The transport layer add a header which include the destination and src port. In the network layer, the ip address will be added to the header.

IP header is 20 bytes and has 5 rows in total.

Fields:
- IP protocol version number (IPV4)

- IP datagram length - the length of the entire packet including the header

- Headerchecksum -  only for header

- Source IP address - sending host

- Destin IP - receiving host

- upper layer protocol - udp/tcp

-ttl - Time to live (Specified by the sender)

   Each router decrease the TTL as it received it.

   This is to ensure that the packet will not circulate the network forever.

- Flags/Frag offset - IP fragmentation

Fragmentation

- Packet might pass through different routers before reaching destination and different links may have different MTU (Max transfer Unit) - The maximum size of the ip packet that the link level frame can carry

- To large IP datagrams will be fragmented by routers

- Fragmented packets will be reassembled by destination host

when all fragmented packets are received. It needs to know

   - How to reassembled

   - How many packets are there

   - The order

   - What is the length

- Each Fragmented packet will have its own header (20byte),

   - length of packet

   - ID  (Same for all fragments)

   - Flag to state how many trailing packets are there (0 if its the last)

   - offset (show the relative order of the packets from the first packet in units of 8 bytes)      

   We only have 13 bits for offset thus we have to represent in 8 bytes in order to be able to 

Network address translation

Recap

- 32 bits -> a.b.c.d/x (where x is the prefix and a,b,c,d are 8 bits each)

- Subnets -> A set of directly connected host

- Addressing -> CIDR (A fix subnets with the use of prefix)

- Getting IP address -> Get a block from ICANN/IANA; get from ISP; DHCP

- Hierarchical addressing  -> Longest prefix matching

Router -  Function as an DHCP server and a client

DHCP server: To our home devices

DHCP client : To the ISP provider

Non unique IP address is not routable

LAN

- Local area network

e.g school network

WAN
- Public IP

Implementation

- Replace the source Ip and port of every outgoing datagram to (Nat IP and new port)
- Remember the mapping of the source ip to port number of NAT Ip and new port

- Replace in destination fields of every incoming datagram with corresponding source IP and port number stored in NAT translation table

Sending a packet to a server in WAN from LAN

Translation

1. The router will replace the IP of the received packet with the public IP (Usually the IP of the NAT router).

2, Translate the port number to another port number

3. Sends the packet to the outside server

- All datagrams leaving the local network will have the same source NAT ip address

- There cannot be a collision of port number within the LAN

Receiving a packet from WAN to a host in LAN

Translation

1. Reverse translation

2. Send to the original host

Motivation and Benefits

- Do not need a range of public ip address from IP, just one public for NAT router

- All host use private IP address, can change address of host in the local network without notifying the outside word

- Change ISP without changing addresses of host in local network

- Host inside the local network are not explicitly addressable and visible by outside world (security plus)

Challengers

- Peer to peer does not work directly

   The receiving Nat device does not have the information of the peer it suppose to send to in its LAN

- This can be countered by using a 3rd party 

Routing Algorithms

The internet is a networks of networks, there is no single organisation that own every single router

THus routing is done hierachyally

AS - Automonous system

Routing in the internet

Intra- AS routing

- Finds a good path between two routers within an AS

- Commonly use protocols: RIP, OSPF

- Single admin, no policy decisions are neeeded

- Routing focus on performance

Inter-AS routing (Not covered)

- Handles the interfaces between ASs

- The standard protocol: BGP

- different admin to control traffic and who routes

- Policy may dominate over performance

Abstract view of Intra AS routing

- Graph

- Vertices: routers

- Edges: Physical links

Routing algo classification (Not tested)

- All routers have the complete knowledge of network topology and link cost

- Periodically send link cost

Distance Vector algorithms

- Router know physically connected neighbours and link cost to neighbours

- Router exchange 'local views' with neighbours and update own 'local views' (based on neighbor' view)

- Iteraative process of computation

   - Swap local view with direct neighbours

   - Update own local view

   - Repeat till no more change to local view

KEY POINT: It will only contact neighbours and not indirect neighbours

Pros: Will not be overflooded

Cons: Longer

c(x,y) is the cost of link between routers x and y

- =infinite if x and y are not direct neighbours

dx(y): the cost of the least cost path from x to y from x's view

Bellman ford equation

dx(y) = minv{c(x,v) + dv(y)}

where the min is taken over all direct neighbours of v of x

Refer to CS2040 > Graph Theory

- Every router send it distance vector to its directly connected neighbor

-  x finds out that y is advertising

- Update its distance to z accordingly

- Not down that all packets for z should be sent to y, This info will be use to create forwarding table of the router x

- After every router exchange several rounds of update with its direct neighbours, all router will know the least cost path to all the other router.

RIP

Routing information protocol implements the DV algorithms. It use hop count as the cost metric and is insensitive to network congestion

ICMP

Internet control message protocol is use by host

ICMP type and Code

Ping and traceroute:
The command ping sees if a remote host will respond -> is there a connection

The command traceroute sends a series of small packets across a network and attempts to display the route that the message will take to get to a remote host.

Traceroute will show all the path, it sends the packet using ttl incremementally since the router have to forward back its own ip address if ttl reaches 0.

ICMP is use to send error message and to trouble shoot networks.