Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

P4 (PSS)Principper for styresystemer og parallelitet > Eksamen > Flashcards

Eksamen Flashcards

1
Q

Hvad er en proces?

A

Et program med alt dens tilhørende data.

Local data:
address space, heap, open files, process-ID, parent, ownership, CPU reg. (copy)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Hvad er et program?

A

Et sæt instruktioner i maskinkode.

  • Instruktionssekvens (objektkode).
  • Oftest en fil.
  • Statisk.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Hvad er en tråd?

A

Den mindste eksekverbare del af en proces.

Local data:
thread-ID, priority, stack.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What’s the order of the memory hierarchy?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What are the basic elements in a computer system

A
  • Processor
  • Main Memory
  • I/O Modules
  • System Bus
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What components can be found in a processor/CPU

A

PC - Program counter

IR - Instruction register

MAR - Memory address register

MBR - Memory buffer register

I/O AR - input/output address register

I/O BR - input/output buffer register

Execution Unit

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is an Execution Unit?

A

The part of a CPU that:

  • Does some arithmetic operation.
  • Sets flags according to a comparison.
  • Moves a value from one register to another.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What does a processor do?

A

It controls the operation of the computer and performs its data processing functions.

*When there is only one processor, it is often called a Central Processing Unit(CPU)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What does Main Memory do?

A

It stores data and programs.

This memory is typically volatile (when the computer shuts down the content of the memory is lost).

Main memory is also called primary memory or RAM.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What does I/O Modules do?

A
  • They move data between the computer and its external environtment.
  • They contain internal buffers for temporarily holding data until it can be sent on.

The external environtment consists of a variety of devices, including secondary memory devices (e.g., disks), communications equipment, and terminals.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What does the System Bus do?

A

It provides for communication among processors, main memory, and I/O modules.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What does a processor use to exchange data with main memory?

A

It uses two internal registers:

MAR (memory adress register)

MBR (memory buffer register)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What does the MAR (memory adress register) contain?

A

The adress in memory for the next read or write instruction.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What does MBR (memory buffer register) contain?

A

The data to be written into or which receives the data from from memory.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What does an I/OAR do?

A

It specifies a particular I/O device.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What does an I/OBR (input output buffer register) do?

A

It is used for the exchang of data between an I/O module and the processor.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What does DSP stand for?

And what does it do?

A

Digital Signal Processor

Deals with streaming signals - such as audio & video.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is an instruction cycle?

A

The processing required for a single instruction. Fetching and then executing.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Which steps does a instruction cycle consist of?

A
  1. Instruction fetch
  2. Instruction execution
  3. Check for interrupts
  4. HALT (error stage)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What is a program execution?

A

A repetition of instruction execution.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

A fetched instruction is loaded into what register?

A

IR (Instruction register)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Which four distinct actions can a machine instruction specify?

A
  1. Processor-memory action.
  2. Processor-I/O action.
  3. Data Processing action.
  4. Control action.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What is a processor-memory action?

A

Data is transferred from processor to memory or vice versa.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is an Processor-I/O action?

A

Data is transferred to or from a peripheral device by transferring between the processor and an I/O module.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What is a Data processing action?

A

The processor performs some arithmetric or logical operation on data.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What is a Control action?

A

An instruction may specify that the sequence of execution be altered.

For example: The processor may fetch an instruction from location 149, which specifies that the next instruction will be from location 182. The processor sets the program counter to 182. Thus, on the next fetch stage, the instruction will be fetched from location 182 rather than 150.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What is an interrupt?

A

A message which interrupts the current program to do something else, after which it will return to where it was interrupted.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

How are multipe interrupts dealt with?

A

There are two ways to deal with it:

  1. Sequential interrupt processing (also called a disabled interrupt)
    • Ignores all interrupts until this one is done.
  2. Nested interrupt processing.
    • If an interrupt is received while another interrupt is being handled, the newest interrupt will take priority.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

What is Cache memory?

A

It is a device for staging the movement of data between main memory and processor registers to improve performance.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

What is SMP (Symmetric Multiprocessing)?

A

SMP (symmetric multiprocessing) is the processing of programs by multiple processors that share a common operating system and memory.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

What is a core?

A

When there are multiple processors inside the same chip.

(They each have their individual cache storages, but also share at least one cache that is accessible by all of them.)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

What is the difference between a multiprocessor and a multicore?

A

Multiprocessors doesn’t share a cache and are not in the same chip but multicores do.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

What is spatial locality?

A

If a particular memory location is referenced at a particular time, then it is likely that nearby memory locations will be referenced in the near future.

In this case it is common to attempt to guess the size and shape of the area around the current reference for which it is worthwhile to prepare faster access.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

What is temporal locality?

A

If memory has been accessed recently it is already in cache and is therefore fast to use again.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

What is an instruction trace?

A

A listing of a sequence of instructions.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

What is a Batch Job?

A

A batch job is a computer program or set of programs processed in batch mode. This means that a sequence of commands to be executed by the operating system is listed in a file (often called a batch file, command file, orshell script) and submitted for execution as a single unit.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

What is interactive log-on?

A

A user at a terminal logs on to the system.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

What are the five states in the five state process model?

A
  1. New.
  2. Ready.
  3. Running.
  4. Blocked/Waiting.
  5. Exit.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

What does the blocked/waiting state mean in the five state process model?

A

A process that cannot execute until some event occours, like the completion of I/O operation.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

What does the new state mean?

A

A process that has just been created, but has not yet been admitted to the pool of executable processes by the OS.

Typically, a new process has not yet been loaded into the main memory, although its process control block has been created.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

What does the Exit state mean?

A

A process is in the Exit State when it has been released from the pool of executeable processes by the OS.

Either because it halted or because it aborted for some reason.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
Q

What is preemption?

A

Preemption is defined to be the claiming of a ressource from another process that is using it.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
43
Q

What is swapping and what is its purpose?

A

When none of the processes in main memory is in the Ready state, the OS swaps one of the blocked processes from the disk into a suspend queue.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
44
Q

What is concurrency?

A

Concurrency is when two tasks can start, run, and complete in overlapping time periods. It doesn’t necessarily mean they’ll ever both be running at the same instant. Eg. multitasking on a single-core machine.

Can be implemented using software such as an OS or Virtualization software

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
45
Q

What is paralellism?

A

Parallelism is when tasks literally run at the same time, eg. on a multicore processor.

To implement parallelism hardware such as a multicore processor is needed.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
46
Q

What is an atomic operation?

A

A function or action implemented as a sequence of one or more instructions that appears to be indivisible.

The sequence of instructions is guaranteed to execute as a group.

Atomicity guarantees isolation from concurrent processes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
47
Q

What is a Critical Region/Section?

A

Code region that is vulnerable to race conditions by accessing shared resources

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
48
Q

What is deadlock?

A

A collection of threads P are in a deadlock state if every thread in P is waiting for an event that can only be generated by another thread in P.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
49
Q

What is livelock?

A

Deadlock-like state with no progress although with no cyclic wait.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
50
Q

What is mutual exclusion?

A

The requirement that when one process is in a critical region that accesses shared ressources, no other process may be in a critical region that accesses any of those shared ressources.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
51
Q

How can you ensure mutual exclusion?

A

There are three ways:

  1. Disabling interrupts
    1. Pro’s: effective.
    2. Con’s: too effective, potentially very disruptive.
  2. Software locks
    1. Pro’s: portable, less disruptive.
    2. Con’s: inefficient, vulnerable to compiler optimisation.
  3. Hardware locks
    1. Pro’s: (more) efficient
    2. Con’s: less portable… still inefficient(!)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
52
Q

Interrupts: What is a software/hardware lock?

A

In computer science, a lock or mutex (from mutual exclusion) is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. A lock is designed to enforce a mutual exclusion concurrency control policy.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
53
Q

What is a race condition?

A

A situation in which multiple threads or processes read and write a shared data item and the final result depends on the relative timing of their execution.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
54
Q

What is starvation?

A
  • Situation where a thread never acquires a resource because other processes always get it first.
  • Typical problem for systems with priorities.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
55
Q

What are Priorities?

A

Priorities are the measurement of the relative importance of the task.

  • Hard real-time tasks may have an “absolute” priority, with the system failing if a deadline is missed.
  • If the system is to continue to run no matter what, then both hard and soft real-time tasks may be assigned relative priorities as a guide to the scheduler.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
56
Q

What is a semaphore?

A

A semaphore is a variable or abstract data type that is used for controlling access, by multiple processes, to a common resource in a parallel programming or a multi user environment.

A useful way to think of a semaphore is as a record of how many units of a particular resource are available, coupled with operations to safely (i.e., without race conditions) adjust that record

  • Semaphores which allow an arbitrary resource count are called counting semaphores
  • Semaphores which are restricted to the values 0 and 1 (or locked/unlocked, unavailable/available) are called binary semaphores.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
57
Q

What is a mutex?

A

A (very) simple semaphor.

  • Two states (binary): locked and unlocked.
  • lock: locks an unlocked mutex.
  • unlock: unlocks a locked mutex.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
58
Q

What is a condition variable?

A

A data type that is used to block a process or thread until a particular condition is true.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
59
Q

What is a monitor?

A
  • Language construct ensuring mutual exclusion.
  • Encapsulates critical regions.
  • Guaranteed by the compiler.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
60
Q

What is a spinlock?

A

Mutual exclusion mechanism in which a process executes in an loop waiting for the value of a lock variable to indicate availability.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
61
Q

What are event flags?

A

An event flag is a process synchronization primitive.

It has two possible states: “set” or “cleared”.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
62
Q

What requirements is memory management intended to satisfy?

A
  • Relocation
  • Protection
  • Sharing
  • Logical organization
  • Physical organization
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
63
Q

Memory management: What is Relocation?

A

Processes should be able to be relocated everywhere in memory and still work. This raises technical concerns related to adressing

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
64
Q

Memory management: What is protection?

A

A process cannot be allowed to access other processes data.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
65
Q

Memory management: What is Sharing?

A

Despite protection, we can still allow processes to access shared data.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
66
Q

Memory management: What is logical organization?

A

Main memory is organized as a linear or one-dimensional address space that consists of sequence of bytes or words. Secondary memory at its physical level is similarly organized. Most of the programs are organized into modules.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
67
Q

Memory management: What is Physical organization?

A

Computer memory is organized into two levels:

  1. Main memory - Main memory is a volatile memory and it provides fast access at relatively high cost.
  2. Secondary memory - Secondary memory is a non-volatile memory and it is slower and cheaper than main memory.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
68
Q

Why is it impossible to enforce memory protection at compile time?

A

Because it’s impossible to know how many ressources a process needs before runtime.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
69
Q

What are some reasons to allow two or more processes to all have access to a particurlar region of memory?

A

For example if a number of processes are executing the same program it is advantageous to allow each process to access the same copy of the program rather than have its own separate copy.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
70
Q

What are the advantages of using unequal-size partitions in a fixed-partitioning scheme?

A

It creates less internal fragmentation because you get a memory block which fits better to the size you need.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
71
Q

What is the difference between simple paging and virtual memory paging?

A

In simple paging you need all information loaded into main memory to run a process as opposed to virtual memory paging that can run one page at a time.

72
Q

What is thrashing?

A

When the processor spends most of the time handling page faults instead of “real” instructions.

73
Q

Why is locality (both spatial and temporal) important when using virtual memory?

A

Principle of locality er nødvendigt for at gøre det muligt at gætte hvad der skal bruges om lidt hvorved det undgås at smide pages væk der skal bruges snart, og derved undgås thrashing.

74
Q

Which elements are typically found in a page table entry?

A
  • Modified bit
  • Present bit
    • (hvis true, så har den også frame no.)
  • Other control bits
    • for example: bits used in algorithms by the OS.
75
Q

What does TLB stand for?

A

Translation Lookaside Buffer

76
Q

What is the purpose of the TLB?

A

A TLB is an associative cache of page table entries and is used to avoid the necessity of accessing the main memory every time a virtual address is mapped.

It improves virtual address translation speed.

77
Q

What is a policy?

A

An algorithm that is ‘not set in stone’.

78
Q

What are the different Page fetch policies?

A
  1. Demand paging.
  2. Prepaging.
79
Q

What is Demand paging?

A

A page gets loaded into main memory when a process needs it.

80
Q

What is Prepaging?

A

Loads pages into memory before they have to be used.

(It’s not feasible since you rarely knows which pages is needed except at the start of a program)

81
Q

What is Resident set size (RSS)?

A

In computing, resident set size (RSS) is the portion of memory occupied by a process that is held in main memory (RAM).

82
Q

What is a working set?

A

All the pages a process has accessed within a specific time interval.

83
Q

What is a Memory Module?

A

It consists of a set of locations, defined by sequentially numbered addresses.

Each location contains a bit pattern that can be interpreted as either an instruction or data.

84
Q

What is a process control block?

Why is it needed?

A

What is it?
A datastructure that contains sufficient information so that it is possible to interrupt a running process and later resume execution as if the interruption had not occurred.

Why is it needed?
It is the key tool that enables the OS to support multiple processes and to provide for multiprocessing.

85
Q

When are processes created?

A

It happens for three reasons:

  • It is created upon login.
  • It is spawned by an existing process.
  • It is created when a new job is started( by OS, user, …).
86
Q

How does process creation work?

A
  1. Assign a unique process identifier to the new process.
  2. Allocate space for the process.
  3. Initialize the process control block.
  4. Set the appropriate linkages.
    1. For example: If the OS maintains each scheduling queue as a linked list, then the new process must be put in the Ready or Ready/Suspended list.
  5. Create or expand other data structures.
    1. For example: The OS may maintain an accounting file on each process to be used subsequently for billing and/or performance assessment purposes.
87
Q

How does process switching work?

A
  1. Save the relevant data for the current program.
  2. Pick the program with the highest-priority, that is ready to run.
  3. Re-instate the new program’s data.
  4. Execute.
88
Q

When does process termination happen?

A

It happens for four reasons:

  • Program completed.
  • Lack of resources:
    • Time (hard max limit).
    • Memory.
    • …
  • Error condition
    • Invalid instruction.
    • Arithmetic error.
    • …
  • Parent request/parent termination.
89
Q

What is an operating system?

A

An operating system (OS) is software that manages computer hardware and
software resources and provides common services for computer programs.

90
Q

What is a Process Image?

A

It is a collaction of process related data:

  • Process Control Block.
  • Program (code).
  • Stack.
  • Heap (user data).
91
Q

What is a Thread Control block?

A

Thread Control Block (TCB) is a data structure in the operating system kernel which contains thread-specific information needed to manage it. The TCB is “the manifestation of a thread in an operating system”.

An example of information contained within a TCB is:

  • Stack pointer: Points to thread’s stack in the process.
  • Program counter.
  • State of the thread (running, ready, waiting, start, done).
  • Thread’s register values.
  • Pointer to the Process control block (PCB) of the process thread lives on.

The Thread Control Block acts as a library of information about the threads in a system. Specific information is stored in the thread control block highlighting important information about each process.

92
Q

Define Multiprogramming:

A
  • Split of tasks that can be executed concurrently on shared processors.
  • Implemented by rapid switching between tasks.
  • Common in modern OS’s
93
Q

Define Multithreading:

A
  • Split of processes into several threads.
  • Always at least one thread pr. process (even in non-multithreaded systems)
94
Q

Why do we need Threads?

A

Performance

  • Low-cost thread creation, switching, and termination.
  • Efficient inter-thread communication (no need to involve kernel)
  • Can utilise multi-processor/multi-core platforms.

Better architecture/design

  • Easy split into foreground and background work.
  • Asynchronous processing.
  • Modularity.
95
Q

What is Kernel?

A

Controls execution of the processors.

The kernel manages:

  • Thread scheduling.
  • Process switching.
  • Exception and interrupt handling.
  • Mulitprocessor synchronization.

Unlike the rest of the Executive and the user level, the Kernel’s own code does not run in threads.

It contains the most frequently used functions in the OS and, at a given time, other portions of the OS currently in use.

96
Q

Name and describe the three implementation strategies for threads:

A

Implement in kernel-space (aka. obvious choice)

  • Modify/extend kernel to support threads.
  • Pro’s: better handling of blocked threads.

Implement in user-space

  • User-space library for thread creation, switching, termination, …
  • Pro’s: performance (kernel not involved), portable.
  • Con’s: blocked threads.

Implement in both kernel- and user-space (aka. complex choice)

  • Mainly in user-space.
  • Mapping user-space threads to (fewer) kernel-space threads.
  • Pro’s: all of the above.
  • Con’s: complex implementation, complex management.
97
Q

How do you avoid Race Conditions?

A

Make sure that only one thread at a time accesses shared resources

  • Updating a shared resource happens atomically (Event, or sequence of events, that happen(s) uninterruptedly).
  • Critical regions are executed under mutual exclusion.
98
Q

What is Busy Waiting?

A

A “no-op” loop waiting for a condition to be fulfilled: a loop where the executing thread actively waits for access to the critical region.

99
Q

What is a Blocking Action?

A

A better alternative to Busy Wait.

Let another thread work while we wait

  • Block the thread until access to the resource can be achieved.
  • Wake the thread when leaving the critical region.
  • Leave the hard work to the OS.
100
Q

What is a Blocked Thread?

A
  • Thread that does not run until it recieves a signal from another thread.
  • Special state: blocked.
  • Not allocated CPU time.
  • OS keeps account of blocked threads and why they are blocked.
101
Q

What is Coffman’s conditions?

A

If all four of the conditions are met, Deadlock can happen.

  • Mutual Exclusion
    • Resources cannot be shared
  • No preemption
    • Resources cannot be taken away from a thread
  • Hold-and-wait
    • Threads may always try to take more resources
  • Circular Wait
    • There is a circular dependency of resources
102
Q

How do you prevent Deadlock?

A

Break one of Coffman’s conditions:

  • Avoid: Mutual exclusion
    • Make resources shareable.
    • Critical regions are always un-shareable resources.
  • Allow: Preemption
    • Allow pre-emption of resources (forcibly removing resources).
    • Only possible (safe) if state of resources can be re-created.
  • Avoid: Hold-and-wait
    • Require all resources to be allocated at once.
    • Waste of resources.
    • Potentially a long wait.
  • Avoid: Circular wait
    • Resources are allocated in a specific order.
    • All resources must be known beforehand.
103
Q

What is priority inversion?

A
  • When a low-priority thread blocks a high(er)-priority thread.
  • Happens when a higher-priority thread needs a resource held by a lower-priority thread.
104
Q

TODO Explain the Dining Philospohers:

A

Nogle der har en god forklaring, der også kommer ind på de forskellige måder at undgå dead/live-lock?

105
Q

What is a Safe State?

A

A state in which there is at least one allocation sequence that allows all threads to finish without deadlock.

106
Q

TODO Lav kort med der giver basal forståelse af pthreads.

A
107
Q

What is a physical address type?

A

It defines a specific physical memory cell in primary memory.

108
Q

What is a virtual address type?

A

References to memory location independently of physical location.

  • Indirection (“Every software problem can be solved by adding another layer of indirexction” (Steven M. Bellovin)).
  • Virtual addresses are mapped to physical addresses at runtime .
  • Requires hardware support (MMU); often (always) integrated into CPU.
  • Virtual addressing is transparent to the programmer.
109
Q

What is a relative address type?

A

A logical address defined relative to a known base address.

  • Base address is a known physical address.
  • Relative address is the offset to the base address.
  • The physical address is the sum of base address and offset.
110
Q

TODO How do you perform a simple Address Translation from virtual to physical?

Nogen der kan beskrive det?

A
111
Q

What is virtual memory?

A

A storage allocation scheme in which secondary memory can be addressed as though it were part of main memory.

  • The addresses a program may use to reference memory are distinguished from the addresses the memory system uses to identify physical storage sites, and program-generated addresses are translated automatically to the corresponding machine addresses.
  • The size of virtual storage is limited by the addressing scheme of the computer system and by the amount of secondary memory available and not by the actual number of main storage locations.
112
Q

What is paged memory?

A
  • Process memory is split into a number of pages of fixed size.
  • Physical memory is split into a number of pages frames (da: rammer)
    • Pages are placed in page frames.
    • Page frames have same fixed size as pages.
  • OS places pages in frames and maintains information about placement in a page table.
  • OS maintains one page table pr. process.
  • Requires MMU support.
113
Q

How does paged memory support shared memory?

A
  • Memory can be shared by letting different page tables refer to the same frame.
  • Same physical memory in two different address spaces (one per process).
  • Shared frames does not necessarily imply same (local) page numbers.
  • Shared memory useful for:
    • IPC (Inter-process communication).
    • Sharing of program code, libraries (DLL, .so).
114
Q

What is Segmented Memory?

A

Memory is split into segments

  • Separate address space (programmer defined).
  • Defined size, access rights, etc.
  • Defined as start address (base address) and length.
  • Logical address on the form <segment>.</segment>
  • Segment table maps segment number to start address og segment length.
115
Q

The different ways an operating system does memory management:

A

Memory management:

  • Static allocation, uniform/nom-uniform size.
  • Dynamic allocation.
  • Paged and/or segmented memory
116
Q

What is an MMU?

A

A Memory Management Unit, is a computer hardware unit having all memory references passed through itself,

  • Primarily performs the translation of virtual memory addresses to physical addresses.
  • It is usually implemented as part of the central processing unit (CPU).
117
Q

What is static allocation?

A

Allocation in blocks of pre-determined fixed size.

  • Main challenges: block size, process placement.
  • Main advantages: easy to implement, little overhead.
  • Main disadvantages: inflexible, inefficient.
118
Q

Static Allocation: What is uniform, fixed size?

Pros and cons?

A

Every block (partition) has same size.

Pros

  • Easy to implement/manage.
  • Little/no OS overhead.

Cons:

  • Internal fragmentation (a lot).
  • Inflexible (fixed no of proc.).
  • Big programs problematic (overlay).
119
Q

Static Allocation: What is Non-uniform block size?

Pros and cons?

A

Split memory into blocks of different size.

  • Requires strategy for allocation of processes to blocks.
  • Smallest-fit
    • May result in processes waiting for blocks of the “appropriate” size.
  • Smallest-available
    • May result in more internal fragmentation
  • Problem: memory requirement must be known beforehand
120
Q

What is Dynamic allocation?

A
  • Allocation in blocks dynamically sized during load-time.
  • OS allocates appropriate block
    • OS maintains start address and length.
    • Processes must specify memory requirements at start-up.
121
Q

What placement strategies for finding an appropriate block are there for Dynamic allocation?

A
  • Best-fit: find block that is closest in size. (Usually the best strategy)
  • First-fit: find first block big enough.
  • Next-fit: find first block big enough, after last placed block.
122
Q

Pro’s and con’s of Dynamic allocation?

A

Pros

  • No (visible) internal fragmentation.
  • Adapts to current needs (few big or many small processes).

Cons:

  • Memory requirements must be known beforehand.
  • Compaction
    • Relocation of processes to reduce external fragmentation.
    • Similar to de-fragmentation of harddisks.
  • Compaction without virtual memory requires re-writing of addresses in program code and data (pointers).
123
Q

What is the difference between internal and external fragmentation?

A
  • Internal fragmentation is the wasted space within each allocated block because of rounding up from the actual requested allocation to the allocation granularity.
  • External fragmentation is the various free spaced holes that are generated in either your memory or disk space. External fragmented blocks are available for allocation, but may be too small to be of any use.
124
Q

TODO How do you implement virtual memory using paging?

A
125
Q

What is logical addresses?

A

In computing, a logical address is the address at which an item (memory cell, storage element, network host) appears to reside from the perspective of an executing application program.

A logical address may be different from the physical address due to the operation of an address translator or mapping function. Such mapping functions may be, in the case of a computer memory architecture, a memory management unit (MMU) between the CPU and the memory bus

126
Q

Virtual memory: What is a Fetch Policy?

A

The Fetch Policy determines when a page should be brought into main memory.

The two most common alternatives are demand paging and prepaging.

Deman paging:

  • A page is brought into main memory only when a reference is made to a location on that page. (The page is brought in as it is used)

Prepaging:

  • Pages other than the one demanded by a page fault are brought into main memory. (All the pages are brought in before they are used).
127
Q

Virtual memory: What is a Placement Policy?

A

The placement policy determines where in main memory a process piece is to reside.

128
Q

Virtual memory: What is a Page Replacement Policy?

A

When all of the frames in main memory are occupide and it is necessary to bring in a new page to satisfy a page fault, the replacement policy determines which page currently in memory is to be replaced.

129
Q

What kind of strategies exist for Frame Allocation:

A

When you have to allocate frames to processes there are four different ways to do so:

  1. Equal allocation.
  2. Proportional allocation.
  3. The “Working set” model.
  4. Page fault frequency.
130
Q

Frame Allocation: What is “The working set” model?”

A

The OS looks at the working set of each process and allocates appropriately.

131
Q

What is a Filesystem?

What does it do?

A
  • The primary(?) “interface” to the OS (for users).
  • Main purpose: organising data (in files, directories, …).
  • Filesystem maintains list of filenames and corresponding block numbers.
  • Defines operations that can be done on files and volumes (renaming, creation, deletion, …).
  • Solves administrative tasks:
    • Sharing and protection.
    • Reliability and fault tolerance.
    • Efficiency.
    • Space usage.
132
Q

How can files be organised in a file system?

A

There are ways to organise a file system:

  1. Flat filesystems.
  2. Two-level file systems.
  3. Hierarchical file systems.
  4. Paths.
133
Q

What is a Flat file system?

A

A Flat file system has no subdirectories.

134
Q

What is a two-level file system?

A

A Two-level file system has one directory for each user, but no subdirectories.

135
Q

What is a hierachical file system?

A

A hierarchical file system uses a hierachical organisation of folders.

Directories are organised as trees.

136
Q

What is a Path file system?

A
137
Q

What are Hard Links?

A
  • Two directory entries for same file content.
  • Difficult to realise if meta-data is stored in directory.
  • Does not work across volumes.
  • A file is deleted (or unlinked) when there are no more hard links to it.
  • Hard links can be used to avoid unnecessary replication of files
    • Guarantees consistent file content.
    • Reduces space usage.
  • Hard links allow flexible name space organisation (across directory structure).
138
Q

What are Symbolic Links?

A
  • Deleting the file pointed to by a symbolic link results in a dead symbolic link.
  • For flexible than hardlinks
    • Can link across volumes.
    • Can link to a directory.
  • Special attribute marks the file as a symbolic link.
  • Windows’ shortcuts: a kind of symbolic link.
139
Q

How are Disk Blocks allocated in a filesystem?

A

There are four ways to allocate disk blocks in a filesystem:

  1. Contiguous allocation.
  2. Chained/linked allocation.
  3. Mapped allocation.
  4. Indexed allocation.
140
Q

What is Contiguous allocation?

Pros’ and con’s?

A

Contiguous memory allocation is a classical memory allocation model that assigns a process consecutive memory blocks (that is, memory blocks having consecutive addresses).

  • Pros:
    • Easy to implement/administrate.
  • Cons:
    • Often results in fragmentation.
141
Q

What is Chained/linked allocation?

Pros’ and con’s?

A

Each file is stored as a linked list of disk blocks. (The blocks may be spread out on any addresses on the disk)

  • Cons:
    • Can take relatively longer time to read the entire file (compared to continuous allocation).
142
Q

What is Mapped allocation?

A

In computer file systems, a block allocation map is a data structure used to track disk blocks that are considered “in use”. Blocks may also be referred to as allocation units or clusters.

143
Q

What is Indexed allocation?

A

Linked allocation does not support random access of files, since each block can only be found from the previous. Indexed allocation solves this problem by bringing all the pointers together into an index block.

This type of allocation will have a pointer which has the address of all the blocks of a file. This method solves the problem of fragmentation as the blocks can be stored in any location.

144
Q

What are processor registers?

A

A processor register is a small amount of storage available as part of a digital processor, such as a central processing unit (CPU). Such registers are typically addressed by mechanisms other than main memory and can be accessed faster.

145
Q

How does a System Call work?

A

In computing, a system call is how a program requests a service from an operating system’s kernel.

This may include hardware-related services (for example, accessing a hard disk drive), creation and execution of new processes, and communication with integral kernel services such as process scheduling.

System calls provide an essential interface between a process and the operating system.

Implementation:

A typical way to implement this is to use a software interrupt or trap. Interrupts transfer control to the operating system kernel so software simply needs to set up some register with the system call number needed, and execute the software interrupt.

146
Q

What is a device driver?

A
  • A module for the OS
  • The OS’ interface to hardware
    • Disks (floppy, optical, …)
    • Keyboards, mouse, …
    • USB, FireWire, serial ports, printers, bluetooth, …
  • Virtual devices
    • VPN
  • Plugins
    • File systems
    • Scheduling (policy)
    • Filtering (firewall)
  • A protocol
  • A program
147
Q

What are the different types of I/O?

A

There are three types of I/O:

  • Programmed I/O
  • Interrupt-driven I/O
  • Direct Memory Access (DMA)
148
Q

What is Programmed I/O?

A

The CPU issues a command then waits for I/O operations to be complete.

As the CPU is faster than the I/O module, the problem with programmed I/O is that the CPU has to wait a long time for the I/O module of concern to be ready for either reception or transmission of data.

The CPU, while waiting, must repeatedly check the status of the I/O module, and this process is known as Polling.

As a result, the level of the performance of the entire system is severely degraded.

  • CPU requests I/O operation
  • I/O module performs operation
  • I/O module sets status bits
  • CPU checks status bits periodically
  • I/O module does not inform CPU directly
  • I/O module does not interrupt CPU
  • CPU may wait or come back later
149
Q

What is Interrupt-driven I/O?

A

Interrupt-driven I/O:

  • Unit generates interrupt when data is ready.
  • ISR responsible for moving data in or out of data-register.
  • Polling can be avoided.
  • CPU responsible for copying data.
150
Q

What is Direct Memory Access (DMA)?

A

Direct Memory Access (DMA) means CPU grants I/O module authority to read from or write to memory without involvement.

DMA module controls exchange of data between main memory and the I/O device.

Because of DMA device can transfer data directly to and from memory, rather than using the CPU as an intermediary, and can thus relieve congestion on the bus.

CPU is only involved at the beginning and end of the transfer and interrupted only after entire block has been transferred.

151
Q

What is Polling?

A

Polling is the continuous checking of other programs or devices by one progam or device to see what state they are in, usually to see whether they are still connected or want to communicate.

Specifically, in multipoint or multidrop communication (a controlling device with multiple devices attached that share the same line), the controlling device sends a message to each device, one at a time, asking each whether it has anything to communicate (in other words, whether it wants to use the line).

152
Q

Explain the different kinds of I/O Scheduling:

A

FIFO

  • First come first served.
  • Fair but poor performance.

Closest block first

  • Good performance, but not fair.

SCAN

  • The “elevator algorithm”.
  • Maintains direction for read head.
  • Changes direction at inner-/outer-most cylinder.
  • Reasonably fair, reasonable performance.

C-SCAN (cyclic scan)

  • Like SCAN, but does not chage direction (wraps around).
  • Lower latency than SCAN.
153
Q

What is an Exception?

A

An (unpredictable) interruption of a thread-execution caused by an event in- or out-side the CPU.

  • Exceptions generated by the CPU itself.
  • Three categories of exceptions
    • Faults.
    • Traps.
    • Interrupts.
  • Often: no clear difference between exceptions, interrupts, and faults.
  • Exceptions allow user-mode to communicate with kernel-mode
    • Primarily control communication.
    • Data exchanged via shared memory.
  • Usually: a small number of different exceptions in kernel (known beforehand).
154
Q

Exceptions: What is Faults?

A

Generated by suddenly occurring errors:

  • Division by zero.
  • Use of illagal instructions.
  • Insufficient permissions.
155
Q

Exceptions: What are Traps?

A
  • Software interrupts/trap instructions, e.g. INT.
  • Used for implementing system-calls.
156
Q

What is Scheduling?

A

In computing, scheduling is the method by which work specified by some means is assigned to resources that complete the work.

All scheduling systems have these three common goals outside of their individual goals:

  1. Fairness: fair share of CPU time to every process.
  2. Policy enforcement: compliance with policy.
  3. Balance: keep all sub-systems busy.
157
Q

Scheduling: What are the goals for Batch Systems?

A

In addition to the three common goals Batch systems are concerned with:

  • Throughput: maximise jobs pr hour.
  • Turnaround time: minimise time spent on a task.
  • CPU utilisation: keep the CPU buys.
158
Q

Scheduling: What are the goals for Interactive Systems?

A

In addition to the three common goals Interactive systems are concerned with:

  • Response time: respond to user requests quickly.
  • Proportionality: predictability from user prespective.
159
Q

Scheduling: What are the goals for Real-time Systems?

A

In addition to the three common goals Real-Time systems are concerned with:

  • Meeting deadlines: critical for hard real-time.
  • Predicatbility: cirtical for hard real-time.
160
Q

Scheduling: What are the policies for Batch Systems?

A

First-Come First-Served (FIFO)

  • Easy to understand.
  • Easy to implement.
  • Can result in (very) low CPU-utilisation.

Shortest Job First

  • Optimal when all jobs are known and available at the same time.
  • Must be able to determine running time beforehand.

Shortest Remaining Time Next

  • Preemptive version of Shortest Job First.
  • Must be able to determine running time beforehand.
161
Q

Scheduling: What are the policies for Interactive Systems?

A

Round-robin

  • Single queue of threads (run queue).
  • Active thread runs for a quantum; moved to the back of the queue when finished.
  • Length of quantum important for performance.
  • Can be expanded to multiple run queues for priorities.
  • Dynamic prioritisation possible by moving threads between run queues.

Priority Scheduling

  • Like round-robin, but using a priority queue.
  • Runnable thread with highest priority is allowed to run.
  • May require dynamic (re-)prioritisation to ensure fairness.

Shortest Process Next

  • Like Shortest Job Scheduling.
  • Estimate residual running time based on history.

Guaranteed Scheduling

  • Fixed, dynamic amount of CPU time.
  • Track spent CPU-time.
  • Variation: thread with most unspent quantum chosen.

Lottery-scheduling

  • Scheduler draws a lot (randomly).
  • Prioritisation by handing out different number of lottery tickets to different threads.
  • Threads can trade lottery tickets.
  • Fair sharing of resources between users.

Fair-Share Scheduling

  • Take thread/process ownership into account.
162
Q

Scheduling: What are the policies for Real-Time Systems?

A

Cyclic Executive

  • Static “scheduler”, deterministic.

Fixed-Priority

  • Highest-priority thread/task is scheduled.
  • Predictable (statically).

Earliest Deadline First

  • Optimal.
  • Less predictable.
  • Failures may lead to domino effect.

Value-Based

  • Flexible, genereic.
  • Hard to reason about.
163
Q

What is a Shell?

A

In computing, a shell is a user interface for access to an operating system’s services. In general, operating system shells use either a command-line interface (CLI) or graphical user interface (GUI), depending on a computer’s role and particular operation.

164
Q

From where can an interrupt be sent from?

A

An Interrupt can be sent from one of the following:

  • I/O module.
  • Program.
  • Timer.
  • Hardware failure.
165
Q

What is synchronization?

A

Thread synchronization is defined as a mechanism which ensures that two or more concurrent processes or threads do not simultaneously execute some particular program segment known as mutual exclusion.

When one thread starts executing the critical section (serialized segment of the program) the other thread should wait until the first thread finishes.

166
Q

How large is a page?

A

4kb

167
Q

Explain the seven state process model:

A

The seven state process model contains seven states for execution of processes:

  1. New: processes which are newly coming for execution.
  2. Ready: processes which are in main memory and available for execution.
  3. Running: processes which are running or executing.
  4. Exit: processes which are completely executed.
  5. Blocked: processes which are in main memory and awaiting an event.
  6. Blocked suspended: processes which are in secondary memory and awaiting an event.
  7. Ready suspended: processes which are in secondary memory but is available for execution as soon as it is loaded into main memory.
168
Q

Explain inter-process communication (ICP):

A

Interprocess communication (IPC) is a set of programming interfaces that allow a programmer to coordinate activities among different program processes that can run concurrently in an operating system. This allows a program to handle many user requests at the same time. Since even a single user request may result in multiple processes running in the operating system on the user’s behalf, the processes need to communicate with each other. The IPC interfaces make this possible.

169
Q

What is a Resource allocation graph?

A
170
Q

Deadlock solution strategy: What is avoidance?

A

Deadlock can be avoided if certain information about processes are available to the operating system before allocation of resources.

For every resource request, the system sees whether granting the request will mean that the system will enter an unsafe state. The system only grants requests that will lead to safe states.

In order for the system to be able to determine whether the next state will be safe or unsafe, it must know in advance at any time:

  1. resources currently available.
  2. resources currently allocated to each process.
  3. resources that will be required and released by these processes in the future.
171
Q

Deadlock solution strategy: What is detection?

A

Detection:

Under deadlock detection, deadlocks are allowed to occur. Then the state of the system is examined to detect that a deadlock has occurred and subsequently it is corrected.

An algorithm is employed that tracks resource allocation and process states, it rolls back and restarts one or more of the processes in order to remove the detected deadlock.

Detecting a deadlock that has already occurred is easily possible since the resources that each process has locked and/or currently requested are known to the resource scheduler of the operating system.

It then performs the recovery strategy.

172
Q

Deadlock solution strategy: What is recovery?

A

Recovery:

After a deadlock is detected, it can be corrected by using one of the following methods:

  • Process Termination:
    • We can choose to abort all processes involved in the deadlock. This ensures that deadlock is resolved with certainty and speed. But the expense is high as partial computations will be lost.
    • We can choose to abort one process at a time until the deadlock is resolved. This approach has high overheads because after each abort an algorithm must determine whether the system is still in deadlock.
    • Several factors must be considered while choosing a candidate for termination, such as priority and age of the process.
  • Resource Preemption:
    • Resources allocated to various processes may be successively preempted and allocated to other processes until the deadlock is broken.
173
Q

What is an inode?

A

An index node is a data structure used to represent a filesystem object, which can be one of various things including a file or a directory. Each inode stores the attributes and disk block location(s) of the filesystem object’s data.

174
Q

Device driver: What are character devices?

A

Character special files or character devices provide unbuffered, direct access to the hardware device. They do not necessarily allow you to read or write single characters at a time; that is up to the device in question. The character device for a hard disk, for example, will normally require that all reads and writes are aligned to block boundaries and most certainly will not let you read a single byte.

  • A stream of characters
    • Keyboard, mouse, console, serial ports
    • /dev/null, /dev/zero, /dev/random
  • Interface
    • File-operations
      • seek, read, write, readdir, select, ioctl, mmap, open, flush, close, …
    • Registered by the module
      • module register chrdev
      • module unregister chrdev
  • Example: /dev/zero
    • Delivers stream of 0’s
    • dd if=/dev/zero of=/home/foo/overwrite.me count=512
175
Q

Device driver: What are block devices?

A

Block special files or block devices provide buffered access to the hardware, such that “the hardware characteristics of the device are not visible.” Unlike character devices, block devices will always allow you to read or write any sized block (including single characters/bytes) and are not subject to alignment restrictions. The downside is that because block devices are buffered, you do not know how long it will take before a write is pushed to the actual device itself; additionally, if the same hardware exposes both character and block devices, there is a risk of data corruption due to the clients using the character device being unaware of changes made in the buffers of the block device.

  • Data transferred in a number of blocks of fixed size
    • Disks: hard, floppy, optical, …
  • Includes buffering: no ordering necessary (random access, I/O scheduling)
  • Interface
    • Often formatted with a file system
    • Also le-operations(!)
      • seek, read, write, readdir, select, ioctl, mmap, open, flush, close, …
    • Registered by the module
      • register blkdev
      • unregister blkdev
  • Example: RAM disk /dev/ram0

P4 (PSS)Principper for styresystemer og parallelitet (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions