Operating Systems Final Review

What is a network?

A bunch of computers connected together to exchange data

What is an IP address?

a sequence of numbers that uniquely identifies each computer or device connected to a network.

What does an IP address look like?

four unsigned integers ranging from 0-255 separated by dots.

Ex: 23.40.100.0

Why isn't an IP address alone enough for networking communications?

There are several processes running on any computer at any given time, so there needs to be something else to uniquely identify which process we want to send or receive data from.

How do we specify a message should be delivered to a specific program?

We specify it by using a networking port.

What is a networking port?

a unique identification number assigned to a program that wants to use the network

What are well known ports?

Ports with pre-determined purposes ranging from 0 - 1023

Ex: 80 - Web Servers (http requests)

What is a networking socket?

A combination of an IP address and a networking port.

What is a browser?

A program that displays webpages received from the internet as files

What is a web-server?

A server that responds to requests for webpages.

Does each computer have a unique IP address?

Yes

What is a client?

A computer that asks for services/help from other computers on the network.

What is a server?

A computer in the network that listens to incoming requests and replies to them.

What is a communication protocol?

set of standards that defines the structure of messages (TCP, IP,HTTP)

How does the browser know the web server's networking socket?

It uses URLs

What is a URL?

Uniform Resource Locator. It is the English name for a web server's IP address

What is DNS?

Domain Name System. It is a computer/server that receives a URL and returns the corresponding IP address.

What is RPC?

Remote Procedure Code.

An instrument that allows the start of functions on a server

How does the web server know where to reply to a browser request?

The web server will look at the networking socket that came with the initial request.

What is a physical address?

Addresses that are on the physical RAM device.

What is a logical (virtual) address?

Address that exist in a program's virtual memory (imaginary RAM memory that the program believes it has)

How does logical memory work?

The Operating System/hardware tells a program when it first launches that it has access to all of the memory, but it actually only has access to a specific chunk.

What is a Physical Address Space?

a collection of all physical addresses

What is a Logical Address Space?

a collection of all logical addresses of one process.

What is a significant difference between physical address space and logical address space?

There is only one physical address space on a computer, but there are as many logical address spaces as there are processes running on the computer.

What is the Memory Management Unit (MMU)?

a device that converts logical addresses into physical addresses

What must happen when the CPU executes an instruction with a logical address?

The CPU must communicate with the Memory Management Unit, where the logical address is converted into a physical address.

What is the RAM Memory Controller?

a device that allows the computer to interact with RAM.

What is Contiguous Memory Management?

When the operating system searches for a large enough block of contiguous memory to accommodate the process. If a suitable block is found, it is allocated to the process.

What is the range of logical addresses for a process that needs 10 kb of memory?

It will start at address 0 and end at address 10,000 (in binary)

What is a limit value?

The max amount of memory a program is given. It can change depending on the needs of the program, but once it is set, it won't change.

Ex: A program that needs 2 kb when it launches cannot exceed 2 kb in memory.

What is fragmentation?

A scenario in which the computer wastes RAM due to inefficient memory usage.

What are the two types of fragmentation?

External Fragmentation and Internal Fragmentation

What is external fragmentation?

When the inefficiently used memory in the RAM is unused by processes and wasted.

How can external fragmentation happen?

if three processes are running and the process that is physically between the other two in the RAM finishes running, it causes a memory hole of however large the process was. It becomes hard to fully utilize the memory that is left there because you would need a process that is either as big or smaller than the old process to run there.

What is a memory hole?

A gap of memory between two programs that remains unused due to external fragmentation.

What are some approaches to contiguous memory allocation (management)?

1) Best Fit - Maximizes external fragmentation (memory holes)

2) Worst Fit - Minimizes external fragmentation (memory holes)

3) First-Fit - Fast method

What is the "best fit" approach for contiguous memory allocation?

The OS will choose a memory hole that is closest to the size of a process that is going to run. If there is none, it will just proceed after the farthest process in the RAM. This maximizes external fragmentation (amount of memory holes).

What is the "worst fit" approach for contiguous memory allocation?

The OS will choose the biggest memory hole available and put the process in there. This minimizes external fragmentation (amount of memory holes).

What is the "first fit" approach for contiguous memory allocation?

The OS will choose the first memory hole that is large enough to fit the process. This is a fast method, but its effectiveness depends on how good of a fit the first memory hole the OS finds is.

What is Paging?

A technique modern computers use to split a logical address space of a process into pieces of an equal fixed size. The same happens to the physical address space.

What are pages?

Pieces of an equal fixed size of a logical address space.

What are frames?

Pieces of an equal fixed size of the physical address space.

What is a page table?

A table located in the Memory Management Unit that keeps track of every page number's corresponding frame number.

How does the MMU convert logical addresses to physical addresses when dealing with paging?

When a logical address is given to the MMU, it must figure out which page it is located in by floor-dividing the address by the page size. It then takes the modulus (remainder) of the address with the page size and uses that as the offset. The MMU looks at its page's corresponding frame in the page table and gets the base address by multiplying the frame number by the page size. Finally, it adds the offset to the base address of the frame. to get the physical address.

How do you get the offset for a logical address' corresponding physical address in a frame?

Take the modulus of the logical address and the page size (remainder after dividing the logical address by the page size)

How does the MMU figure out a logical address' page number?

It does floor-division between the logical address and the size of each page.

How many wires connect the CPU with the MMU?

It depends on how many bits the computer uses. It may have 32 wires corresponding to a 32-bit computer or 64 wires corresponding to a 64-bit computer.

Do all wires connecting the CPU to the MMU communicate with the page table?

No

What are all the wires that go into and out of the MMU do?

Some wires will deal with the page number, some wires will deal with the frame number, and some wires deal with the offset needed to get the physical address.

In binary, how do we determine the offset based on the page size?

The page size will always be a power of 2, so we take the log-base-2 of the size to get the length of the offset in binary. The offset will be the right-most n bits, where n is log(page size), of the address.

In binary, how do we determine the page number of an address?

After you determine the length of the offset, the page number will be the leftmost k bits of the address, where k is the length of the offset in binary subtracted from the size of the address in binary.

If the address length is 48 bits and the page size is 2 kb, what is the length of the offset? How many pages can the process have?

2 kb = 2048

2048 = 2^11

The 11 rightmost bits represent the offset.

The 37 rightmost bits represent the page number.

2^37 - 1 = 137438953471 possible pages

Given a system with logical and physical address sizes of 24 bits and page sizes of 2 kb:

1) What is the size of the page offset (in bits)?

2) What is the number of entries in a page table?

3) What physical address corresponds to the following logical address (in hexadecimal): 0x001DFA

Page Number | Frame Number

0 -> 9

1 -> 10

2 -> 11

3 -> 12

1) 2kb = 2048 B.

2048 = 2^11

So page offset is 11

2) Addresses are 24 bits, and the rightmost 11 bits are the page offset.

24-11 = 13.

2^13 = 8192

There are 8192 entries in a page table

3) 0x001DFA = 00000000 0001 1101 1111 1010

Page Number = 00000000 0001 1 = 3

Page 3 = Frame 12

Frame 12 = 0000000001100

Physical Address = 00000000 0110 0101 1111 1010 = 0x0065FA

What is On-Demand Paging?

All the pages are stored on the hard disk until they are needed. When a function or code is needed, then it will be copied from the hard disk and onto the RAM.

What is Page Fault?

A situation when a process wants to use a page that is not currently in RAM. They are performance expensive because this page now needs to be copied onto the RAM and entered into the page number.

Why is storing the whole page table in the MMU a bad idea?

Copying an entire page table, which can have millions of entries, would result in much slower context switching.

Why is the MMU using the page table straight from RAM a bad idea?

You cannot do the memory operation without the page table, so you would have to read from the RAM, then convert the logical address, then read from the RAM again, slowing the entire process down significantly.

What is a TLB?

Translation Lookaside Buffer.

A memory device inside the MMU that stores the most useful entries of the page table of the currently running process.

What is a TLB miss?

When a needed entry is not in the TLB.

How is a TLB miss solved?

The entry is read from the page table in RAM and added to the TLB.

What is a TLB hit?

When a needed entry is already in the TLB.

What are the advantages of using a TLB?

- You don't have to store the entire page table.

- Faster context switches

- Only have to access RAM when a TLB miss occurs.

What is a thread?

An independent execution of program code with its own program counter

Is threading exclusive to multi-core CPUs?

No. A single-core CPU can have more than one thread.

How do servers use threading?

One thread is listening to requests from the internet, and every time a new request is received, a new thread is executed to serve that request.

Why choose threads over creating a new process (forking)?

- More memory efficient (stored in process' already allocated memory)

- Faster to create and delete

- Shares memory for free

- Context switching is faster

Why choose processes (forks) over threads?

- You can run exec() to run a different program in the same process

- Fault independent. If a fork experiences an error, only itself will crash rather than the entire process tree.

Where does a thread get stored in RAM?

In the original process' chunk of memory. A new stack is created in this chunk, and it belongs to the thread. Stack overflow could occur.

Do threads have their own heap, text, and data sections?

No. It shares it with the process it belongs to.

What do threads of the same process share?

- Text section

- Data section

- Heap

How do you initialize a thread in C++?

#include

std::thread t1{ function() }

Why is getting the correct result from a race condition a problem?

A correct result gives the illusion that everything is working as intended when in reality the program has issues.

What is a race condition/data race?

A mistake or data corruption when one or more thread or process try to simultaneously access the same piece of memory and at least one of them try to modify it.

What is a critical section?

A piece of code that should not overlap in execution with other critical sections. Problems happen when they do overlap.

What are hardware-implemented atomic functions?

Implemented in the CPU as wires and logic gates

Functions with two properties:

1) Once it starts, it finishes. It is impossible to interrupt it.

2) Only one copy of an atomic function can run at a time.

They are basic tools that allow us to make tools to prevent race conditions.

What is a mutex?

A mutually exclusive access to a resource. It's a special case of a semaphore with a maximum concurrency of 1.

How do you use a mutex in C++?

#include

std::mutex for_glob;

for_glob.lock();

(code here)

for_glob.unlock();

What is a memory address? How much memory can you address with addresses of a given size (for example, 64-bit addresses)

A number that identifies a section of memory. You can have 2^64 different addresses in a 64-bit system

Why physical addresses are inconvenient for modern programs?

A process may not always be placed in the same chunk of memory every time, so if it is always trying to access a specific address, such as 123, it may be trying to access memory that doesn't belong to it.

In addition, if two processes of the same program try to access the exact same physical address, it could lead to memory problems.

What kind of address does the CPU fetch with instructions?

Logical address

What kind of address does the CPU send to RAM with a load/store request?

Physical address

What kind of address arrives to RAM with the load/store request?

Physical address

What is internal fragmentation?

A scenario where the allocated memory for a process is larger than the requested memory, leaving unused space within a page, wasting memory in the process

What kind of fragmentation does contiguous memory management suffer from?

External fragmenation

What kind of fragmentation does paging suffer from?

Internal fragmentation

How do sizes of pages and frames relate?

Page and frame sizes are the same.

How many page tables are there in a system?

There are as many page tables as there are running processes.

What are synchronization problems?

Programing problems that arise when you create multithreaded code or a program that exchanges data with other program

What are some examples of synchronization hazards?

Race condition and deadlock

What is a shared resource?

Anything that is used by multiple threads, processes, or devices

How can a race condition can happen?

When two threads run a critical section at the same time, want to access the same memory address, and at least one of them wants to modify it.

Can a race condition happen if only one party modifies the data and the others are just reading?

Yes

Can a race condition happen if everybody is just reading?

No

Explain the idea of locking shared resources.

By providing exclusive access to shared resources to one thread at a time, you can prevent race conditions where one or more thread reads from memory and at least one thread writes to that same memory.

What does it mean if the function is hardware implemented?

There is no program code for it, no general CPU instructions written in memory. The function is implemented with hardware circuitry and called with a single special CPU instruction.

What does the join() function do?

It pauses the thread and it waits for another thread to terminate before continuing

What does a process do if it needs a mutex that is busy?

it pauses somehow and waits for mutex to be free again before proceeding further

What is a Producer-Consumer problem (a.k.a. Bounded Buffer problem)?

There is a producer, which is a thread that produces something such as video frames.

There is thread of processes called consumer, which consumes whatever useful item that is produced.

The Producer-Consumer problem involves programming a producer and consumer so that if a producer creates an item and there is no space on the shared buffer (array), then the producer waits. If there are no items in the shared buffer, then the consumer waits.

What is a Readers-Writers problem?

There are processes/threads wanting to read from a shared piece of data, and there are some that want to write to that data.