Shared Flashcard Set

Details

CS411
Operating Systems II
73
Computer Science
Undergraduate 4
12/05/2011

Additional Computer Science Flashcards

 


 

Cards

Term
What is the "top half", and how does it differ from the "bottom half", from the context of interrupts?
Definition
The top half is the actual interrupt handler, while the bottom half is the deferred, non-time critical portion.
Term
Describe interrupt context. How does it differ from process context?
Definition
Interrupt context is not allowed to sleep. Has no backing process.
Term
Draw the general path of an interrupt through the system.
Definition

Device sends interrupt to CPU.

CPU hands to kernel.

Switch to kernel mode.

Gets processed by kernel.

return / accept new interrupt

Term
There are 3 methods of implementing bottom halves. What are they? How do they differ?
Definition

tasklets have greater serialization guarantees

(softirqs have none)

Work queues are scheduled, rather than run in interrupt
context.

Term
What is the path a system call takes?
Definition

user library makes system call, which traps to kernel,

  processes system call,

and returns to user library 

Term
The kernel’s linked list implementation is fairly unique in the way in which it is used. Describe how to create a list with your own data.
Definition

Don't add your data to the linked list struct...

 add the linked list struct to your struct of data. 

Term
What is the kernel implementation of a queue called?
Definition
kfifo
Term
For what purpose was the kernel map intended?
Definition
Mapping unique IDs
Term

Basic unit of memory management?

Hardware that manages it? 

Definition

page

 the MMU 

Term
The kernel's 3 memory zones, and their ranges?
Definition

ZONE_DMA = less than 16MB

 ZONE_NORMAL = 16MB - 768MB

ZONE_HIGHMEM = >768MB 

Term
Kernel's equivalent of malloc()?
Definition
kmalloc()
Term

What is the SLAB?

 First used where? 

Definition

SLAB is a generic data structure caching layer

 First introduced in Solaris 

Term
What does it mean to have a flat address space?
Definition
Linear and contiguous.
Term
What is the mm_struct, and for what is it used?
Definition

the memory descriptor

(the kernel's representation of the process's address space) 

Term
What is a block device?  How is it different from a char device?
Definition

A character device is a stream of characters.

  A block device provides random access to block sized chunks of data. 

Term
Just as the kernel has a basic unit of memory, block devices have a basic unit of storage. What is it at the hardware level? At the software level?
Definition

hardware unit of memory = sector

software unit of memory = block 

Term
What is the size range of the software level basic unit of storage?
Definition
sector <= block <= page
Term
What structure in the kernel maps data in memory to data on disk?
Definition
buffer_head struct
Term
Explain the relationship between the struct bio, struct bio vec, and struct page.
Definition

struct bio has a pointer to a list of bio_vec structs, and another pointer to the currently indexed member of that list.

Each bio_vec struct points to a page struct where the buffer resides. 

Term
Describe the naming conventions that should be used in the Linux kernel.
Definition

lowercase with underscores for variables and functions. 

not CamelCase.

descriptive.

Term
The basic block I/O access algorithms are known as elevators. Explain where this name comes from.
Definition

From elevators.

They service all requests in a single direction before going in the opposite direction. 

Term
Which elevator to use to manage I/O for a solid state disk?
Definition
noop
Term
Describe a critical region.
Definition

A section of code where multiple threads could be reading or writing the same data, in an unpredictable order.

 

code path that accesses and manipulates shared data

Term
Why is synchronization of processes necessary?
Definition

To avoid race conditions and deadlocks?

 

 

To ensure that unsafe concurrency is prevented and that race conditions do not occur

Term
Describe deadlock.
Definition
2+ processes, each waiting for an event only the other can cause
Term
There were 4 conditions that must be met for deadlock to occur. Name 2 of them.
Definition

1. mutual exclusion

2. hold and wait

3. no preemption

4. circular wait 

Term
What algorithm is used when dealing with deadlock in modern systems?
Definition

They put an ostrich in a room with deadlock. The ostrich puts its head in the sand and can see nothing.  It then kicks the shit out of deadlock, which it has mistaken for a lion.

 

lol great answer

Term
The Linux kernel has a specific programming methodology in order to avoid even possible resource deadlock. Describe it.
Definition
number resources
Term
What does it mean for an operation to be atomic?
Definition
It is guaranteed to occur in its entirety, or not at all.
Term
We discussed the difference between atomicity and ordering. Please summarize this discussion.
Definition
Compilers will get smart and condense and even reorder lines of code. Atomicity ensures that an operation must occur, but it does not ensure the order.
Term
There is a method that can be used to ensure ordering in the Linux kernel. Please describe it.
Definition

barrier operations: rmb(), wmb(), and mb()

no loads from before the call will be performed after it. 

Term
How do you decide which of spin locks, semaphores, and Mutexes to use?
Definition

Use spin locks for very short term. Spinning is costly.

Use semaphore if you need to cross the kernel / user space boundary.

Otherwise use a Mutex. 

 

 

1st, determine if the lock will be held for a long time. If yes, use spin lock. If not, determine if code can sleep. If not, use spin lock. If you need to synchronize between user and kernel space, use semaphore. Otherwise, use mutex.

Term
For the kernel, what is the tick rate, and what is it used for?
Definition

Tick rate is the frequency of the system timer.

An timer interrupt happens on an exact tick.  Used for...  Uptime.  Time of day.  Runqueue balancing. etc

 

Used for Wall time and System Uptime.

 

Term
Describe the concept of a tickless operating system, and what advantages it would have.
Definition

Timer interrupts are dynamically scheduled to whenever the next timer is set to go off.

 Advanages: reduced overhead and power consumption. 

Term
Where is the total ticks since system boot stored?
Definition
the global variable, jiffies
Term
How does the system deal with the above variable (the one that holds total ticks since system boot) wrapping around?
Definition
Linker overlays 32-bit jiffies on lower bits of jiffies_64.
Term
Describe the difference between absolute and relative time.
Definition
Relative time is the distance from a certain point in time, such as right now.  Absolute time elapses independently.
Term
What are BogoMIPS, and what are they used for?
Definition
Bogus Million Instructions Per Second.  Measures how fast a processor can do nothing.
Term
The VFS is very important to everyday operation. What does it do for us?
Definition

It allows us to use the same few functions and system calls on block devices that store their ones and zeros in ways completely unlike one another.

 

manages our filesystems and gives user-space apps a single unified interface to work with.

Term
Draw the path of the flow of data from user space to physical media.
Definition
user space -> VFS -> filesystem -> physical media
Term
There are 4 object types associated with VFS. What are they?
Definition

file

inode

dentry

superblock 

Term
Describe each of the 4 object types associated with the VFS.
Definition

superblock: a specific mounted filesystem.
inode: a specific file.

dentry: a single component of a path.
file: an open file as associated with a process. 

Term
There are 3 main data structures associated with a process at the VFS layer. These are the files struct, the fs struct, and the mnt namespace. Describe the purpose of each and how they relate to one another.
Definition

files_struct: per-process info about open files/descriptors

fs_struct: per-process filesystem info

namespace: uncommonly, a process will have a unique version of the file hierarchy as described by this struct.

(how do they relate?) 

 

they related to each other by a single process

Term
What is caching, and why is it important?
Definition
Holding data from disk in memory, in hopes that we will want to access the same data again in the near future. Important because it replaces disk access with memory access, which is leagues faster.
Term
Please describe the two different types of locality, and how they can be used to inform caching decisions.
Definition

Temporal locality is close in time. If a file was recently accessed it may be accessed again.

 

Spatial locality is close together in the directory structure.  If /a/b/c has been accessed, /a/b/* might all be worth caching. 

Term
Reads and writes are cached in different ways, with multiple possible strategies. For both, describe how data ends up in the cache, and the strategies that could be used to keep it in
sync with the canonical copy.
Definition

Reading is simple. When we want to read something, we check to see if it is cached first.

 Writing has multiple strategies. We could not cache writing at all, or we could write to both the cache and the backing store at once, or we could write to the cache first and maintain a dirty list.

Term
What strategy does Linux use for cache eviction? Please be very specific.
Definition
Linux replaces the clean pages with something else. It selects these pages by the two-list strategy. If there are not enough clean pages, it writes back some dirty pages first.
Term
The Linux page cache uses a specific object to index entries in the cache, which is distinctly misnamed. Please name and describe its usage.
Definition

address_space

It maps stuff in cache to its real location.

Term
Describe laptop mode, as it relates to the page cache.
Definition
Tries to wait until the disk is spinning before flushing dirty buffers to disk.  And, if the disk is already spinning, all dirty buffers are flushed at once.  This saves battery life because spinning the disk is an intensive and highly physical process.
Term
Draw a process tree.  This tree consists of 6 processes, named A - F.Process A is the grandparent of process C. Process C is the child of process B, and the parent of process F. Process C can send information via pipes to both process D and process E.
Definition

A -> B -> C -> D,E,F

(D, E, and F are children of C) 

Term
There are 2 ways of viewing an operating system, as discussed in class. What are they? Explain one of them.
Definition

1. extended (virtual) machine: the OS is easier to program than the underlying hardware.  The operating system provides a variety of services that programs can obtain using system calls.

2. resource manager

Term
There are multiple methods of IPC. Name 3 of them.
Definition

Pipes.

Shared memory.

Named pipes.

Ordinary files.

Term
What is multiplexing, and what is one way in which an operating system provides it?
Definition
Multiplexing = switching between processes, to give the appearance of parallelism.  Done with a process scheduler.
Term
What is a core image?
Definition

entire memory space of a process

 

(I don't think it always has to be the entire memory space)

Term
How does one create a child process identical to the parent? And how does the child differentiate itself?
Definition

Created with fork(). Differentiated by its return value.

child sees it return 0

parent sees it return child's process id (if successful)

 

 

In Linux, created with clone() and the PID is different for the child

Term
What impact does adding more threads to a CPU bound process have? Is there a limit? Why?
Definition

Initially adding more threads will lighten the load on the CPU. 

 The limit is called the "core limit", which can be set with setrlimit. 

 The effect of too many competing threads will be thrashing. 

Term
What 2 commands are required in every MPI program?
Definition

MPI_Init()

MPI_Finalize() 

Term
What system calls does linux implement pthread_create()?
Definition

clone

 

and

 

fork? 

Term
State at least one reason for developing and testing kernel code in a virtual machine.
Definition
If you ruin it, starting over is quite simple on a VM.
Term
Why are version control systems, such as git and svn, helpful in working in a team environment?
Definition

You can label what a commit did exactly.

You can revert commits.

You can pull only the commits you want. 

 

You can have multiple developers working on code - merge will bring forth any conflicts to be resolved

Term
What is processor affinity, and in what way does Linux provide it?
Definition

A preference for which processor to run your code on. In linux you can set it with taskset.

 

(this question was to remain blank on midterm #1) 

Term
Draw and describe the flow chart for process states in the Linux kernel.
Definition
(leave blank)
Term

Define:

turnaround time

response time

CPU utilization

throughput

waiting time 

Definition

Turnaround time: from submission of a process to its completion.
Response time: from when a request was submitted until the first response is produced.

CPU utilizationpercentage of time the CPU spends working (instead of being idle)

throughput: number of processes that complete their execution per time unit 

waiting time:  time spent in the ready queue

 

 

Term

Should each of the following be minimized or maximized, pertaining to performance of a scheduler:

turnaround time

response time

CPU utilization

throughput

waiting time 

 

Definition

minimize: all the ones that say "time"

 maximize: CPU utilization, throughput 

Term
Describe the mechanism that protects the operating system from unauthorized access by userspace processes.
Definition

separation of kernel and userspace modes(?)

 

yes. Userspace applications cannot directly execute kernel code

Term
Go back and make sure that you leave #3 in this section blank. Not scratched out. Blank.
Definition
(does that)
Term
When building the kernel, one file determines which features are included. What is it? How should it be created for the purposes of this class?
Definition

.config 

For this class, it was in the git repo to be cloned.  Actually it was called config, and needed to be moved down a directory and renamed .config 

Term

What does it mean for a process to be CPU bound?

I/O bound? 

Definition

CPU bound spends most of its time in the CPU.

I/O bound spends most of its time waiting for input from the user. 

Term
What was wrong with the scheduler originally used in Linux?
Definition
sucky / did not scale
Term
Describe, in broad terms, the operation of the Completely Fair Scheduler.
Definition

Gives its N processes each 1/N potential share. Each quantum it reevaluates whether each needs this full share and most times is redistributing most of this to CPU bound processes.

 

whatever has run for the least amount of time gets scheduled next.

Term
What is context switching, and what function in the kernel implements it?
Definition

context switching: booting one process off the CPU (steel-toed boot) and putting on the next.

 

context_switch() 

Term
What type of data structure holds the collection of runnable processes for CFS?
Definition
red-black tree
Term
What is the username and password to get into your virtual machine?
Definition

bob

bob123bob 

Supporting users have an ad free experience!