CS 143A Midterm 1

What is an Operating System

OS is the software that acts an intermediary between the user applications and computer hardware

What are the four computer system components

Hardware, Operating System, Apllication Programs, Users

What is the CPU Execution Sequence

1. Fetch Instruction at Program Counter

2. Decode Instruction

3. Execute Instruction

4. Write results to registers or memory

5. Increase the Program Counter

Synchronous I/O

After I/O is requested, program stops executing and waits till I/O is done

Asynchronous I/O

After requesting I/O, other parts of the program can continue while one part is waiting for I/O to finish

Interrupts, what are they, how do they work, what are some special things that happen when an interrupt occurs

Interrupts are messages sent to I/O when finished

Interrupt Handler / Interrupt Service Routine is the part of the CPU that knows how to handle the interrupt, it knows where to go from the Interrupt Vector Table

Incoming interrupts are disabled while CPU is already handling an interrupt, however, a message is sent back to I/O saying that the interrupt was blocked/not-recieved and to try again.

What is DMA, how does it work

I/O has direct access to memory through the device controller, CPU is interrupted after memory-I/O interaction is complete

User Mode, what is it, what happens when privileged instructions are executed in user mode, what is that called?

Execution is done on behalf of the user

Executing priveleged in the user mode causes a trap, which is a software generated interrupt and switches the mode from user to kernal mode to handle it

Kernal Mode, What is it

Execution is done on behalf of the operating systems

Privileged instructions are only executable in the kernal modes

What are system calls

User code that causes a trap (causing switch to kernel to handle syscall).

What is a process

An instance of a program

How is timer used in CPU protection

Timer for process execution on CPU, once timer hits 0, send interrupt to switch off program (incase corrupted program is just idling on CPU)

Memory Protection: Base and Limit

Give program a certain amount of memory in the range based on two registers

Base Register holds smallest address
Limit Register Contains how much address space u can use (so max address is base+limit)

What is a command interpreter system do

Place to give commands that go directly to operating system

What is the Hierarchy for memory

1. Registers

2. Cache

3. Main Memory

4. SSD

5. Hard Drive

6. Optical Disk

7. Magnetic Tapes

What is a Monolithic Operating System

Large kernels with lots of components
Ex: Linux, Windows, MAC

What is a Microkernel Operating System, what are some advantages, vs disadvantages

Only small core components in OS, reset is dependent on User-Level Processes

Advantages:
More reliable, secure, easier to port over to new architecture

Disadvantage
- Performance is worse

What is a virtual Machine

Running one ore multiple OS’s on top of another OS (VMM)

What is the process states

New - Process is being created

Running - Instructions are being executed

Waiting - Waiting for some event to occur (ex: I/O wait)

Ready - Waiting to be assigned to processor

Terminated : Process has finished executed

What is contained in the Process Control Block

Process State

Process Number/ID

Program Counter

CPU Registers

CPU Scheduling Information (Type of scheduling going on)

Memory Management Information

List of Open Files

I/O Status Information - List of I/O Devices

Accounting Information - Time Limits

Job queue

Set of all processes in System

Ready Queue

Set of all processes in main memory that are ready and waiting to execute

Device Queue

Set of processes waiting for an I/O (I/O queue)

Context Switch, what is it, what part of the process does it save?

Thing that switches CPU from one process to another

Saves PCB state of old process and loads new one

Long-Term Scheduler / Job Scheduler

Selects which process process should be brought into ready queue, infrequent

Short-Term Scheduler / CPU Scheduler

Selects which process should execute next and allocates CPU, frequent

Medium Term Scheduler

Swaps out process temporarilyis

I/O bound process

Spends more time in I/O

CPU BOund Process

Spends more time in CPU executing

Parent / Child Process, what is copied, what is required to be allocated

When a process (parent) creates another process (child)

New PCB allocated

New Page Tables for address space

Multithreading

Splitting a process/program into threadsT

Thread, what is it, what is shared with other peer threads, what is private, what is a thread control block

Thread is simple process

Shares Content of memory (global variables, heap), and I/O State (file system, etc.) with other threads

Private to each thread → Thread Control Block, Execution Stack

Thread Control Block contains execution state, ID, Program Counter, CPU Register values, stack pointer, scheduling priority

Heavyweight Process

Task/Process with one thread

Kernal Threads

Threads supported directly by the kernel

User Threads

Threads Supported above the kernel by library calls, (thread management is done at user level)

Many-To-One

Many user level threads map to a single kernel thread

One-to-One

Each user-level thread maps to a kernel thread

Many-To-Many

Many User level threads are mapped to many kernel threads

Signal

UNIX notifications that an event happened (basically UNIX versions of interrupt)

User-Define Handler vs Default Handeler

User-Defined signal handler can overrun default, default handler will handle every signal though

Thread Pool

Pool of threads waiting for work

Multiprocessing

Multiple CPUS

Multithreading

Multiple threads per process

Multiprogramming

Multiple Processes one one CPU

Interprocess Communication (IPC), what is it, what are two ways its implemented

Can be implement by shared memory

Can be implemented by messaging system

Can do both

Increase the amount of memory available for a particular process - User or Kernel Mode

Kernel, changing amount of memory means accessing memory not given to process

Read a character from the keyboard. - User or kernal mode?

Kernal, I/O access needs kernal

Execute a matrix multiplication operation. - User or Kernal

User, Even though we use CPU, User processes can use CPU without every contacting kernal

Modify the content of an in-memory table. - User or Kernal

User - Assuming its modifying memory content that was already allocated to it for its memory space

What is the following an example of: An exception generated by the CPU at predictable places in the user code

System Call

What is this an example of: the program don’t need to wait and will be informed when event is finished

Asynchronous I/O

What is this an excample of: the program is notified when an event occurs without needing to wait

Interrupt

What is this an example of - program keep checking the state of an event

Polling

What is this an example of - a request made by a user-level program to go into kernel mode

System Call

What is this an example of - The program has to wait for the event to finish before it can proceed

Synchrnous I/O or Interrupt or trap or systemcall

What is this an example of - An event that may occur at any unpredictable point during the execution of user code

Interrupt

What is this an example of - handle events external to the processor

Interrupt

.Which one is more time efficient? Why? polling-driven implementation or interrupt implementation?

Interrupt

Are traps asynchronous or synchronous

Synchronous

Are interrupts asynchronous or synchronous

asynchronous

Trap or Interrupt - A user program executes a system call instruction (e.g., syscall)

Trap

Trap or Interrupt - A division by zero occurs during program execution

Trap

Trap or Interrupt - A timer expires causing the OS scheduler to run

Interrupt

What does the UNIX System call Open Do, What are its parameters, what does it return

Use:
- The open() function is used to open an existing file or create a new one.

Parameters:
- pathname: A string representing the relative or absolute path to the file you want to open.
- flags An integer that specifies the access mode. You must include one of the following: O_RDONLY: Open for reading only. O_WRONLY: Open for writing only. O_RDWR: Open for both reading and writing, O:CREAT: For creating a new file
- mode: This parameter is only used when O_CREAT is specified it defines the permissions (e.g., 0644) for the new file.

Return
- On success: Returns file descriptor
- On failure: Returns -1

What does the UNIX System call Close Do, What are its parameters, what does it return

Use:
- The primary purpose of close() is to release a file descriptor so it can be reused by the process (Closes the file)

Parameters:
- fd: This is the file descriptor

Return
- On Success: Returns 0
- On failure: Returns -1

What does the UNIX System call Read Do, What are its Parameters, what does it return

Use:
- Reads a certain number of bytes from a file

Parameters:
- fd: The file descriptor of the file to be read
- buf: A pointer to the buffer (a memory area) where the data read from the file should be stored.
- count: The maximum number of bytes you want to read.

Return:
- Success: Returns the number of bytes actually read. (May be less then count if EOF is reached)
- Failure: Returns -1,

What does the UNIX System call Write Do, What are its parameters, what does it return

Use:
- write() takes data from a buffer in the process’s memory and writes it to the file or stream associated with a file descriptor.

Parameters:
- fd: The file descriptor where the data will be written
- buf: A pointer to the buffer containing the data you want to save. (Data you want to write to the file)
- count: The number of bytes from the buffer that you want to write to the file.

Return:
- Success: Returns the number of bytes actually written. (Might be less then count if disk becomes full)
- Failure: Returns -1,

What does the UNIX System call Fork Do, What are its Paraameters, what does it return

Use:
- fork() is used to create a "child" process that is an almost exact duplicate of the "parent" process. The child inherits the parent's memory space (variables, stack, heap), file descriptors, and environment.

Parameters:
- None

Return Value
- In parent: Process ID of child
- In child: 0
- On Failure: -1 to parent, child is not created

Hard Real Time

Deadlines are absolute. Missing even one deadline = system failure.

Correctness depends on both the result and the timing.

Soft Real Time

Deadlines matter, but occasional misses are tolerated.

Performance degrades, but the system still works.

Not Real Time

Only correctness of the output matters, not when it arrives.

What is time-sharing

Time-sharing is an OS technique where multiple processes share the CPU by each getting a small slice of time, creating the illusion that they’re running simultaneously.

Non-Preemptive Scheduling

Once CPU has been allocated to a process, process keeps the CPU till its done (or switches to waiting state (waiting for I/O))

Preemptive Scheduling

Process can be interrupted and must release the CPU

Dispatcher (What 3 things does it do)

Performs context switch

Switches to user mode

Jumps to proper location in user program for instructions

What is dispatch latency

Same as context switching latency, time it takes for it to switch from one process to another, must be fast

CPU Utilization

Idea to keep the CPU and other resources as busy as possible

Throughput

The # of processes that complete their execution per unit of time

Turnaround Time

Amount of time to execute a particular process from its entry time

Waiting

Amount of time a process has been waiting in the ready queue

Response Time

Waiting Time + Context Switch + First Response is produced (basically waiting time till it first gets CPU)

First Come First Serve Scheduling, What is it, How do you calculate waiting time, How about turnaround time

Non-Preemptive

Just a queue of processes based on arrival time, once a process gets the CPU, it has it till it finishes

Turnaround Time = Completion Time - Arrival Time
Waiting Time = Turnaround Time - Burst Time

Shortest Job First Scheduling (Non-Preemptive), What is it, how does it work, how do calculate waiting time, turnaround time?

Each process is ordered in a queue ranked by the burst time, once a process gets the CPU, it has it till completion

Waiting Time = Turnaround Time - Burst Time
Turnaround Time = Completion Time - Arrival Time

Shortest Job First Scheduling (Preemptive), What is it, how does it work, how do calculate waiting time, turnaround time?

Each process is ordered in a queue ranked by the burs time, if a process joins the queue that is shorter then the remaining time of the process already in the CPU, the process in the CPU is switched out

Waiting Time = Turnaround Time - Burst Time

Turnaround Time = Completion Time - Arrival Time

What is the exponential Averaging Equation

𝜏_n+1 = a t_n + (1-a)𝜏_n

𝜏_n+1 - Predicted value for next CPU Burst

a - weight (between 0 and 1)

t_n - Actual length of nth burst

𝜏_n - Predicted length of nth burst

Priority Scheduling, What is it, What’s an example of it, What is a problem with it, what is a solution to it

A scheduling algorithm where a priority value is associated with each process, and a process is ranked by that priority

SJF is a priority scheme

Problem: Starvation - Lowest Priority Process may never execute

Solution: Aging- as time progresses increase the priority of the process

Round Robin, What is it, how does it work, how do calculate waiting time, turnaround time?

Processes are in a queue by arrival time, each process is allocated a certain amount of time in the CPU (Called a time quantum)

Turn Around Time = Completion Time - Arrival Time
Waiting Time = Turnaround Time - Burst Time

What is a multilevel queue, are processes assigned to queues forever

Ready Queue is separated into multiple queues

Once a process is assigned to a queue, it is in that queue permanently (no switching between queues)

What is a multilevel feedback queues, are processes assigned to queues forever

Ready Queue is separated into multiple queues with priorities

Processes CAN move between the queues

What is self-scheduled multi-processor scheduling vs manager-worker scheduling

Both these are CPU scheduling with multiple CPUs

Self-Schedule: Each CPU dispatches a job from the ready Q

Manager-Worker: One CPU schedules the other CPU

What is asymmetric Multiprocessing

When there are multiple processors (or cores), one runs the kernal, the others run the programs

What is a load balancer

Distributes load acroases all participants uniformly (distributed scheduling)

What is a periodic scheduler

There is a fixed arrival rateW

What is a demand-driven scheduler

There is a variable arrival rate

What are deadline schedulers

Priority is determined by deadline

What is the Priority Inversion problem and the inheritance solution

Priority Inversion: Higher priority process is waiting on lower priority process that is using a resource, so it isn’t getting scheduled

Priority inheritance: Low priority process inherits high priority until it has completed

Critical Selection Problem, What is it, what are its requirements

Idea n processes are competing to access shared data, only one process may be in this critical section at a time

Requiremetns
- Mutual Exclusion: No other processes can be executing critical sections while Pi is in its critical section
- Progress: If a process wants to enter critical section, and no other process is in its critical section, then it must be allowed in eventually (can’t delay indefinitely)

- Bounded Waiting: Limit on how many times x process can enter its critical section before y process can enter its.

Bakery Algorithm

Before entering its critical section, process recieves a number, holder of the smallest number enters critical section

If processes Pi and Pj receive the same number, process that comes first in process array (process with smaller index) is served first

Test-and-Set

Hardware solution to critical section problem

Uses a loop to test if lock is taken, if its not taken, it turns it to true (taken) and executes critical section, otherwise loops until lock is changed to false so that the next process can take it

boolean TestAndSet(boolean *lock) {

boolean old = *lock;

*lock = true;

return old;

}

do {

while (TestAndSet(&lock))

; // busy wait (spin)

// critical section

lock = false;

// remainder section

} while (true);

Mutex Lock

Basically the lock that implements test and set