Transcript Review Ch 8--12 - network systems lab @ sfu

CMPT 300: Final Review
Chapters 8 – 12
Memory Management: Ch. 8, 9
 Address spaces

Logical (virtual): generated by the CPU

Physical: seen by the memory unit
 User program deals with logical addresses; never sees physical
addresses
 Mapping from logical to physical addresses

Static: done at compile-time

Dynamic: done at load or execution time
2
Memory Allocation
 Memory is usually divided into two partitions for:

Kernel: usually held in low memory

User processes: usually held in high memory

Typically, the two partitions are managed differently
 Memory allocation


Contiguous

First-, Best-, Worst-fit

Fragmentation: external and internal
Paging, segmentation, virtual memory
3
Paging
4
Segmentation
1
4
1
2
3
2
4
3
user space
physical memory space
5
Segmentation Hardware
6
Paging and Segmentation
 Paging issues:

Page size


Internal fragmentation and page table size
Page table (one table for each process)

Access time: use cache (TLB)

Size: use two- or three-levels page tables
use hashed or inverted page tables for > 32 bits
architectures
 Segmentation: variable size

External fragmentation

Facilitates sharing of code and data (share the whole segment)
 Combined Segmentation + paging:

Example Intel Pentium
7
Virtual Memory
 Logical address space can be much larger than physical address
space
 Only the needed parts of the program are brought to memory for
execution
 Allows address spaces to be shared by several processes
 Allows for more efficient process creation
 Virtual memory can be implemented via

Demand paging

Demand segmentation
8
Virtual Memory and Page Fault
9
Page Replacement
 When we need to bring a page from disk and there is no free frame:

Find a victim page to evict from memory
 Objective: minimize number of page faults (they are very costly)
 Replacement algorithms

FIFO, OPT, LRU, second-chance, …
10
Thrashing
 Thrashing  a process is busy swapping pages in and out more
than executing (because OS allocated too few frames to it)
11
Locality Model
 As a process executes, it moves from locality to locality, where a
locality is a set of pages that are actively used together

Locality could be: function, module, segment of code, …
 Locality model helps us to estimate the working set of a process

Working set: pages that are actively being used (within a
window)
12
Allocating Kernel Memory
 Treated differently from user memory because


Kernel requests memory for structures of varying sizes

Process descriptors (PCB), semaphores, file descriptors, …

Some of them are less than a page
Some kernel memory needs to be contiguous


some hardware devices interact directly with physical
memory without using virtual memory
Virtual memory may just be too expensive for the kernel (cannot
afford a page fault)
13
Kernel Memory: Buddy System
14
Kernel Memory: Slab Allocation
15
File Systems: Ch. 10, 11, 12
Application Programs
Logical File System

Interface: file and directory structure
 Maintains pointers to logical block addresses
Implementation: block allocation, …
 Maps logical into physical addresses

File-organization Module
Device Drivers

Implementation: device-specific instructions
 Writes specific bit patterns to device controller
Storage Devices
16
File System Interface
 Files


The smallest storage unit from the user’s perspective

A collection of blocks on the disk from OS’ perspective
Directory structure

Tree-structured with links (general graphs)

Each file has an entry in the directory
17
File System Implementation
 To implement a file system, we need


On-disk structures, e.g.,

directory structure, number of blocks, location of free
blocks, boot information, …

(In addition to data blocks, of course)
In-memory structures to:

improve performance (caching)

manage file system
18
On-disk Structures
Free block
Boot block
Superblock
Directory structure
File control block
Data block
19
Opening and Reading from a File
20
Block Allocation
 Allocate free blocks to files to achieve efficient disk space
utilization, and fast file access
 Three common allocation methods

Contiguous

Linked

Indexed
 OS keeps track of free blocks using

Bitmaps

Linked lists
21
Combined Scheme: UNIX inode
22
Disk Structure and Scheduling
 Disk structure

cylinders, tracks, sectors, logical blocks
 Disk operation

Move the head to desired track (seek time)

Wait for desired sector to rotate under the head (rotational
latency time)

Transfer the block to a local buffer, then to main memory (transfer
time)
 Disk scheduling

To minimize seek time (head movements)

Algorithms: FCFC, SSTF, SCAN, LOOK
23
Warp Up: What We Have Covered
 How to manage resources in a single computer
24
Warp Up: What We Have NOT Covered
 How to manage resources distributed over multiple computers

CMPT 371: Computer Networks


Protocols and algorithms to make computers talk to each other
CMPT 401: Operating Systems II

Distributed file systems, distributed synchronization, interprocess communications, consistency and reliability, security
 Special-purpose operating systems, e.g.,

Real-time OS

OS on small devices (PDAs, sensors,…)
25
That is it with CMPT 300!
Good Luck on Your Final
26