Week 3 Flashcards by Franklin Hole

What is a process scheduler (allocates CPU time)?

Allocates CPU time to various processes

How well did you know this?

Not at all

Perfectly

What are the 4 Scheduling Algorithms?

First Come First Served (FCFS)

Round Robin (RR)

Shortest Process Next (SPN)

Multilevel Queueing

How well did you know this?

Not at all

Perfectly

What is First Come First Served (FCFS)?

Processes get executed in order they arrive

Not interrupted until finishes or reaches a wait state

How well did you know this?

Not at all

Perfectly

What are the Pros and Cons of FCFS?

Pros:

Simple and easy to implement

Reduced context switching

Intuitively fair

No starvation

Cons:

Convoy effect - Long waiting time, poor responsiveness

How well did you know this?

Not at all

Perfectly

What is Round Robin (RR)?

allocates each task an equal share of the CPU time

How well did you know this?

Not at all

Perfectly

What are the pros and cons of RR?

Pros:

Fair CPU Allocation

Responsiveness

No starvation

Cons:

Time quantum sensitivity

Context switch overhead

How well did you know this?

Not at all

Perfectly

What is Shortest Process Next (SPN)?

Select the process with the shortest execution time

Non Preemptive - something cannot be taken away or interrupted

How well did you know this?

Not at all

Perfectly

What are the pros and cons of SPN?

Pros:

Better average waiting time

Responsiveness

Cons:

Estimating process execution time

May lead to starvation

Longer processes wait longer

How well did you know this?

Not at all

Perfectly

What is Multilevel Queueing?

a CPU scheduling algorithm

divides a ready queue into multiple smaller queues

How well did you know this?

Not at all

Perfectly

What is Fixed-Priority Scheduling?

High priority queues are executed first

May lead to starvation

How well did you know this?

Not at all

Perfectly

What is Time Slicing?

A time slice for each queue

Eg. 60% for interactive, 30% system, 10% batch

How well did you know this?

Not at all

Perfectly

What are the pros and cons of Multilevel queueing?

Pros:

Supports different performance objectives

Cons:

Complex and difficult to calibrate

How well did you know this?

Not at all

Perfectly

What is a multi core processor?

A multi-core processor has multiple processing units (cores) on a single CPU chip

Each core has its own L1 cache memory

There is a cache hierarchy

How well did you know this?

Not at all

Perfectly

What is the common queue?

When a processor becomes available, it chooses a new process from a common queue

How well did you know this?

Not at all

Perfectly

What are private queues?

When a processor becomes available, it chooses a new process from its private queue

How well did you know this?

Not at all

Perfectly

What are the 2 methods for efficient Multi-Processor Scheduling?

Load Balancing

Processor Affinity

How well did you know this?

Not at all

Perfectly

What is Load Balancing?

Evenly distribute processes among CPU cores

Common ready queues automatically enforce load balancing

What is Processor Affinity?

Keep a process on the same CPU core(s)

Soft affinity: only move processes if there is a good reason

Private queues automatically enforce processor affinity

What is The Linux Scheduler?

A multi-queue scheduler

Scheduling domain: a set of CPU cores than can be balanced against each other

Bottom-up Load balancing among domains

Processor affinity - only perform load balancing if there are severe imbalances

What is monoprogramming (single, single)?

Running a single program at a time within a single address space

What is multiprogramming?

allows multiple programs to run simultaneously on a single CPU

basic form of parallel processing

What are the 3 Memory Management Tasks?

Relocation

Protection

Sharing

What is Relocation(hint: new location in m)?

Moving a process to a new location in memory without disrupting its execution

What is Protection?

User processes need to be protected from each other

System processes should be protected from user’s processes

What is Sharing (processes may)?

Processes may sometimes need to share data

What is (Fixed/Static) Partitioning?

Memory is divided into partitions of fixed boundaries (equal or unequal sizes) 1-1 mapping of partitions and processes

What are the pros and cons of Fixed Partitioning?

Pros: Easy to understand or implement No external fragmentation Cons: Internal fragmentation Limited by number and size of partitions

What is Dynamic Partitioning?

Exact memory allocation - only what is needed Partitions of variable length and number 1-1 mapping Starts well then leads to external fragmentation

What is External Fragmentation?

Space is wasted between partitions

What is Compaction?

combining all the empty spaces together and processes Fixes external fragmentation

What are the pros and cons of Dynamic Partitioning?

Pros: No internal fragmentation More efficient than static partitioning Cons: External fragmentation Overhead of compaction

What is Simple Segmentation?

Process divided into segments Segments loaded into memory Segments do not need to be contiguous

What are the pros and cons of Simple Segmentation?

Pros: Sharing and Protection Better handling of larger programs No internal fragmentation Cons: External fragmentation (< dynamic)

What is Virtual Memory Segmentation?

Segmentation + Virtual memory Segments can be swapped between memory and disk storage OS loads segments into memory as needed

What is virtual memory?

Use of disk space to extend main memory; illusion of larger memory but much slower

What are the pros and cons of Virtual Memory Segmentation?

Pros: Can fit processes larger than memory Cons: More complex memory management

What is Simple Paging?

Memory divided into equal fixed-size frames Process is divided into same-size pages

What are the pros and cons of Simple Paging?

Pros: No external fragmentation Simple memory allocation Cons: Small internal fragmentation Page tables can become large

What is Virtual Memory Paging?

Paging + Virtual memory Pages loaded into frames as in simple paging, except that not all pages need to be loaded at same time

What are the Pros and Cons of Virtual Memory Paging?

Pros: Can fit processes larger than memory Cons: adds complexity (overhead)

Protection & Sharing with Segmentation and Paging

Goals: Protection: Each process can only access its own pages/segments Sharing: Multiple processes can access the same page/segment Implementation: Each frame/segment has a number of protection bits specifying read, write, execute permissions, which processes have these permissions Protection/sharing is generally easier with segmentation than with paging since Segment table is smaller than the page table Segments are more natural units for protection/sharing