Summary 2

Question 1

Memory management

Answer 1

the technique for mapping virtual address spaces to

physical memory

Question 2

Physical memory

Answer 2

memory that is directly accessible to the CPU; operates at

high speed, but typically offers lower capacity than storage

Question 3

Disk

Answer 3

a storage device that uses a magnetic storage mechanism. Not all data fits
into physical memory, so the disk holds data until it is pulled into physical
memory

Question 4

Fixed partition scheme

Answer 4

a strategy for translating virtual to physical addresses
in which we divide the memory into partitions such that one process is loaded per
partition and queue processes that are waiting to be loaded into memory. Uses a
fixed offset to convert between physical and virtual addresses

Question 5

Base and limit registers

Answer 5

strategy for translating virtual to physical addresses
in which the base register contains the value that gets added to the virtual
address to determine the physical address, and the limit register contains the
highest address that the program cannot surpass. Requires hardware support to
implement.

Question 6

Bitmaps

Answer 6

in tracking free space in memory, a bitmap is a vector in which each
digit is 1 or 0 depending on whether a given memory chunk is free or not

Question 7

Linked list

Answer 7

in tracking free space in memory, the elements of the linked list
represent blocks of memory that are free

Question 8

Worst-fit

Answer 8

a memory allocation scheme that finds the largest block of free
memory possible and stores the process in it

Question 9

Best-fit

Answer 9

a memory allocation scheme that finds the smallest hole which is large
enough to fit the process and stores the process in it

Question 10

First-fit

Answer 10

a memory allocation scheme that puts the process in the first
discovered hole of free memory that is large enough to fit the process

Question 11

Internal fragmentation

Answer 11

internal to an allocated space, internal fragmentation is

where a process is allocated more bytes than it uses

Question 12

External fragmentation

Answer 12

space that the OS is aware of, but that is too small to fit

new processes

Question 13

Page

Answer 13

A continuous portion of memory that is treated by the operating system as
a single unit of storage

Question 14

Slab allocation

Answer 14

break large chunks of memory given to a process by the Buddy

algorithm into smaller units for allocation

Question 15

Object caches

Answer 15

freed objects are stored in a cache in case they are allocated
again, rather than freeing them for allocation to other processes

Question 16

Virtual memory

Answer 16

virtual memory is the memory that is allocated to a process for storing
its in-memory state. It is considered “virtual” because at creation, it is not yet mapped
into physical memory locations. Virtual memory is broken down into the code, data,
stack, and heap segments, creating a standardized memory representation between all
processes. Virtual memory offers the OS a complete separation of logical and physical
addresses

Question 17

Segmentation

Answer 17

divides the address space into variable sized segments or logical
addressable units. These include the code, stack, heap, and data segments

Question 18

Virtual memory page

Answer 18

a contiguous block of virtual memory addresses of a fixed range,
which is the same as page frames. A page is the smallest unit of addressability to virtual
memory available to the OS for memory management. Pages will not contain addresses
from different segments of virtual memory

Question 19

Page frames

Answer 19

a contiguous block of physical memory addresses of a fixed range, which
is the same as the size of virtual memory pages. Virtual memory pages swapped into
main memory from storage are mapped to page frames.

Question 20

Paging

Answer 20

Paging is the technique by which the OS swaps in various virtual memory
pages as they are needed as virtual memory is typically much larger than physical
memory.

Question 21

Memory Management Unit (MMU)

Answer 21

translates virtual addresses to physical addresses.

Divides the virtual address space into pages

Question 22

Disk controller

Answer 22

enables the CPU to communicate with the disk storage

Question 23

Swap file

Answer 23

space in the hard disk that operates as an extension of the RAM for portions
of the process virtual memory that do not fit in RAM. Pages can be stored in the swap
file to create room for other processes to execute in RAM.

Question 24

Page table

Answer 24

a table exists for each process to map from a page number to page frame
○ Validity bit: stored in the page table; 1 if a page is in memory and 0 if it is not
○ Protection bit: stored in the page table; set to read, write, or execute depending
on the segment
○ Reference bit: stored in the page table; allows us to detect pages that are
frequently used by setting this bit to 1 when a page is accessed
○ Modified (“dirty”) bit : stored in the page table; set to 1 if a page has been
written to and 0 otherwise (on pure reads)

Question 25

Multi-level paging

Answer 25

divide up the virtual addresses such that the highest order group indexes into a top level page table, the second highest order group indexes into the next level page table, and so on. When looking up in a multi-level page table, the corresponding bits of the page number are used to index into each level until we get to the page table of interest. This strategy is used because virtual memory is often larger than physical memory and each process has its own page table, thus the total amount of memory required to store page tables needs to be managed.

Question 26

Transaction lookaside buffer (TLB):

Answer 26

small cache maintained within the MMU hardware to lookup pages before we go to main memory to retrieve the page table. The TLB is associative memory.

Question 27

Inverted page table

Answer 27

stores entries in the form of (page-frame, process ID, and page number), which is like a hash table, to help find the desired page frames and avoid a linear search of the page table

Question 28

Offset

Answer 28

in the offset number, the lower order bits correspond to the offset at which we want to access addresses within a given page, and the higher order bits represent the page we want to access

Question 29

Page fault

Answer 29

hen a page is requested but is not currently in physical memory; causes a trap to the kernel

Question 30

Page replacement

Answer 30

when a page is required, but physical memory is full, the page replacement process selects one of the current pages in physical memory to be written ut to disk ○ FIFO: replace the longest resident page that is already in memory ○ Other policies include: second-chance algorithm, clock algorithm, least recently used algorithm (LRU), approximate LRU ○ Stack property: incrementing the amount of frames from m to m+1 cannot increase the number of page faults ○ Belady’s Anomaly: some page replacement policies do not respect the stack algorithm property

Question 31

Denial of service attacks

Answer 31

bad attackers try to overwhelm a web server by making requests at the same time, using up all the resources on the web server; it can often be difficult to distinguish the fake traffic from legitimate network traffic

Question 32

Event-driven programming

Answer 32

rather than using blocking system calls, event-driven programming allows higher performance and resource utilization by allowing functionality to continue or sleeping until the desired event occurs ○ Event loop: ○ Event handlers:

Question 33

Network stack

Answer 33

○ OSI model: a formal, standard representation of networking that splits the network functionality into seven layers. ○ Internet model: an informal representation of networking that splits the network functionality into five layers. This model groups the “application, presentation, and session” layers of the OSI model together. ■ Physical layer: includes the actual wires and wireless links that move bits between two physical systems ■ Data link layer: determines how the raw bytes should be transferred over the physical links. In particular, the link layer puts raw bytes into messages, performs error detection and correction in transferred data, includes functions for reliable delivery, and determines where and when to send the data over the links. ■ Network layer: includes IP and message routing within the network ■ Transport layer: includes the TCP and UDP protocols; creates network communication channels between different processes on the same or on different machines through the use of sockets ■ Application layer: includes all the user level processes that require network communication. OSI model splits this into three layers: session, presentation, and application.

Question 34

Interface

Answer 34

accepted form of representing and accessing data such that the user can decode the information

Question 35

Protocol

Answer 35

rules and formats that govern communication between two entities over the network or network boxes

Question 36

Data link layer

Answer 36

○ Data frame : grouping of raw data bits; the recipient can identify the frames by the particular sequences of bits that represent the start and end ○ MAC address: unique address that identifies your network card; 48-bit address space

Question 37

Network layer

Answer 37

○ Packet: a method of wrapping data with its control information (e.g. its error detection codes, destination, etc.) ○ Router: a networking device that is connected to multiple network links and determines where to send a packet based on its ○ Switch: within a given network, switches forward messages between devices

Question 38

Encapsulation

Answer 38

each layer can only see the service provided by the layer | immediately below it

Question 39

Device drivers:

Answer 39

a separate device driver exists for each device; the device driver is software that interacts with the interrupts generated by its respective hardware component, acting as an interface between the external devices and the OS; the driver usually runs as a process ○ Interrupt handler : a separate interrupt handler exists for each device that may generate an interrupt; executes (e.g. as a callback function in C) on interrupt; the device driver communicates with the OS through interrupts

Question 40

Device controllers

Answer 40

a hardware component that receives data from its respective device, stores it locally, and passes it to the device driver; the controller makes sense of signals going in and coming out from the CPU ○ Device registers : allow the device driver to read and write status of the devices like checking whether a printer is ready or not ○ Data buffers : enable one to write data to the controller, which is then subsequently pushed onto the external devices; any data that we write to the disk, or read from the disk, is first buffered in the data buffers of the device controllers, then can be read by the device drivers

Question 41

Port-mapped I/O

Answer 41

special assembly language instructions that allow the device | driver to read directly from the external device

Question 42

Memory mapped I/O

Answer 42

reading or writing to particular addresses that correspond to a location in main memory, control register, of address in the data buffer of a specific I/O device. I/O operations at these addresses are automatically converted to corresponding device control registers or data buffers, reducing the burden on the programmer. This technique requires memory caching to be disabled and the MMU to distinguish the I/O requests from legitimate memory accesses.

Question 43

Direct memory access (DMA)

Answer 43

to avoid involving the CPU in the data transfer between the physical memory and external device, a separate hardware co-processor called the DMA is tasked with handling I/O requests

Question 44

Checksum

Answer 44

a sequence of characters, generated by applying cryptographic hash function to data (e.g. in a file). Using the checksum, a system can validate whether different copies of data match.

Question 45

ioctl system call

Answer 45

allows your user application to make requests of devices and is typically used for the purposes of hardware configuration, command line interface, and building upon kernel functionality

Question 46

I/O scheduling

Answer 46

many processes create I/O requests and the I/O scheduler determines the order in which to send these requests to the external devices while preserving interactivity

Question 47

Networking and the OS Endpoint

Answer 47

a remote device capable of communication over a TCP/IP network

Question 48

Networking and the OS Socket

Answer 48

a network abstraction uniquely defined by an IP address and port number; a network abstraction used to receive and send data from a give endpoint identified by the IP address for the network service identified by the port number; sockets allow inter or intra machine processes to communicate over the network ○ IP address : 32-bit number (in IPv4) and 64-bit number (IPv6) used to identify network endpoints and their location in the network ○ Port number : 16-bit unsigned integer; ports are associated with the IP address of the machine being used in networking and the type of network protocol being used in the communication; each port is used to handle a different network service so that the machine can execute multiple services and sessions of the same service; port numbers 0-1023 are reserved for well-known services and port numbers 1024+ can be used by a developer in general applications

Question 49

Networking and the OS Socket API

Answer 49

a common set of functions, data structures, and constants across many OSes used to maintain and interact with sockets; Key functions include: ○ socket() : creates a socket ○ bind() : defines the socket port ○ listen() : sets the socket to start listening for data after it has been bound ○ connect() : initiates a connection with another socket ○ accept() : accepts a connection initiated by another socket ○ send() , sendto(), write(): send data flowing out of the socket ○ recv() , recvfrom, read(): receive data flowing into the socket ○ close() , shutdown() : closing a socket

Question 50

Domain name system (DNS)

Answer 50

a protocol used to map hostnames to IP | addresses, which is used to identify well-known servers in the network

Question 51

Network interface cards

Answer 51

hardware component that connects a machine to the | network

Question 52

Device drivers for networking

Answer 52

software interrupt handlers for different Network | Interface Cards

Question 53

Little-endian

Answer 53

store lower order bytes in the lowest memory locations

Question 54

Big-endian

Answer 54

store higher order bytes in the lowest memory locations

Question 55

Stream socket

Answer 55

uses TCP as the underlying protocol; connection-oriented, such that, providing a two way stream of bytes; guaranteed reliable, at-most-once, and in-order delivery

Question 56

Datagram socket

Answer 56

uses UDP as the underlying protocol; connectionless, sending individual messages as chunks of bytes; no guarantees of reliable, at-most-once, and in-order delivery

Question 57

System calls for files

Answer 57

○ fopen() : open file for reading and writing ○ fwrite() : writes data to a file ○ fseek() : sets the position of the stream to the given offset, allowing seeking a specified part of the file ○ fread() : read from the file ○ fclose() : close the file

Question 58

Disk block

Answer 58

basic logic unit of storage on disk of a contiguous set of bytes

Question 59

Disk partitions

Answer 59

logical split of the actual disk drive. The operating system views each partition as a distinct disk, and different operating systems may be run in each split; each partition has at least one directory, in which all the partition’s files are listed.

Question 60

internal structure of the disk partition

Answer 60

○ Boot block: contains information on the disk layout and code for loading the operating system into the kernel space ○ Superblock: contains basic information about the file system, including the file system size, list of free blocks, list of allocated blocks, and time of the last modification to the partition; the superblock can be read into memory at boot time ○ Free space data structure: tracks the free blocks in the disk ○ I-nodes list : stores information about the individual files stored on disk, and allocatable blocks for directories and file systems

Question 61

Master boot record

Answer 61

stores information about the entire drive

Question 62

Partition table

Answer 62

specifies the beginning of each partition

Question 63

Disk space allocation

Answer 63

managing data in the disk with the aims to ensure fast sequential access, fast random access, the ability to grow a file system quickly, and to minimize fragmentation ○ Contiguous allocation : each file occupies a contiguous region of blocks ○ Linked-list allocation : hold a linked list of blocks for each file such that each block contains a pointer to the next block ○ File allocation table : stores a condensed version of the linked list to be stored at the beginning of the file system; the file is stored in allocated clusters ○ Linked list with indexing or i-nodes = supports direct access to the file’s blocks by storing files in the i-node data structure ■ i-node (index node) : a kernel structure storing information about each file in the file system; contains a pointer to the disk blocks containing the file’s data, and information such as the file permissions, ownership, modification time, and file type

Question 64

Directory

Answer 64

a file that holds the list of filenames and their inodes; provides information needed to find the disk data blocks of a file

Question 65

Hard links

Answer 65

to represent two different paths for a file, create a single i-node and have two directory entries that point to the same i-node; relies on the link-counter ○ Link-counter: counts the number of ways that an i-node can be retrieved along different paths

Question 66

Symbolic/soft link

Answer 66

the original file has its own i-node and for each reference or path to the file, there is a separate i-node, of type LINK, for a file that just contains the path name to the original file

Question 67

Free space management

Answer 67

tracking unallocated blocks in a portion of the disk partition ○ Bitmap: maintains for the entire disk partition with one encoding the fact that the block of a particular number is free and zero otherwise ○ Linked list: list storing the free blocks

Question 68

In-memory cache

Answer 68

uses a scheme to store blocks that are likely to be requested from disk, to shortcut the need for a disk search and propagate the data to the requesting process ○ LRU scheme : given the limited in-memory cache size, evicts the least recently used block from the cache when new blocks are being added in

Question 69

Incremental backups

Answer 69

every time you synchronize with your server, it will only | backup files that have been changed since the last time

Question 70

Physical backup

Answer 70

physically copy block by block from one disk to another

Question 71

Logical backup

Answer 71

copies files from one disk to another