Operating Systems

Question 1

Give OS operations for Process Management, Memory Management, and I/O Management

Answer 1

Process: 1) Create/Delete 2) Suspend/Resume 3) Inter-process Communication (IPC) Memory Management: 1) Keep track of which parts of memory are being used by whom 2) Decide which processes to load into memory when space becomes available 3) Allocated/Deallocate space I/O: 1) Buffering / Caching 2) Device Driver Interfaces

Question 2

What are System Calls used for? Give some examples of them.

Answer 2

They’re used for the user level requesting control from the kernel-level to use privileged services. Examples: fork, exec, read, write, create, etc.

Question 3

What is the difference between a monolithic OS and one that uses a microkernel?

Answer 3

Monolithic OS - All services co-exist together with no clear separation of functionality. Microkernel - Moves as much from the kernel into user-space; communication takes place between user modules using message passing. Microkernels are more reliable and secure than monolithic OS’s because they don’t have so much code running in kernel mode, but there’s some performance overhead of user-space to kernel-space communication.

Question 4

Describe the life cycle of a process.

Answer 4

(1) Process A is created, entering the “new” state. (2) A is admitted and enters the “ready” state. (3) A is allowed to run when called by the scheduler, thus entering the “running” state. (4) One of 3 things occurs: (a) An interrupt is thrown, putting it back in the “ready” state. (b) I/O or event wait, entering the “waiting” state. (c) Finishes executing, thus entering the “terminated” state.

Question 5

What is a Process Control Block (PCB)?

Answer 5

Information kept by the OS on a process, including its (run) state, ID, program counter, registers, scheduling info, etc.

Question 6

What is a Context Switch?

Answer 6

When the CPU switches to another process, saving the state of the old one and loading the saved state of the new one.

Question 7

When does preemptive scheduling apply, and why is it used?

Answer 7

It applies when: (1) When a processes switches from the running state to the ready state. (2) When a process switches from the waiting state to the ready state. It’s used because in non-preemptive scheduling, one a CPU is allocated to a process, that process keeps the CPU until it explicitly relinquishes it, thus causing it to potentially hog the CPU.

Question 8

What are some issues that may arise in multi-processor scheduling?

Answer 8

1) Cache affinity 2) Co-runner selection 3) Homogeneous vs heterogeneous processors 4) Load sharing

Question 9

What is priority inversion, and how might it be averted?

Answer 9

Priority inversion is when a higher-priority process is blocked during a lower-priority process because it’s waiting for a resource held by an even lower priority process. It can be avoided using priority inheritance! (I.e. the process holding the resource now inherits the high-priority process’s priority). -This has its own problems though, such as “chain blockings” of high priority processes by multiple lower priority processes.

Question 10

What is Rate Monotonic Scheduling (RMS)?

Answer 10

-A form of static priority preemptive scheduling. -Each task is initiated at fixed intervals and completed in a certain period -Each task must finish before the start of the next cycle

Question 11

In Proportional Sharing, what is the fractional share ( f_i(t) ) of process p_i at time t?

Answer 11

f_i(t) = weight of process i / The sum of all the process weights

Question 12

What is the ideal service time (S_i) using a resource in the interval t0 to t1 in proportional sharing? What is the lag?

Answer 12

S_i = Integral (from t0 to t1) of f_i(t) dt

lag_i(t_i) = Si(t0, t1) - actual service time

Question 13

What is the virtual time of a task in proportional sharing?

Answer 13

V(t) = Integral from 0->t of ( 1 / the sum of all the weights ) dt

Question 14

What is the Virtual Eligible Time in Proportional Sharing? What about the Virtual Deadline?

Answer 14

V(e) = the virtual time of process i + ( the actual time of process i / its weight )

V(d) = V(e) + r / the weight

NOTE: r = S_i(e,d), representing the service time a new request should receive in the interval [e,d], i.e. the service time of a request (e.g. a quantum).

Question 15

What is a monitor (synchronization)?

Answer 15

A high-level abstraction that provides a convenient and effective mechanism for process synchronization.

Question 16

What is Priority Ceiling Protocol?

Answer 16

A means of avoiding chained blocking (a result of priority inheritence).

Each semaphore has a fixed priority ceiling that = the highest priority among all the tasks that will require it.

How it works:

• Ti can access a semaphore S only if both of these conditions are met:
  
  • S is not already allocated to any other task
  • Priority of Ti is higher than the current processor celing = max(priority ceilings of all the semaphores allocated to tasks other than Ti)

Question 17

What is a Logical/Virtual Address (Same thing) vs. a Physical Address?

Answer 17

Logical addresses are generated by the CPU, whereas physical addresses are the addresses as seen by the memory unit. While logical and physical addresses are the same in compile-time and load-time address-binding schemes, logical/virtual and physical addresses differ in execution-time address-binding schemes.

Question 18

What is the Memory-Management Unit (MMU)?

Answer 18

The hardware device that performs virtual to physical address translation. They may use paging, segmentation, or relocation register techniques as part of address translation.

Question 19

True or False: User programs never see physical addresses, only logical ones.

Answer 19

True.

Question 20

What is Dynamic Loading?

Answer 20

A routine isn’t loaded until it’s called. This means better memory-space utilization since unused routines aren’t ever loaded, and can be useful when large amounts of code are needed to handle infrequently occuring cases.

Question 21

What is Dynamic Linking?

Answer 21

Linking is postponed until execution time. A small piece of code called a stub is used to locate appropriate memory-resident library routines. The stub replaces itself with the address of the routine and then executes the routine. The OS needs to check if the routine is in the current process’s memory address space.

Question 22

What are backing stores and what are they used for?

Answer 22

Backing stores are memory holders such as disks that are large enough to accomodate all copies of all memory images for all users, and are used for swapping processes in and out of memory (they hold the memory that gets swapped out).

Question 23

What are the 3 Dynamic Storage-Allocation Algorithms?

Answer 23

First-fit (find the first hole that’s big enough to allocate), best-fit (find the smallest hole big enough to allocate), and worst-fit (find the biggest hole to allocate). Worst-fit can actually often be a prime choice since it leaves the largest leftover hole, meaning there’s less fragmentation.

Question 24

What is external fragmentation vs. internal fragmentation?

Answer 24

External Fragmentation: The total memory space that exists (external to processes) but is not contiguous.

Internal Fragmentation: Memory internal to a partition (i.e. allocated) but not being used.

Question 25

What is paging used for?

Answer 25

It’s an alternative to segmentation that allows for allocation of non-contiguous memory. Physical memory is divided into fixed-sized blocks called frames, and virtual memory is divided into blocks of the same size called pages. While internal fragmentation can still occur, there won’t be any external fragmentation (since all available memory is part of a page). When allocating memory, just find the number of pages large enough to run the process and load it the program into it. Page tables are used to translate virtual addresses to physical addresses.

Question 26

What is Associative Memory?

Answer 26

A special fast-lookup hardware cache that stores frames. If a page number is in the associative memory cache, its frame can be quickly retrieved; otherwise you need to get the frame number from the page table.

Question 27

What is the Effective Access Time of a frame reached from paging?

Answer 27

Let:

• hit ratio = h
• memory access time = m
• translation look-aside buffer (TLB) search time = s

EAT = h * (m + s) + (1 - h)(2m + s)

Question 28

How is memory protection implemented in paging?

Answer 28

A valid bit is attached to each entry in the page table, indicating if the associated page is in the process’s logical address space, and is thus a legal page.

Question 29

What is the basic layout of a virtual address? What about in a multi-layered paging system?

Answer 29

Basic layout: [page number | page offset]

Multi-leveled:

• page number for the fist page table (10 bits)
• offset of address in the next page table (10 bits)
• offset from address in actual memory (12 bits)

Question 30

How do Hashed Page Tables work?

Answer 30

The virtual page number is hashed into a page table that uses separate-chaining hashing (as in once it goes to that hash, it goes through any other page numbers that might’ve hashed to it and finds the right one).

Question 31

What does a virtual address look like in segmentation?

Answer 31

<segment number : offset></segment>

Question 32

What is the structure of a virtual address in an Inverted Page Table scheme?

Answer 32

<pid : page number offset></pid>

Question 33

What is Virtual Memory?

Answer 33

Mapping address space in memory (RAM) to address space on the Disk.

Question 34

What is a Process?

Answer 34

A program and the data structures required to run it.

Question 35

What is Physical Memory?

Answer 35

RAM

Question 36

What is a page fault?

Answer 36

A virtual address was translated in the PTE (Page Table Entry), but the valid bit was 0, meaning there’s no valid corresponding page. Consequently, a new page has to be loaded to RAM from Disc.

The opposite of this is a page hit, same as a cache hit.

Question 37

What does it mean for RAM to be fully associative?

Answer 37

It means that any page in Disc memory can go into any RAM page.

Question 38

What is a virtual page?

Answer 38

A tag for a Physical Page (the page in RAM). If the virtual page number is in the PTE (Page Table Entry) and the valid bit is 1, that means that the page is in RAM and you can immediately access it! Otherwise (page fault), you’ll need to load a new page from Disc, either evicting an old one or filling in a place in RAM that wasn’t already occupied.

Question 39

What assigns pages?

Answer 39

The operating system. When a program starts up, the OS will create a page table for it consisting of potential disc memory addresses it can use. It’s in charge of making sure that programs don’t have overlapping disc pages.

Question 40

What is a physical address?

Answer 40

An address in RAM. For a 20-bit address, the first 12 are the physical page, and the next 8 are the offset in that page.

Question 41

What are the benefits of Virtual Memory?

Answer 41

1) Programs have more potential address space
2) Address Security: the OS can keep actual addresses hidden from programs (thus preventing modification / access of memory that a program shouldn’t be able to modify / access)
3) Memory sharing: programs can share the same physical memory by having their virtual addresses translate to the same physical address in RAM.

Question 42

What is a bootstrap program?

Answer 42

The first program that runs when a computer boots up.

Initializes all aspects of the system, e.g. CPU registers, device controllers, and memory contents.

Locates, loads, and starts executing the OS kernel to start the OS.

Question 43

What is a GPU?

Answer 43

Graphics Processing Unit

Present on graphics cards or embedded in the motherboard.

A specialized electronic circuit designed to rapidly manipulate memory to accelerate image display.

Question 44

What is a cluster?

Answer 44

A group of computers that share storage and are connected via a LAN or something similar.

Benefits of a cluster include high availability.

Question 45

What are the two main modes of operation in a computer?

Answer 45

Kernel mode - Generally inaccessible by user programs (except through system calls)

User mode - Cannot execute privileged instructions

Question 46

What is a file?

Answer 46

A collection of related information defined by its creator (it’s as general as it sounds)

Question 47

How can you avoid deadlocking processes?

Answer 47

You avoid deadlocks by preventing a process from acquiring locks that another process could already hold. There are two main ways to do this:

If possible: restrict processes to only being able to have one lock at a time.

Otherwise: Enforce a lock-acquiring order.

Question 48

What is livelock?

Answer 48

Deadlock occuring from two processes changing in such a way that they keep preventing each other from progressing. A real-life example is two people trying to get around each other in a hallway, and blocking each other in the process.

A common way for livelock to occur can be two objects attempting deadlock-recovery tactics at the same time.

A way to solve livelock is to make it so that only ONE process attempts to avert the deadlock. This means that the recovery should be instigated by an outside arbiter that decides between the two.