1.
Describe the two general roles of an operating system, and elaborate why these
roles are important.
Operating systems provide:
- a fairly standardised abstraction between hardware and userspace software, that allows userspace software to be written with little concern for the hardware it is running on, and having access to a bunch of useful things like memory, files, screens, i/o etc.
- resource management and allocation to processes & threads. resources include files, memory, cpu runtime, etc.
- a fairly standardised abstraction between hardware and userspace software, that allows userspace software to be written with little concern for the hardware it is running on, and having access to a bunch of useful things like memory, files, screens, i/o etc.
- resource management and allocation to processes & threads. resources include files, memory, cpu runtime, etc.
i) high-level abstractions
why?
- more friendly to programmers
- provides common core for all applications
- hides details of hardware to make application code portable
ii) resource manager
why?
- divides resources amongst competing programs or users according to some system policy to ensure fairness and no starvation where possible.
2.
Using a simple system call as an example (e.g. getpid, or uptime), describe
what is generally involved in providing the result, from the point of calling
the function in the C library to the point where that function returns.
The userspace program makes a function call to the C library, e.g. 'uptime', which sets up a system call in the appropriate manner for the hardware. The userspace program must set up parameters appropriately then trap, such that the kernel takes control and processes the request in userspace. In MIPS, this is achieved through the syscall instruction.
Once the kernel has control, the user state is saved. The kernel performs necessary security & sanity checks, then attempts to fulfill the request. In the case of 'uptime', it would copy the value of a counter, which (presumably) has been counting seconds since powerup. The user state is restored, the counter is placed this in the stack or a register and warps back to userspace. The C library routine reads the stack / register that the kernel just wrote, and returns it to the userspace program.
The steps may be:
- Set up the required syscall arguments
- Call syscall execption
– Change to kernel stack
– Preserve registers by saving to memory (the stack)
– Leave saved registers somewhere accessible to
• Read arguments
• Store return values
– Do the “read()”
– Restore registers
– Switch back to user stack
– Return to application
- Set up the required syscall arguments
- Call syscall execption
– Change to kernel stack
– Preserve registers by saving to memory (the stack)
– Leave saved registers somewhere accessible to
• Read arguments
• Store return values
– Do the “read()”
– Restore registers
– Switch back to user stack
– Return to application
3.
Why must the operating system be more careful when accessing input to a system
call (or producing the result) when the data is in memory instead of registers?
The operating system needs to verify that the memory being written to / read from is a valid address, owned by the process making the request. It must prevent processes from corrupting other processes, or reading memory owned by other processes.
The operating system much take care with inputs from memory
as:
a) The address given by the application as the address of the input or output could be
- an address of an illegal area of memory
- an address of a legal area that is paged to disk
b) or, could change if the application is multithreaded.
Basically, the operating system must ensure that it cannot be corrupted, crashed, or bypassed as a result of accessing memory as directed by the application.
a) The address given by the application as the address of the input or output could be
- an address of an illegal area of memory
- an address of a legal area that is paged to disk
b) or, could change if the application is multithreaded.
Basically, the operating system must ensure that it cannot be corrupted, crashed, or bypassed as a result of accessing memory as directed by the application.
4.
Is putting security checks in the C library a good or a bad idea? Why?
Putting security checks in the C library is no guarantee of security, because it is the choice/convenience of the userspace program to use the C library. There is nothing to stop a userspace program making a system call directly, with whatever paraemters it pleases, which are potentially malicious.
Security checks should be performed in kernel space, where the userspace program has no influence, and cannot circumvent security checks.
5.
Describe the three state process model, describe what transitions are valid
between the three states, and describe an event that might cause such a
transition.
Processes can be Running, Ready, or Blocked. A running process may block on an IO request. A running process may also be placed in a ready queue if it cooperatively or preemtively gets context switched, to allow another program to run. Blocked processes can be moved to a ready queue when the thing it was blocking on becomes available. Ready processes can start running in a context switch.
6.
Multi-programming (or multi-tasking) enables more than a single process to
apparently execute simultaneously. How is this achieved on a uniprocoessor?
Preemptive multitasking is achieved
by rapidly context switching between processes. Each process is given a window
of time to execute, called a 'timeslice'. The processor then gets interrupted
by a timer, which causes it to context switch to another process, which will
run until it blocks, or until the next tick. By switching rapidly enough, it
creates the illusion that several processes are running simultaneously.
Cooperative multitasking is acheived by having every process yield occasionally, such that other processes can run.
Cooperative multitasking is acheived by having every process yield occasionally, such that other processes can run.
7.
What is a process? What are attributes of a process?
A process is one or more threads of execution that exist in
a single virtual memory space. A process has it's own set of file descriptors,
vm space, timekeeping data, pwd, (maybe some other stuff)
1. a program in execution
2.an instance of running program
3. an owner of the resource allocated to program execution
4. a task or a job
5. emcompass one or more threads
attribute of a process:
Address Space
Open files - (could be argued are part of resources)
Process ID
Process Group
Parent Process
signals
etc.
attributes of threads:
Scheduling Parameters
Registers
Program Counter
Program Status Word
Stack Pointer
Thread state
If the OS does not support multi-threaded applications, then thread attributes become process attributes.
2.an instance of running program
3. an owner of the resource allocated to program execution
4. a task or a job
5. emcompass one or more threads
attribute of a process:
Address Space
Open files - (could be argued are part of resources)
Process ID
Process Group
Parent Process
signals
etc.
attributes of threads:
Scheduling Parameters
Registers
Program Counter
Program Status Word
Stack Pointer
Thread state
If the OS does not support multi-threaded applications, then thread attributes become process attributes.
8.
What is the function of the ready queue?
The ready queue stores threads that
aren't currently running, that are capable of resuming execution. There may be
several ready queues for each priority level, depending on the scheduling
algorithm. The scheduler consults the ready queue to determine which
process/thread to run next. As the name suggests, the ready queue is a queue,
in order to schedule fairly.
9.
What is the relationship between threads and processes?
A processes is a container for
threads, which has it's own memory space. A process may contain one or more
threads, which share that memory space, all of the file descriptors and other
attributes. The threads are the units of execution within the process,
they posess a register set, stack, program counter, and scheduling attributes -
per thread.
10.
Describe how a multi-threaded application can be supported by a user-level
threads package. It may be helpful to consider (and draw) the components of
such a package, and the function they perform.
From the kernel's perpective, each process has its own
address space, file descriptors, etc and one thread of execution. To
support multiple threads at user-level, the process contains code to
create, destroy, schedule and synchronise user-level threads - which can be
thought of as mulitplexing many user-level threads onto the single kernel
thread, all managed within the process. The scheduler can run any
arbitrary scheduling algorithms, and is independent of the kernel's scheduler.
User-level threads can also satisfy a huge number of threads if necessary, as it can take advantage of virtual memory to store user-level thread control blocks and stacks.
These are often cooperative schedulers, as there is usually only rudimentary support (if any) for delivering timer ticks to the user-level scheduler. However the application must be specifically written for cooperative scheduling, containg yields such that other threads have an opportunity to run; a single badly written thread without enough yields can monopolise cpu time. Alternatively, these can also be preemptive multitaskers, where the user level thread package receives regular signals from the operating system, which may initiate the context switch. These have high granularity though and aren't really practical.
Another important consideration is making system calls non blocking, so that the user-level thread scheduler can schedule (overlap) execution of another thread with I/O latency rather than blocking the whole process. This is not alway possible (either because of lack of async I/O system calls), or because events such as page faults (which are always synchronous) will block the process and all the user-level threads in side.
User-level threads can also satisfy a huge number of threads if necessary, as it can take advantage of virtual memory to store user-level thread control blocks and stacks.
These are often cooperative schedulers, as there is usually only rudimentary support (if any) for delivering timer ticks to the user-level scheduler. However the application must be specifically written for cooperative scheduling, containg yields such that other threads have an opportunity to run; a single badly written thread without enough yields can monopolise cpu time. Alternatively, these can also be preemptive multitaskers, where the user level thread package receives regular signals from the operating system, which may initiate the context switch. These have high granularity though and aren't really practical.
Another important consideration is making system calls non blocking, so that the user-level thread scheduler can schedule (overlap) execution of another thread with I/O latency rather than blocking the whole process. This is not alway possible (either because of lack of async I/O system calls), or because events such as page faults (which are always synchronous) will block the process and all the user-level threads in side.
11.
Name some advantages and disadvantages of user-level threads.
Advantages: User level threads are more configurable, as
they may use any scheduling algorithm, and they can also run on any OS (probably
even DOS) since they do not require kernel support for multiple threads. User
level threading is also much faster, as they don't need to trap to kernel space
and back again. (hmmm... prescott?)
Disadvantages: without kernel thread support, the threads must be cooperative. Yields are annoying, and require every thread to be well written, e.g. having enough yields and not monopolising cpu time. The I/O must be non blocking, then require extra checking to deal with cases that would normally block. This is not alway possible (either because of lack of async I/O system calls, or polling system calls), or because events such as page faults (which are always synchronous) will block the process and all the user-level threads in side.. User level threads cannot take advantage of multiple cpus, as the os cannot dispatch threads to different processors, or potentially do true parallelism, because the OS only sees 1 process with 1 thread.
Disadvantages: without kernel thread support, the threads must be cooperative. Yields are annoying, and require every thread to be well written, e.g. having enough yields and not monopolising cpu time. The I/O must be non blocking, then require extra checking to deal with cases that would normally block. This is not alway possible (either because of lack of async I/O system calls, or polling system calls), or because events such as page faults (which are always synchronous) will block the process and all the user-level threads in side.. User level threads cannot take advantage of multiple cpus, as the os cannot dispatch threads to different processors, or potentially do true parallelism, because the OS only sees 1 process with 1 thread.
12.
Why are user-level threads packages generally cooperatively scheduled?
User level threads packages are
generally cooperatively scheduled as is usually only rudimentary support (if
any) for delivering timer ticks to the user-level scheduler. They can be made
preemptively if the operating system regularly signals the process, however
this is high granularity, high enough that it isn't particularly useful, so
cooperative is preferential to give the illusion of parallelism.
13.
Enumerate the advantages and disadvantages of supporting multi-threaded
applications with kernel-level threads.
Enumerate eh?
Advantages
Advantages
- assuming that the user-threads package is cooperative, user programs do not need to be written with yields everywhere
- each thread is guaranteed a fair amount of execution time (as fair as the os is)
- userspace programs do not require extra checking around blocking i/o to avoid it - i.e. other ready threads within the process can be scheduled if the running thread blocks on a system call or page fault.
- low granularity multitasking, gives the illusion of parallelism
- can take advantage of multiprocessors, as the kernel can dispatch threads to other cpus as it sees appropriate
Disadvantages
- the user program must use locks and mutexes appropriately around critical sections, since it cannot control when context switching will occur (...but so what)
- code is less portable since this requires operating system support
- cannot choose the scheduling algorithm
- Thread management (create, delete, ect) is more expensive as it now requires system calls
14.
Describe a sequence the sequence of step that occur when a timer interrupt
occurs that eventually results in a context switch to another application.
- Thread 1 running happily
- Timer tick
- Trap into kernel space
- switch to kernel stack for thread 1
- thread 1 user registers stored
- find next thread to run (named thread 2) from scheduler
- context switch to thread 2 (change to its kernel stack, make its thread control current, flush tlb)
- thread 2 user registers loaded
- warp into thread 2
- thread 2 running
- Timer tick
- Trap into kernel space
- switch to kernel stack for thread 1
- thread 1 user registers stored
- find next thread to run (named thread 2) from scheduler
- context switch to thread 2 (change to its kernel stack, make its thread control current, flush tlb)
- thread 2 user registers loaded
- warp into thread 2
- thread 2 running
15.
Context switching between two threads of execution within the operating system
is usually performed by a small assembly language function. In general terms,
what does this small function do internally?
For a real example of such a function look at the OS/161
mips_switch code
In general, assembly language context swith code does:
In general, assembly language context swith code does:
- Saves enough registers on the stack to eventually return back to the calling C function
- stores the stack pointer in the current thread's control block
- load the stack pointer from the destinations thread's control block
- restores the destination threads registers from its stack
- returns to 'C' in the destination thread.
16.
What is a race condition? Give an example.
A race condition occurs when there
is an uncoordinated concurrent access to shared resources (e.g. memory or
device registers), which leads to incorrect behaviour of the program, deadlocks
or lost work.
An example would be two process updating a counter simultaneously. Say the counter has a value of 1. Process A reads the variable but before updating Process B reads and updates the counter to 2. Process A, having no knowledge of what Process B does, updates the counter to 2. The correct behaviour of the program would have the counter being incremented to 3, not 2.
An example would be two process updating a counter simultaneously. Say the counter has a value of 1. Process A reads the variable but before updating Process B reads and updates the counter to 2. Process A, having no knowledge of what Process B does, updates the counter to 2. The correct behaviour of the program would have the counter being incremented to 3, not 2.
17.
What is a critical region? How do they relate to controlling access to shared
resources?
A critical region is an area of code
where the code expects shared resources not to be changed or viewed by other
threads while executing inside the critical region.
18.
What are three requirements of any solution to the critical sections problem?
Why are the requirements needed?
from lecture notes:
Mutual Exclusion: No two processes simultaneously in critical region
Progress: no process outide of a critical region may cause another process to block
Bounded: No process must wait forever to enter its critical region
Mutual Exclusion: No two processes simultaneously in critical region
Progress: no process outide of a critical region may cause another process to block
Bounded: No process must wait forever to enter its critical region
19.
Why is turn passing a poor solution to the critical sections problem?
need to wait for whatever thread
whose turn it is to actually use that section, which it might not be about to
use. This can cause the thread waiting on the critical section to block
unnecessarily long. if the different threads have different patterns of use of
the critical region, performance is limited by the most infrequent user., i.e.
the system progresses at the rate of the slowest thread.
20.
Interrupt disabling and enabling is a common approach to implementing mutual
exclusion, what are its advantages and disadvantages?
Advantages: It's easy and efficient on a uniprocessor.
Disadvantages: it doesn't work on multiprocessors as other processors can access resources in parallel - even if all interrupts are diabled on all processors. Userspace programs shouldn't be allowed to do it as they can disable preemption and monopolise the CPU.
Slows interrupt response time.
Disadvantages: it doesn't work on multiprocessors as other processors can access resources in parallel - even if all interrupts are diabled on all processors. Userspace programs shouldn't be allowed to do it as they can disable preemption and monopolise the CPU.
Slows interrupt response time.
21.
What is a test-and-set instruction? How can it be used to implement mutual
exclusion? Consider using a fragment of psuedo-assembly language aid you
explanation.
Test and set is an atomic instruction (meaning
uninterruptable) which always returns the content of the tested memory
location, and additionally set the location to 1 if (and only if) the memory
location contained 0.
lecture notes:
enter_critical_region:
tsl register, lock // try to set the lock, and copy the lock to 'register'
cmp register, 0 // if the register is zero
jne critical_region // then we don't hold the lock.
ret // return to caller after executing the critical region
leave_region:
move 0, lock // set lock to zero to release it.
ret
lecture notes:
enter_critical_region:
tsl register, lock // try to set the lock, and copy the lock to 'register'
cmp register, 0 // if the register is zero
jne critical_region // then we don't hold the lock.
ret // return to caller after executing the critical region
leave_region:
move 0, lock // set lock to zero to release it.
ret
22.
What is the producer consumer problem? Give an example of its occurence in
operating systems.
The producer consumer problem is a
problem that involves filling and depleting a bounded buffer. The producer
inserts entries into the buffer, and can sleep if it is full. The consumer must
retrieve data from the buffer, possibly sleeping if it is empty. Transactions
on the buffer itself may require a mutex. This is seen in operating systems in
buffers for everything, particularly i/o device input queues.
Given a single, fix-sized queue, the producer process(es) geenerate(s) an item to put into the queue while the consumer(s) take(s) the item out of the queue and consume(s) it.
Give an example of its occurence in operating systems.
Take file system buffer cache as example, the file system writes are produced by the application requests. OS has to find a free entry in the buffer cache to store the write or blocks the request until a free slot is available on the bounded buffer cache.
23.
A semaphore is a blocking synchronisation primitive. Describe how they work
with the aid of pseudo-code. You can assume the existance of a thread_block()
and a thread_wakeup() function.
A semaphore has two operations:
Verhogen and Proberen, increment.and decrement
P (decrementing) atomically reduces a counter by 1; if this drives it negative, it blocks until the counter is at least 0.
V (incrementing) atomically increases a counter by 1, and wakes threads sleeping on this semaphore.
Interrupts are disabled around these code regions such that they are atomic.
Psuedocode:
P:
// while decrementing would drive it negative, sleep.
sem.count--;
while (sem.count < 0) {
add this process to semphore queue
thread_block();
}
V:
// increment and wake other threads
sem.count++;
if (sem.count <= 0) {
remove head of semaphore queue
thread_wakeup(head);
}
P (decrementing) atomically reduces a counter by 1; if this drives it negative, it blocks until the counter is at least 0.
V (incrementing) atomically increases a counter by 1, and wakes threads sleeping on this semaphore.
Interrupts are disabled around these code regions such that they are atomic.
Psuedocode:
P:
// while decrementing would drive it negative, sleep.
sem.count--;
while (sem.count < 0) {
add this process to semphore queue
thread_block();
}
V:
// increment and wake other threads
sem.count++;
if (sem.count <= 0) {
remove head of semaphore queue
thread_wakeup(head);
}
24.
Describe how to implement a lock using semaphores.
A lock using semaphores is acheived by initialising the
semaphore to 1. The count of a semaphore is effectively the number that may be
allowed before preventing more in, so if it is 1, it acts as a lock. e.g.:
/* noncritical */
/* decrement semaphore (acquire lock) */
P(sem);
/* critical */
/* increment sem (release lock) */
V(sem);
/* noncritical */
/* noncritical */
/* decrement semaphore (acquire lock) */
P(sem);
/* critical */
/* increment sem (release lock) */
V(sem);
/* noncritical */
25.
What are monitors and condition variables?
Monitors are a programming language
construct designed to simplify control of concurrent access. Code related to a
shared resource (and the shared resource itself) is placed in a monitor,
then the compiler ensures that there is only one thread executing inside the
monitor at a time.
Condition variables are entities used within monitors to block and wait for an event, the operations 'wait' waits for the event to occur and 'signal'.
operation is used to generate the event. Basically, the thread invoking 'wait' sleeps until another thread wakes it with 'signal'.
Condition variables are entities used within monitors to block and wait for an event, the operations 'wait' waits for the event to occur and 'signal'.
operation is used to generate the event. Basically, the thread invoking 'wait' sleeps until another thread wakes it with 'signal'.
26.
What is deadlock? What is startvation? How do they differ from each other?
Deadlock is the state of a set of
threads where all threads in the set are blocked waiting for another
thread in the set to release a resource, and a required resource can only be
released by a thread in the blocked set. The set remains blocked forever.
Example with a set size of 2 {1,2}: Thread 1 needs the resource A and B to proceed, it holds A. Thread 2 needs resource A and B to proceed, it holds B. Both are blocking on the resource they need and cannot release what they are holding.
Starvation is the phenomenon where the allocation of resources is 'unfair', and something cannot proceed because it never gets the resources it requires even though the resources may become available as the resources are always granted to something else.
In deadlock, processes halt because they cannot proceed and the resources are never released. In starvation, the system overall makes progress using (and reusing) the resources, but particular processes consistently miss out on being granted their resource request.
Example with a set size of 2 {1,2}: Thread 1 needs the resource A and B to proceed, it holds A. Thread 2 needs resource A and B to proceed, it holds B. Both are blocking on the resource they need and cannot release what they are holding.
Starvation is the phenomenon where the allocation of resources is 'unfair', and something cannot proceed because it never gets the resources it requires even though the resources may become available as the resources are always granted to something else.
In deadlock, processes halt because they cannot proceed and the resources are never released. In starvation, the system overall makes progress using (and reusing) the resources, but particular processes consistently miss out on being granted their resource request.
27.
What are the four condtions required for deadlock to occur?
Mutual exclusion:
only one thread can use a resource at a time
Hold and wait:
a resource can be held, then blocking whilst waiting for more resources
No preemption:
resources cannot be forcibly taken away from process holding it
Circular wait:
A circular chain of 2 or more processes, each or which are waiting for a resouce held by the next member in the chain.
only one thread can use a resource at a time
Hold and wait:
a resource can be held, then blocking whilst waiting for more resources
No preemption:
resources cannot be forcibly taken away from process holding it
Circular wait:
A circular chain of 2 or more processes, each or which are waiting for a resouce held by the next member in the chain.
28.
Describe four general strategies for dealing with deadlocks.
1) ignore it
- easy
- especially if the other strategies are very costly, and deadlock is a rare occurence
2) detect and recover
detection:
- do pages of maths
- and some more maths
- then some more
- or perhaps explore a graph
- with maths
recover :
- then either steal preemptible resources, or try and save valid states of processes and roll back to them
- looks complicated...
3) deadlock avoidance
- disallow deadlock by trying to determine if allowing a particular resource allocation will cause deadlock
- only allow progression of programs into 'safe states', which guarantee process completion.
- difficult, because we need to know process requirements in advance, or do checks before allocating resources. this can often be impossible practically
4) deadlock prevention
- negate one of the 4 requirements of deadlock.
- solve hold and wait, by making threads drop resources they hold if they cannot get all of the resources they require for progress. this can cause starvation.
- usually done by using ordered resources, to break the circular dependancy condition. breaking other conditions is rarely a feasable option.
- easy
- especially if the other strategies are very costly, and deadlock is a rare occurence
2) detect and recover
detection:
- do pages of maths
- and some more maths
- then some more
- or perhaps explore a graph
- with maths
recover :
- then either steal preemptible resources, or try and save valid states of processes and roll back to them
- looks complicated...
3) deadlock avoidance
- disallow deadlock by trying to determine if allowing a particular resource allocation will cause deadlock
- only allow progression of programs into 'safe states', which guarantee process completion.
- difficult, because we need to know process requirements in advance, or do checks before allocating resources. this can often be impossible practically
4) deadlock prevention
- negate one of the 4 requirements of deadlock.
- solve hold and wait, by making threads drop resources they hold if they cannot get all of the resources they require for progress. this can cause starvation.
- usually done by using ordered resources, to break the circular dependancy condition. breaking other conditions is rarely a feasable option.
29.
For single unit resources, we can model resource allocation and requests as a
directed graph connecting processes and resources. Given such a graph, what is
involved in deadlock detection.
Deadlock detection can be done by
finding closed loops in the graph, which involve two or more processes
requesting resources which are hold by other processes.
30.
Is the following system of four processes with 2 resources deadlocked?
Current allocation matrix
P1 1 3
P2 4 1
P3 1 2
P4 2 0
Current request matrix
P1 1 2
P2 4 3
P3 1 7
P4 5 1
Availability Vector
1 4
Give 1 2 to P1:
Current allocation matrix
P1 2 5
P2 4 1
P3 1 2
P4 2 0
Current request matrix
P1 0 0
P2 4 3
P3 1 7
P4 5 1
Availability
0 2
P1 finishes, releases 2 5.
Current allocation matrix
P2 4 1
P3 1 2
P4 2 0
Current request matrix
P2 4 3
P3 1 7
P4 5 1
Availability
2 7
Give 1 7 to P3:
Current allocation matrix
P2 4 1
P3 2 9
P4 2 0
Current request matrix
P2 4 3
P3 0 0
P4 5 1
Availability
1 0
P3 finishes, releases 2 9:
Current allocation matrix
P2 4 1
P4 2 0
Current request matrix
P2 4 3
P4 5 1
Availability
3 9
Now there is no possible request that can be fulfilled, so it is deadlocked.
If the availability vector is as below, is the system above still deadlocked?
2 3
Scenario 2:
Current allocation matrix
P1 1 3
P2 4 1
P3 1 2
P4 2 0
Current request matrix
P1 1 2
P2 4 3
P3 1 7
P4 5 1
Availability Vector
2 3
Give 1 2 to P1:
Current allocation matrix
P1 2 5
P2 4 1
P3 1 2
P4 2 0
Current request matrix
P1 0 0
P2 4 3
P3 1 7
P4 5 1
Availability Vector
1 1
P1 finishes, releases 2 5:
Current allocation matrix
P2 4 1
P3 1 2
P4 2 0
Current request matrix
P2 4 3
P3 1 7
P4 5 1
Availability Vector
3 6
Now there is nothing satisfyable. Deadlocked
Scenario 3: Is the system deadlocked if the availability is
2 4
Current allocation matrix
P1 1 3
P2 4 1
P3 1 2
P4 2 0
Current request matrix
P1 1 2
P2 4 3
P3 1 7
P4 5 1
Availability Vector
2 4
Give 1 2 to P1
Current allocation matrix
P1 2 5
P2 4 1
P3 1 2
P4 2 0
Current request matrix
P1 0 0
P2 4 3
P3 1 7
P4 5 1
Availability Vector
1 2
P1 ends, releasing 2 5
Current allocation matrix
P2 4 1
P3 1 2
P4 2 0
Current request matrix
P2 4 3
P3 1 7
P4 5 1
Availability Vector
3 7
Run P3 (releases 1 2):
Current allocation matrix
P2 4 1
P4 2 0
Current request matrix
P2 4 3
P4 5 1
Availability Vector
4 9
Run P2 (releases 4 1):
Current allocation matrix
P4 2 0
Current request matrix
P4 5 1
Availability Vector
8 10
Then P4 can run. System isn't deadlocked.
General approach:
a) look for a process whose requests <= the availability.
we know we can then satisfy the requirements for this process, so we assume it gets its resources required and terminates. Thus, we can
b) release all resources *currently allocated* to that process, and add then to the pool.
c) repeat for all processes. If you eventually reach a point where you cannot do this, and there are still processes remaining, the system is deadlocked. If you release them all, you are safe.
P1 1 3
P2 4 1
P3 1 2
P4 2 0
Current request matrix
P1 1 2
P2 4 3
P3 1 7
P4 5 1
Availability Vector
1 4
Give 1 2 to P1:
Current allocation matrix
P1 2 5
P2 4 1
P3 1 2
P4 2 0
Current request matrix
P1 0 0
P2 4 3
P3 1 7
P4 5 1
Availability
0 2
P1 finishes, releases 2 5.
Current allocation matrix
P2 4 1
P3 1 2
P4 2 0
Current request matrix
P2 4 3
P3 1 7
P4 5 1
Availability
2 7
Give 1 7 to P3:
Current allocation matrix
P2 4 1
P3 2 9
P4 2 0
Current request matrix
P2 4 3
P3 0 0
P4 5 1
Availability
1 0
P3 finishes, releases 2 9:
Current allocation matrix
P2 4 1
P4 2 0
Current request matrix
P2 4 3
P4 5 1
Availability
3 9
Now there is no possible request that can be fulfilled, so it is deadlocked.
If the availability vector is as below, is the system above still deadlocked?
2 3
Scenario 2:
Current allocation matrix
P1 1 3
P2 4 1
P3 1 2
P4 2 0
Current request matrix
P1 1 2
P2 4 3
P3 1 7
P4 5 1
Availability Vector
2 3
Give 1 2 to P1:
Current allocation matrix
P1 2 5
P2 4 1
P3 1 2
P4 2 0
Current request matrix
P1 0 0
P2 4 3
P3 1 7
P4 5 1
Availability Vector
1 1
P1 finishes, releases 2 5:
Current allocation matrix
P2 4 1
P3 1 2
P4 2 0
Current request matrix
P2 4 3
P3 1 7
P4 5 1
Availability Vector
3 6
Now there is nothing satisfyable. Deadlocked
Scenario 3: Is the system deadlocked if the availability is
2 4
Current allocation matrix
P1 1 3
P2 4 1
P3 1 2
P4 2 0
Current request matrix
P1 1 2
P2 4 3
P3 1 7
P4 5 1
Availability Vector
2 4
Give 1 2 to P1
Current allocation matrix
P1 2 5
P2 4 1
P3 1 2
P4 2 0
Current request matrix
P1 0 0
P2 4 3
P3 1 7
P4 5 1
Availability Vector
1 2
P1 ends, releasing 2 5
Current allocation matrix
P2 4 1
P3 1 2
P4 2 0
Current request matrix
P2 4 3
P3 1 7
P4 5 1
Availability Vector
3 7
Run P3 (releases 1 2):
Current allocation matrix
P2 4 1
P4 2 0
Current request matrix
P2 4 3
P4 5 1
Availability Vector
4 9
Run P2 (releases 4 1):
Current allocation matrix
P4 2 0
Current request matrix
P4 5 1
Availability Vector
8 10
Then P4 can run. System isn't deadlocked.
General approach:
a) look for a process whose requests <= the availability.
we know we can then satisfy the requirements for this process, so we assume it gets its resources required and terminates. Thus, we can
b) release all resources *currently allocated* to that process, and add then to the pool.
c) repeat for all processes. If you eventually reach a point where you cannot do this, and there are still processes remaining, the system is deadlocked. If you release them all, you are safe.
31.
Assuming the operating system detects the system is deadlocked, what can the
operating system do to recover from deadlock?
An operating system can take resources if they are
preemptible (meaning the process doesn't die if it's taken away). It can kill a
process to free up resources. Otherwise, it can try and take snapshots of
process states, and roll back to state where the system was not deadlocked.
32.
What must the banker's algorithm know a priori in order to prevent deadlock?
The bankers algorithm must now the
maxmimal resource requirements of all processes.
We assume that the banker can keep track of resource availability and usage, and the process that receive the resources they require eventual finish and release them.
We assume that the banker can keep track of resource availability and usage, and the process that receive the resources they require eventual finish and release them.
33.
Describe the general strategy behind dealock prevention, and give an example of
a practical deadlock prevention method.
Deadlock prevention is removing the
capability of deadlock to occur, by negating one of the 4 conditions of
deadlock. A practical example of how to achieve this is to use ordered
resources, such that circular dependancies cannot form. see above
Note: avoiding deadlock via carefull allocation (e.g. banker algorithm) is not prevention, it is avoidance.
Note: avoiding deadlock via carefull allocation (e.g. banker algorithm) is not prevention, it is avoidance.
34.
Filesystems can support sparse files, what does this mean? Give an example of
an application's file organisation that might benefit from a file system's
sparse file support.
Sparse files mean that there aren't
physical blocks on the disk dedicated to holding empty parts of the file. An
application that might benefit from this is a CDROM image representing a
not full disk. the filesize would be the size of the hard disk, however unused parts
in the image do not mean blocks wasted.
This means filesystems support this
kind of file that if some entire blocks of one file contains nonmeaningful
data(should be null), these blocks need not be allocated on the disk.
Some database applications that lseek to large offsets obtained from large hash values may benefits for sparse files.
Some database applications that lseek to large offsets obtained from large hash values may benefits for sparse files.
35.
Give an example of a scenario that might benefit from a file system supporting
an append-only access write.
Log files (e.g. used for auditing),
append-only prevents modifying (accidently or otherwise) any existing log
entries.
36.
Give a scenario where choosing a large filesystem block size might be a
benefit; give an example where it might be a hinderance.
Large blocksizes would be good when
uber large files are being used, e.g. a video collection on a disk, and almost
no little files. Particular benefits in sequencial access. (and less
metadata required to keep track of the smaller number of blocks)
It would be a waste of disk blocks in filesystems that store alot of little files, like news, /etc, my physiology study so far, etc. It is also poorer performance when there is random access of small segments of data, as we need to load the entire block, even though we may olny need a tiny portion of it.
It would be a waste of disk blocks in filesystems that store alot of little files, like news, /etc, my physiology study so far, etc. It is also poorer performance when there is random access of small segments of data, as we need to load the entire block, even though we may olny need a tiny portion of it.
37.
Give an example where contiguous allocation of file blocks on disks can be used
in practice.
CDROM file systems - you know how
big al the files are prior to burning the disk.
38.
What file access pattern is particularly suited to chained file allocation on
disk?
Sequencial file access is suited to chained file allocation.
The chain is effectively a linked list that is traversed as the file is read.
Random access is poor, because each prior link of the chain must be considered to get to any point of the file.
Random access is poor, because each prior link of the chain must be considered to get to any point of the file.
39.
What file allocation strategy is most appropriate for random access files?
Indexed allocation is appropriate
for random access, as there is a constant time (slowing down very slightly with
increased indirection levels), for accessing any part of the file.
40.
Compare bitmap-based allocation of blocks on disk with a free block list.
Bitmap based block allocation is a fixed size proportional
to the size of the disk. THis means wasted space when it's full. A free block
list shrinks as space is used up, so when the disk is full, the size of the
free block list is tiny.
Contiguous allocation is easier to perform/find with a bitmap.
Contiguous allocation is easier to perform/find with a bitmap.
41.
How can the block count in an inode differ from the (file size / block size)
rounded up to the nearest integer. Can the block count be greater, smaller, or
both.
Block count can be larger than the
filesize, if the file is non-sparse, and additional blocks are required for
holding metadata. This is the norm.
Block count can be smaller, in the case of a sparse file using only a small fraction of the file, the data and metadata is less than the notional size of the sparse file.
They can be equal with just the right tradeoff of the above cases.
Block count can be smaller, in the case of a sparse file using only a small fraction of the file, the data and metadata is less than the notional size of the sparse file.
They can be equal with just the right tradeoff of the above cases.
42.
Why might the direct blocks be stored in the inode itself?
Quick access to the start of the
file stored in the inode itself. For small files, no direct blocks
required, entire file can be in the inode. This improves the performance for
small files.
43.
Given that the maximum file size of combination of direct, single indirection,
double indirection, and triple indirection in an inode-based filesystem is
approximately the same as a filesystem soley using triple indirection, why not
simply use only triple indirection to locate all file blocks?
Triple indirection is slower, as it
may result in multiple seeks to get to the desired block. Seeks take a long
time. Tiny files that only use a few KB will perform much better if they do not
have to do seeks to find each level of indirection... see 42 (lol).
44.
What is the maximum file size supported by a file system with 16 direct blocks,
single, double, and triple indirection? The block size is 512 bytes. Disk block
numbers can be stored in 4 bytes.
block size = 512
number of block numbers in an indirection block
= block size / 4
= 128
number of blocks for file data in that file object
= 16 + 128 + 128^2 + 128^3
Maximum file size:
(direct + single indirect + double indirect + triple indirect) * (blocksize)
= (16 + 512/4 + (512/4)^2 + (512/4)^3) * (512)
= 68853964800 bytes, ~64 gigs
number of block numbers in an indirection block
= block size / 4
= 128
number of blocks for file data in that file object
= 16 + 128 + 128^2 + 128^3
Maximum file size:
(direct + single indirect + double indirect + triple indirect) * (blocksize)
= (16 + 512/4 + (512/4)^2 + (512/4)^3) * (512)
= 68853964800 bytes, ~64 gigs
45.
The berkely fast filesystem (and Linux Ext2fs) use the idea of block groups.
Describe what this idea is and what improvements block groups have over the
simple filesystem layout of the System V file system (s5fs).
Block groups are clustered
arragements of related data blocks and inodes. This increases performance
through spacial locality of data arranged on the disk. System V didn't do this,
so it didn't see performance gains through locality.
Also, the super-block was replicated in each group, so the file system was no longer lost if the one s5fs super block went bad.
Also, the super-block was replicated in each group, so the file system was no longer lost if the one s5fs super block went bad.
46.
What is the reference count field in the inode? You should consider its
relationship to directory entries in you answer.
The refernce count is the number of
hard links (names in directories) presently pointing at a particular inode.
When this reaches zero, it is an indication that that inode can be deleted,
since nothing points at it anymore (it has no name).
47.
The filesystem buffer cache does both buffering and caching. Describe why buffering
is needed. Describe how buffering can improve performance (potentially to the
detriment of file system robustness). Describe how the caching component of the
buffer cache improves performance.
Buffering is required when the unit
of transfer/update is different between two entities (e.g. updating 1 byte in a
disk block requires buffering the disk block in memory). Buffering can improve
performance as writes to disk can be buffered and written to disk in the
background - this does reduce file system robustness to power failures and
similar.
Caching is loading used data into the buffercache, such that subsequent reads to the same area of data are accelerated by using the data in cache and not having to access disk. The acceleration is seen due to the principle of locality; if data is used, data nearby will be used soon, so the application will run alot faster if it is in RAM rather than requiring a disk seek, which is several orders of magnitude slower.
Caching is loading used data into the buffercache, such that subsequent reads to the same area of data are accelerated by using the data in cache and not having to access disk. The acceleration is seen due to the principle of locality; if data is used, data nearby will be used soon, so the application will run alot faster if it is in RAM rather than requiring a disk seek, which is several orders of magnitude slower.
48.
What does flushd do on a UNIX system?
Periodically syncs (writes) dirty
blocks to disk (every 30 seconds) to avoid significant data loss on
unexpected OS shutdown/powerloss.
Also indirectly improves performance as it increases the number of clean blocks, and clean blocks can be booted immediately from buffer cache rather than writing them back, which should be a speedup.
Also indirectly improves performance as it increases the number of clean blocks, and clean blocks can be booted immediately from buffer cache rather than writing them back, which should be a speedup.
49.
Why might filesystems managing external storage devices do write-through
caching (avoid buffering writes) even though there is a detrimental affect on
performance.
External devices have no guarantee
of connectivity. To ensure filesystem consistency, writes should be made
without caching and be made as atomic as possible in case the drive is removed
before the write has been committed to the drive.
50.
Describe the difference between external and internal fragmentation. Indicate
which of the two are most likely to be an issues on a) a simple memory memory
mangement machine using base limit registers and static partitioning, and b) a
similar machine using dynamic partitioning.
- Internal fragmentation: the space
wasted internal to the allocated region.Allocated memory might be slightly
larger than requested memory.
- External fragmentation: the space wasted external to the allocated region.memory exists to satisfy a reqest but it's unsuable as it's not contiguous.
Stattic partitioning is more likely to suffer from internal fragmentation.
Dynamic partitioning is more likely to suffer from external fragmentation.
- External fragmentation: the space wasted external to the allocated region.memory exists to satisfy a reqest but it's unsuable as it's not contiguous.
Stattic partitioning is more likely to suffer from internal fragmentation.
Dynamic partitioning is more likely to suffer from external fragmentation.
51.
List and describe the four memory allocation algorithms covered in lectures.
Which two of the four are more commonly used in practice?
First fit - allocate into the first
available gap found of adequate size, starting from the beginning of memory.
Next fit - allocate into the first available gap found, resuming the search from the last allocation.
Best fit - search all of memory to find the smallest valid gap and allocate into it, on the basis that it'll leave the smallest unusable gap.
Worst fit - search and place into the largest area, on the basis that it is likely to leave a gap big enough for something else to use.
First and next fit are used in practice as they are faster, with comparable performance.
Next fit - allocate into the first available gap found, resuming the search from the last allocation.
Best fit - search all of memory to find the smallest valid gap and allocate into it, on the basis that it'll leave the smallest unusable gap.
Worst fit - search and place into the largest area, on the basis that it is likely to leave a gap big enough for something else to use.
First and next fit are used in practice as they are faster, with comparable performance.
First-fit
Scan memory region list from start for first fit.
Must always skip over potentially many regions at the start of list.
Next-fit
Scan memory region list from point of last allocation to next fit.
Breaks up large block at the end of memory
Best-fit
Pick the closest free region in the entire list
Leaves small unusable regions and slower due to searching of entire list.
Worst-fit
Finds the worst fit in the entire list
Slower as it searches entire list. Fragmentation still an issue.
First-fit and next-fit most commonly used as it is easier to implement and works out better.
Scan memory region list from start for first fit.
Must always skip over potentially many regions at the start of list.
Next-fit
Scan memory region list from point of last allocation to next fit.
Breaks up large block at the end of memory
Best-fit
Pick the closest free region in the entire list
Leaves small unusable regions and slower due to searching of entire list.
Worst-fit
Finds the worst fit in the entire list
Slower as it searches entire list. Fragmentation still an issue.
First-fit and next-fit most commonly used as it is easier to implement and works out better.
52.
Base-limit MMUs can support swapping. What is swapping? Can swapping permit an
application requiring 16M memory to run on a machine with 8M of RAM?
Swapping is the act of running each
whole process in main memory for a time then placing back onto disk and vice
versa. It is used when the system does not have enough main memory to hold all
the currently active processes.
Assuming that an application is one program and hence a single process, swapping will not permit an application(process) requiring 16M of memory to run on a machine with 8M RAM (main memory) as the whole process is too large to fit into main memory.
Assuming that an application is one program and hence a single process, swapping will not permit an application(process) requiring 16M of memory to run on a machine with 8M RAM (main memory) as the whole process is too large to fit into main memory.
53.
Describe page-based virtual memory. You should consider pages, frames, page
tables, and Memory Management Units in your answer.
Each process has it's own page
table, which is a mapping betweem virtual pages and physical frames. A page is
a chunk of virtual memory (commonly 4KB) that exists within the processes
virtual memory space. This is mapped to a physical frame (4KB of real 1s and 0s
in RAM) using a page table.
The program is given the illusion of running in it's own address space. CPU instructions execute the program, which will perform memory requests to virtual addresses. These are converted to physical addresses by looking up in the Page Table, (more specifically the Translation Lookaside Buffer (TLB)), then the physical memory is accessed.
The TLB is the fast hardware implementation of a page table lookup. It contains recently used page table entries, which allow a really quick mapping between virtual pages and physical frames. In the event that the TLB doesn't contain the virtual address requested, a page fault is triggered. The operating system is called to find the approriate mapping from the page table, stored in RAM, and load it into the the TLB as appropriate. (in MIPS... Pentium architectures have some dedicated hardware for pagetables, and therefore some hardware support for tlb refill).
The program is given the illusion of running in it's own address space. CPU instructions execute the program, which will perform memory requests to virtual addresses. These are converted to physical addresses by looking up in the Page Table, (more specifically the Translation Lookaside Buffer (TLB)), then the physical memory is accessed.
The TLB is the fast hardware implementation of a page table lookup. It contains recently used page table entries, which allow a really quick mapping between virtual pages and physical frames. In the event that the TLB doesn't contain the virtual address requested, a page fault is triggered. The operating system is called to find the approriate mapping from the page table, stored in RAM, and load it into the the TLB as appropriate. (in MIPS... Pentium architectures have some dedicated hardware for pagetables, and therefore some hardware support for tlb refill).
54.
Give some advantages of a system with page-based virtual memory compared to a
simply system with base-limit registers that implements swapping.
A simple base limit with swapping
system requires that all of the data from base to limit must be resident in
contiguous main memory for execution. This can lead to external fragmentation,
and swapping is much more likely to occur when memory is becoming full. This
incurs a huge penalty when context switching, because a large chunk must be
swapped out to disk, then a large chunk retrieved from disk before execution
can resume. Disk is horridly slow compared to ram.
In a paging system, physical memory doesn't have to be contiguous, and there is no external fragmentation, so only the minimum amount of memory needs to be moved in a context switch; only the pages required to hold the resident set are required to be in memory for execution.
The paging sceme makes it possible for the resident sets of many processes to be present in memory, which drastically increases the performance of a context switch as there is much less likely to be a disk access on context switching.
Also, paging supports running a process who's virtual memory usage is greater than the size of physical RAM in the machine.
In a paging system, physical memory doesn't have to be contiguous, and there is no external fragmentation, so only the minimum amount of memory needs to be moved in a context switch; only the pages required to hold the resident set are required to be in memory for execution.
The paging sceme makes it possible for the resident sets of many processes to be present in memory, which drastically increases the performance of a context switch as there is much less likely to be a disk access on context switching.
Also, paging supports running a process who's virtual memory usage is greater than the size of physical RAM in the machine.
55.
Describe segmentation-based virtual memory. You should consider the components
of a memory address, the segment table and its contents, and how the final
physical address is formed in your answer.
Segmentation is made up of many
small base limit portions (segments), each having a segment number and a size.
The segments allow multiple processes to share data on a per segment basis, and
since segments may be arbitrarily defined to contain code/stack/whatever, this
could be a per subroutine basis. It also allows permissions of each segment to
be set appropriately. An annoyance is that the programmer must be aware of the
segmentation, and this isn't trivial. Segments are loaded into contiguous
regions of physical memory. The segment number, base, limit & permissions
are stored in a per-process segment table.
An instruction looks like this:
operation, whatever, segment number, offset.
When the instruction is computed, the segment table is looked up to find the appropriate segment based on segment number. If the segment number is present in a table entry, and offset is smaller than limit - base, the physical address is formed out of base + offset. Then the physical memory is fetched and the operation performed. If the segment isn't present, or the offset is out of bounds, a fault is handed to the operating system that would then deal with the process.
An instruction looks like this:
operation, whatever, segment number, offset.
When the instruction is computed, the segment table is looked up to find the appropriate segment based on segment number. If the segment number is present in a table entry, and offset is smaller than limit - base, the physical address is formed out of base + offset. Then the physical memory is fetched and the operation performed. If the segment isn't present, or the offset is out of bounds, a fault is handed to the operating system that would then deal with the process.
56.
What is a translation look-aside buffer? What is contained in each entry it
contains?
TLB is a fast hardware implementation of a page table lookup. Recent page table entries used are loaded into the TLB , such that virtual to physical address conversion is really fast. When a virtual address cannot be successfully translated by the TLB, a pagefault is thrown and the OS finds the appropriate frame in the page table, or if it is an invalid operation, kills the process. see 53
Each TLB entry has page number (for matching), and frame number associated with that page, privileges, and ASID (sometimes).
The frame number is the significant bits of the physical memory address. Privileges are what operations can be performed; this provides some memory protection to shared libraries and code segments; e.g. a process cannot execute in it's stack, or cannot write to code, etc.
Address spaces, and the page tables used to map them, are a per process entity. The ASID (address space identifier) is used to check if tlb entries present are those of the by the currently running process, and therefore the currently active page table. ASIDs allow multiple processes to have hot TLB entries by not requiring complete flushing of the TLB on a context switch. This will boost performance just after a context switch.
57.
Some TLBs support address space identifiers (ASIDS), why?
see 56
58.
Describe a two-level page table? How does it compare to a simple page table
array?
For a 32 bit (4GB) virtual address space, with 4K pages/frames:
A two level page table uses indirection to save memory and at the expense of time. The top-level page table (an array of 1024 pointers to 2nd-level arrays) would be indexed such that the most significant bits of the virtual address (VADDR[31:22]) are used to look up the 2-level array (of page-table entries - frame numbers and permissions), where some of the less significant bits VADDR[21:12] are used to index that table.
This is preferential to simple page table arrays as it allows second level pages to be omitted if they're not required. It also means that a rediculously long array is not required either. 2^20 page table entries, 4 bytes each, is 2^22 bytes, is 4MB of memory required to hold a 1-level page table. If the page table itself can be swapped, this is a big disk hit. If not, 4MB must be resident in physical memory as contiguous segments, which can cause fragmentation.
2-level page table is slower to look up as it requires 2 memory references per lookup.
assume we got 32-bits virtual address and 4k page size, top
level table A, and second level table B, first 10 is to locate A's index, and
next 10-bits is the offset to locate B's index, using A's content to locate the
B's base address, and plus the offset to B's index, we got the physical frame
index; then using the last 12 bits plus the B's content, finally the physical
address located.
The two-level table avoids allocating pagetables for all possible translations, if the translations are not required.. A disadvantage is that it requires 2 memory references to look up a page table entry, instead of one.
The two-level table avoids allocating pagetables for all possible translations, if the translations are not required.. A disadvantage is that it requires 2 memory references to look up a page table entry, instead of one.
59.
What is an inverted page table? How does it compare to a two-level page table?
An inverted page table is a list of
pages sorted by frame number. Inverted page tables hash the virtual address
page number to lookup into the page table, which then matches the page number
(or uses a linked list structure to find the page). This index is the frame
number.
Page table size is proportional to size of physical memory, not address space size. This is particularly important on 64 bit machines, where virtual address space size, if 2^64 bytes, is 16 Giga Giga bytes; storing a multi level page table for this would require too many levels of indirection and be slow, and require alot of space to store.
Page table size is proportional to size of physical memory, not address space size. This is particularly important on 64 bit machines, where virtual address space size, if 2^64 bytes, is 16 Giga Giga bytes; storing a multi level page table for this would require too many levels of indirection and be slow, and require alot of space to store.
Inverted page table is an array of
page numbers sorted (indexed) by frame number. Virtual address is hashed
to locate the entry in the frame table. The most important advantage is that
its size is related to physical memory size, not virtual memory. Inverted page
table is good for system with large addressing space but significantly less
physical memory (e.g. 64-bit addressing with 2GB of ram)
60.
What are temporal locality and spatial locality?
temporal locality (locality of time)
is the phenomenon where if a piece of memory is accessed, it is likely that
that piece of memory will be accessed again in the near future. spatial
locality is where if a piece of memory is accessed, it is likely that future
accesses will be to similar addresses. These phenomena are why caching works;
memory accesses are rarely random.
61.
What is the working set of a process?
The pages/frames currently relevant
for the execution of a process. It includes the current top of stack, areas of
the heap being accessed, the current area of code segment being executed, and
any shared libraries recently used.
The workset of a process consists of
all pages accessed within in the recent past (a small, current, time window).
62.
How does page size of a particular achitecture affect working set size?
If the page size is small, the work
set size is smaller (in terms of memory used, not absolute number of pages) as
the pages more accurately reflect current memory usage (i.e. there is less
unrelated data within the page).
If the page size is large, working set also increases as more unrelated data within the larger pages are included in the current working set.
If the page size is large, working set also increases as more unrelated data within the larger pages are included in the current working set.
63.
What is thrashing? How might it be detected? How might one recover from it once
detected?
Thrashing is when you're trying to
run java 'hello world', and any other process on a system. The memory
requirements of the currently running processes are so large that the working
sets of the executing processes cannot be contained in physical memory. So one
process tries to run, gets a page fault, retrieves the page from swap, boots
out another processes' frame doing that. Then it context switches and the other
process tries to run, but it's memory has been booted, so it page faults to
swap, etc. The time is spent swapping frames rather than getting anything done.
It could be detected by monitoring swapping levels compared to real cpu utilization. If swapping is huge, and utilization is down, thrashing is occuring. Suspending processes can alleviate thrashing; hopefully some processes will go below the thrashing threshold, run, terminate, then free up memory for other processes. Installing more ram helps, and not running java hello world helps.
It could be detected by monitoring swapping levels compared to real cpu utilization. If swapping is huge, and utilization is down, thrashing is occuring. Suspending processes can alleviate thrashing; hopefully some processes will go below the thrashing threshold, run, terminate, then free up memory for other processes. Installing more ram helps, and not running java hello world helps.
Thrashing occurs when too many processes are run on a
processor at a given time. What occurs is the the number of page faults
increase dramatically and the virtual memory subsystem is constantly paging
pages in and out of memory. This occurs when the working set of all processes
is larger than the amount of RAM available on a system.
This can be detected by monitoring the page fault frequency and CPU utilisation. If increasing the number of processes results in increasing page fault rate and decreasing CPU utilisation, then the system is thrashing.
To recover from this condition the number of processes currently in the running/ready queue must be reduced. This can be accomplised by suspending processes (pushing them onto the sleeping queue), so that pressure on physical memory is reduced (suspended processes eventually get swapped out), and thrashing subsides.
This can be detected by monitoring the page fault frequency and CPU utilisation. If increasing the number of processes results in increasing page fault rate and decreasing CPU utilisation, then the system is thrashing.
To recover from this condition the number of processes currently in the running/ready queue must be reduced. This can be accomplised by suspending processes (pushing them onto the sleeping queue), so that pressure on physical memory is reduced (suspended processes eventually get swapped out), and thrashing subsides.
64.
Enumerate some pros and cons for increasing the page size.
pros:
reduces pagetable size
increases tlb coverage
increases swapping I/O throughput, as small disk transaction times are dominated by seek & rotational delays.
cons:
increases page fault latency, as swap response time is slower due to more data.
increases internal fragmentation of pages, as there is more 'wasted page' in the working set
reduces pagetable size
increases tlb coverage
increases swapping I/O throughput, as small disk transaction times are dominated by seek & rotational delays.
cons:
increases page fault latency, as swap response time is slower due to more data.
increases internal fragmentation of pages, as there is more 'wasted page' in the working set
65.
Describe two virtual memory page fetch policies. Which is less common in
practice? Why?
Demand paging - relevant pages are
loaded as page faults occur
Pre paging - try to load pages for a process before they're accessed. Wastes I/O bandwidth if pages are loaded unnecessarily, and worse if an unnecessary page kicks out a necessary page.
Pre paging - try to load pages for a process before they're accessed. Wastes I/O bandwidth if pages are loaded unnecessarily, and worse if an unnecessary page kicks out a necessary page.
Demanding paging (or fetch on demand) : load pages when page
fault occur, and is more common.
Prepaging policy : Pre-paging brings in more pages than needed at the
moment. IO is improved due to reading large chunks but waste bandwith if pages aren't used. Especially bad if we eject pages in working set in order to pre-fetch unused pages. Hard to get in right in practice.
Prepaging policy : Pre-paging brings in more pages than needed at the
moment. IO is improved due to reading large chunks but waste bandwith if pages aren't used. Especially bad if we eject pages in working set in order to pre-fetch unused pages. Hard to get in right in practice.
66.
What operating system event might we observe and use as input to an algorithm
that decides how many frames an application receives (i.e. an algorithm that
determines the application's resident set size)?
Monitor page fault frequency of an
application - high frequency => needs more memory allocated to resident set
size
67.
Name and describe four page replacement algorithms. Critically compare them
with each other.
From best to worst (lecture notes):
1) Optimal - use time travel to find the page that won't be used for the most time and boot it. Impossible to implement - used only as a theoretical reference point for comparing over algorithms.
2) Least Recently Used - calculate whatever page hasn't been used the longest, and boot it. impossible to implement efficiently in practice - requires a timestamp on every memory reference.
3) Clock page replacement - set 'referenced' bit to 1 when something is used. when looking for an entry to boot, set these bits to 0 if they're 1, and kick the first 0 candidate found. resume searches from the last one booted. Efficient (implementable) approximation of LRU - used in practice.
4) FIFO - remove the page that has been there longest - does not consider actual memory usage in its decision - it will evict the most frequently used page in the system.
1) Optimal - use time travel to find the page that won't be used for the most time and boot it. Impossible to implement - used only as a theoretical reference point for comparing over algorithms.
2) Least Recently Used - calculate whatever page hasn't been used the longest, and boot it. impossible to implement efficiently in practice - requires a timestamp on every memory reference.
3) Clock page replacement - set 'referenced' bit to 1 when something is used. when looking for an entry to boot, set these bits to 0 if they're 1, and kick the first 0 candidate found. resume searches from the last one booted. Efficient (implementable) approximation of LRU - used in practice.
4) FIFO - remove the page that has been there longest - does not consider actual memory usage in its decision - it will evict the most frequently used page in the system.
68.
Describe buffering in the I/O subsystem of an operating system. Give reasons
why it is required, and give a case where it is an advantage, and a case where
it is a disadvantage.
Buffering in the i/o subsystem is required to match two
entities when the unit of tranfer is different (e.g. updating 1 byte in a disk
block requires buffering the disk block in memory).
Buffering is advantageous if the peak rates of producing and consuming data is different. Data can arrive asynchronously, pile up in a buffer whilst the processor is doing something else useful, then it'll context switch to the process waiting on that buffer which can then do an operation on lots of data;
Too much buffering in really high speed networks can reduce performance, if the time required to copy between buffers is comparable to the time spent acting on data.
Buffering is advantageous if the peak rates of producing and consuming data is different. Data can arrive asynchronously, pile up in a buffer whilst the processor is doing something else useful, then it'll context switch to the process waiting on that buffer which can then do an operation on lots of data;
Too much buffering in really high speed networks can reduce performance, if the time required to copy between buffers is comparable to the time spent acting on data.
69.
Device controllers are generally becoming more complex in the functionality
they provide (e.g. think about the difference between implementing a serial
port with a flip-flop controlled by the CPU and a multi-gigabit network adapter
with the TCP/IP stack on the card itself). What effect might this have on the
operating system and system performance?
Pushing more I/O functionality into device controllers
relieves the operating system from having to perform it (e.g. adding DMA to a
device controller relieve the OS from having to copy data to memory). This
results in improved performance as the OS only has to supervise the device,
instead of doing all the work itself in the device driver, also the I/O
functionality can now happen in parallel with the OS/application doing somthing
else. It may also reduce device driver complexity and improve reliability, but
that is dependent on whether the complex device is actually reliable itself.
70.
Compare I/O based on polling with interrupt-driven I/O. In what situation would
you favour one technique over the other?
In polling based I/O, the OS simply
busy waiting on a loop, continuly checking for I/O, whereas in interrupt-driven
I/O, when an I/O job arrive an interrupt is generated and the OS runs the
interupt-handler, after that it return to what it was doing before the
interrupt came.
If the cost for interrupt handling (the cost of switching to kernel-mode and preserving the user-level context and then eventually returning again) is bigger than the time spent busy-waiting in polling and the rate of I/O jobs arrive is high then polling is prefered, otherwise the latter is a better choice.
If the cost for interrupt handling (the cost of switching to kernel-mode and preserving the user-level context and then eventually returning again) is bigger than the time spent busy-waiting in polling and the rate of I/O jobs arrive is high then polling is prefered, otherwise the latter is a better choice.
1 poll is cheaper than 1 interrupt;
but 1 interrupt guarantees an event, polling may have thousands of wasted
polls. Interrupt driven I/O is preferential when input is unpredictable, e.g.
packets, typeing, mouses. Polling is favourable when the time spent busy
waiting is less than the time spent dealing with interrupt overheads
71.
Explain how the producer-consumer problem is relevant to operating system I/O.
Many I/O devices utilise a buffer to
store incoming information. Upon an event, such as entering the 'new line'
character, it notifies the OS / user program. Data is then copied from the
buffer to a location which it can be used, and the consumed data is cleared
from the buffer.
This is an example of a bounded-buffer producer-consumer problem, where the producer is the I/O device, the consumer is the OS / user program and the buffer is bounded by its size. Therefore, concurrency control must be implemented to ensure that race conditions do not occur. Additionally, the OS / program must consume the buffer quickly enough to prevent it from overflowing and lose information.
This is an example of a bounded-buffer producer-consumer problem, where the producer is the I/O device, the consumer is the OS / user program and the buffer is bounded by its size. Therefore, concurrency control must be implemented to ensure that race conditions do not occur. Additionally, the OS / program must consume the buffer quickly enough to prevent it from overflowing and lose information.
72.
What is disk interleaving? What problem is it trying to solve?
Disk interleaving is putting blocks
like 1 - 2 - 3 - 4 rather than 1 2 3 4 5 6, such that each read occurs at a
nice time. It addresses latency between successive disk block reads lining up
with latency of disk rotation, so that when the next read comes along, it's
just before the block requested rather than just after.
73.
What is cylinder skew? What problem is it trying to solve?
cylinder skew is vagely like
interleaving, except it is an offset of the next block between cylinders, such
that rotation and cylinder head seek latency are taken into account. The idea
is for when the request for the block on the disk results in a seek to the next
track, the block is further around on the disk such that when the seek is
complete the disk block is just arriving under the head, instead of having been
missed. T
74.
Name four disk-arm scheduling algorithms. Outline the basic algorithm for each.
SSTF: shortest seek time first:
service the requests that requires the least head movement next. quick, but can
suffer starvation.
FCFS: process requests in the order they were received. deteriotes to random with multiple processes accessing the disk.
SCAN: service all pending requests in ascending order until the end of the disk platter is reached, then service all requests in descending order until the start of the disk platter is reached, repeat ad infinitum.
C-SCAN: SCAN, but only the ascending pass is done. When it reaches the end it just goes back to the beginning. Increases performance due to ascending disk block numbers of contiguous files, that are likely to be missed on the downward pass of SCAN.
FCFS: process requests in the order they were received. deteriotes to random with multiple processes accessing the disk.
SCAN: service all pending requests in ascending order until the end of the disk platter is reached, then service all requests in descending order until the start of the disk platter is reached, repeat ad infinitum.
C-SCAN: SCAN, but only the ascending pass is done. When it reaches the end it just goes back to the beginning. Increases performance due to ascending disk block numbers of contiguous files, that are likely to be missed on the downward pass of SCAN.
75.
What are the three general goals of computer security?
Confidentiality - preventing
unauthorized people from gaining access to private data
Integrity - data is only modifyable/producable by authorized people (or the data is well formed)
Availability - providing the data/services intended to authorised parties in a timely fashion
Integrity - data is only modifyable/producable by authorized people (or the data is well formed)
Availability - providing the data/services intended to authorised parties in a timely fashion
76.
Which of the three goals of computer security is the following an attack on:
a)
Network snooping
b)
A distributed denial of service attack
c)
Modifiying your marks in the student records database
snooping is an attack on confidentiality
distributed DOS is an attack of availability
modifying marks is an attack on integrity
77.
Give an example of why it is important to consider the skill and resources
available to likely intruders when designing computer security mechanisms and
policies to defend against those intruders?
It the intruder has few skills or
resources (e.g. grandma), then a simple cheap security mechanism might be
sufficient (e.g. passwords).
If the adversary is the US government, then passwords will be of little defence.
If the adversary is the US government, then passwords will be of little defence.
78.
You are desigining an authentication mechanism to be used by a user with a web
client to authenticate it to a web server. The network connection is known to
be easily snoopable, but confidentiality of traffic after authentication is of
no concern. What authentication protocol covered in lectures would be most
appropriate and why.
Challenge response (or less convenient one-time passwords)
as network snooping does not reveal anything to the intruder that can be used
later to gain access.
79.
Describe what a buffer overrun attack is.
buffer overrun is when some noob
used gets (i.e. code does not check the bounds of an array allocated on the
stack that is used for buffering input), and they end up corrupting your stack
with a phony function return address and malicious code sent in the input. When
the code thinks it's returning from a subroutine, it'll jump to the malicious
code and send your music collection to the RIAA.
80.
What is the principle of least privilege? Why is the setuid root facility in
UNIX generally a violation of the principle? Give an illustrative example of
that violation.
least privilege is where you give a
something the bare minimum amount of permissions it requires in order to
operate. setuid is generally a violation, because it allows programs root
access (or other user access) for their execution. if the program does become
compromised, it's in this really really privileged position where it can do
anything and break anything.
81.
Running active web content in a web browser securely is a difficult problem.
JAVA (with its controlled interpretation of the downloaded code) is one
approach to the problem, ActiveX with its digitally signed code to guarantee authenticity
is another approach. Give an advantage and a disadvantage of each approach.
java is more secure, but there is a performance hit in
interpreting code.
activex is silly; it allows native binaries to be run, which are really fast, but 'Hey! Do You Want Me To Install Spyware? Was That A Yes? OKAY!!!
' isn't security.
if i was a virus writer, i'd love it.
activex is silly; it allows native binaries to be run, which are really fast, but 'Hey! Do You Want Me To Install Spyware? Was That A Yes? OKAY!!!
' isn't security.
if i was a virus writer, i'd love it.
JAVA:
advantage: Able to check addresses are valid at run-time
disavantage: Run slow compared to running code natively
ActiveX:
advantage: Faster than interpretation
disavantage: Doesn't protect the user from bad/buggy code
advantage: Able to check addresses are valid at run-time
disavantage: Run slow compared to running code natively
ActiveX:
advantage: Faster than interpretation
disavantage: Doesn't protect the user from bad/buggy code
82.
What is the difference between mandatory access control and discretionary
access control?
mandatory is the strict enforcement
of a security policy that is out of users control (policy set by system
admin/owner). in discretionary, it's up to you (the user) to choose what you
hide & reveal.
83.
What are access control lists and capabilties, and how do they relate to the
protection matrix model of representing authority in a system.
Access control lists define what
users / processes are able to perform certain actions on a resource. For
example, UNIX permissions: read, write, execute. Capabilities define, for each
user / process, what actions they can perform on different resources. They are
both ways to represent the protection matrix model of authority in a system.
ACLs represent the protection matrix stored by column, capabilities represent the protection matrix stored by row (asusming, like in the notes that each rows is labelled by process and each column is labelled by an object/resource).
ACLs represent the protection matrix stored by column, capabilities represent the protection matrix stored by row (asusming, like in the notes that each rows is labelled by process and each column is labelled by an object/resource).
84.
Explain how it is easier to apply the principle of least privilege in a
capability-based system compared to an access-control-list-based system.
access control lists typically give
permissions to broad categories of domains, e.g. unix files grouping domains on
a per user/group/eveyone basis. this means that any process operating as that user
will have access to every file that user has access to, which is usually far
more than the process needs, unless a special user is created just for running
that process, which is fiddly (many unix daemons do this).
to actually apply least privilege wich acls requires either a special user for each process, or to find every resource the process can access and temporarily modify the privileges. this is difficult, time consuming, and impractical.
using capability based systems, each process is assigned a minimal set of capabilities upon creation. the process is given least privilege when it is made, which is easy to enforce.
to actually apply least privilege wich acls requires either a special user for each process, or to find every resource the process can access and temporarily modify the privileges. this is difficult, time consuming, and impractical.
using capability based systems, each process is assigned a minimal set of capabilities upon creation. the process is given least privilege when it is made, which is easy to enforce.
The imprtant point is that with
ACLs, all processes owned by the user have the same privileges, thus is
difficult to apply POLP.
With capabilities, each process has capabilties to the objects it can access. It is easier when creating a new process to only give the process the caps it needs, i.e. the least privilege it requires.
As ACL's (Access control lists) are done on the actual resources (files, printers etc), these access permissions allow the user to make use of the resources. Hence any process with the User's ID would also have acess to these resources.
To apply Principle of Least Privaledge to the process we would have to remove the right for this process to acess every single resource before run time (this is the difficult part). That would envlove looking for every single resource the process has access to (VERY HARD TO DO with ACL) and then modifying every single resource (also time consuming).
The better way to do it would be with capabilites.
With capabilities, each process has capabilties to the objects it can access. It is easier when creating a new process to only give the process the caps it needs, i.e. the least privilege it requires.
As ACL's (Access control lists) are done on the actual resources (files, printers etc), these access permissions allow the user to make use of the resources. Hence any process with the User's ID would also have acess to these resources.
To apply Principle of Least Privaledge to the process we would have to remove the right for this process to acess every single resource before run time (this is the difficult part). That would envlove looking for every single resource the process has access to (VERY HARD TO DO with ACL) and then modifying every single resource (also time consuming).
The better way to do it would be with capabilites.
85.
What is a trusted computing base?
The trusted computing bases is the
set of component of the system that must be trusted to behave correctly in
order for the security policy to be enforced.
The entire OS is part of the trusted computing base.
Ideally, trusted computing bases are small, understandable, have verifyable models that the process must operate through.
The entire OS is part of the trusted computing base.
Ideally, trusted computing bases are small, understandable, have verifyable models that the process must operate through.
86.
The Bell-La Padula Multilevel security policy is a security policy designed to
keep secret information secret. Describe the model including the properties
that must be guaranteed for secrecy to be preserved.
The Bell-La Padula model separates
the system into different levels of secrecy (both for processes and objects).
Any level can read information from the same or lower secrecy levels, and write
the the same or higher secrecy levels. Secrecy is preserved by denying low
secrecy levels access to info from higher levels.
87.
What is a covert channel?
a covert channel is an unauthorised
communications channel that can be created in a system by observing and
manipulating measurable performance characteristics of the system. e.g.
encoding data through bus locking latencies, e.g. by representing logic 1 with
a read (inducing latency) and 0 with no read (bringing no latency).
A covert channel is an unauthorised and implicit
communication channel created via influencing and observing shared resources in
the system.
Any shared system resource (CPU, disk seeks) can be used for signalling to send secrets. As a process with a secret alternates between busy and sleeping, a process who wishes to obtain a secret can monitor how fast it is does this to obtain the secret.
Any shared system resource (CPU, disk seeks) can be used for signalling to send secrets. As a process with a secret alternates between busy and sleeping, a process who wishes to obtain a secret can monitor how fast it is does this to obtain the secret.
88.
Which of RAID 1 or RAID 5 would you use in the following scenarios and why:
a)
A transaction database that performs many thousands of updates per second.
b)
A web server that serves almost entirely static web content.
a) A transaction database that performs many thousands of
updates per second.
When using a database the prefered raid to use would be RAID 1. The reason for this is that the write and update performace of RAID 1 is better than that of RAID 5.
b) A web server that serves almost entirely static web content.
RAID 5 would be more beneficial here, as the data can be accessed fast. As the pages are static, and assuming no backend database there are no real writes to the disk, this means that the update performance of RAID 5 is not an issue, and you might as well save on the number of disks and use raid 5.
When using a database the prefered raid to use would be RAID 1. The reason for this is that the write and update performace of RAID 1 is better than that of RAID 5.
b) A web server that serves almost entirely static web content.
RAID 5 would be more beneficial here, as the data can be accessed fast. As the pages are static, and assuming no backend database there are no real writes to the disk, this means that the update performance of RAID 5 is not an issue, and you might as well save on the number of disks and use raid 5.
89.
Compare RAID 0, RAID 1, and RAID 5 in terms of performance improvement, ability
to withstand failure, and space overhead require to implement the particular
RAID level.
corrected: raid1 write performance
> raid 5 write performance
RAID 0, or striping, improves performance of reads and writes, if the blocks being read or written are stored on different physical volumes. Failure threshold is worse than a single disk; logical volume failure is the probability of any of the physical volumes failing. there is no space overhead, the logical volume size is the sum of the physical volume sizes.
RAID 1, or mirroring, improves read performance significantly, as any read can be sent to any disk. write performance is same, as any write must be performed on both disks (but in parallel). failure threshold is better than single disks (can tolerate a single disk failure), space overhead is poor, doubles the number of disks..
RAID 5, distributed block parity?? raid5, like raid0, improves read performace if requests are to different disks. write performance is worse than raid 0, worse than single disk and worse than raid 1. each write requires: a write to the block, then reading the parity to re-compute parity, then writing to the parity block. failure threshold is better than single disk and raid 0, can tolerate a single disk failure.
RAID 0, or striping, improves performance of reads and writes, if the blocks being read or written are stored on different physical volumes. Failure threshold is worse than a single disk; logical volume failure is the probability of any of the physical volumes failing. there is no space overhead, the logical volume size is the sum of the physical volume sizes.
RAID 1, or mirroring, improves read performance significantly, as any read can be sent to any disk. write performance is same, as any write must be performed on both disks (but in parallel). failure threshold is better than single disks (can tolerate a single disk failure), space overhead is poor, doubles the number of disks..
RAID 5, distributed block parity?? raid5, like raid0, improves read performace if requests are to different disks. write performance is worse than raid 0, worse than single disk and worse than raid 1. each write requires: a write to the block, then reading the parity to re-compute parity, then writing to the parity block. failure threshold is better than single disk and raid 0, can tolerate a single disk failure.
90.
Why is it generally correct to favour I/O bound processes over CPU-bound
processes?
i/o is many orders of magnitude
slower than cpu. therefore favouring i/o bound process won't actually give them
more execution time than a cpu bound process, because they're just going to
block again on the next i/o transaction. favouring them gives them a chance to
operate when the i/o requests appear (system is more responsive, and I/O
utilisation is higher as requests are re-issued faster); it also decreases the
probability of packet loss, as the i/o buffers are given more chances to be
read.
91.
What is the difference between preemptive scheduling and non-preemptive
scheduling? What is the issue with the latter?
preemptive scheduling menas that
processes are context switched at regular time intervals, by the kernel. non
pre-emptive scheduling, means a process returns control to other processes upon
termination, or by yielding (cooperative multitasking). fair share of cpu-time
in a non-preemptive system requires that all processes are yielding at similar
time intervals. a single process can monopolise cpu time by not yielding.
92.
Given an initial set of batch jobs, show that shortest job first minimises average
turn-around time.
turnaround time is completion time -
submission time.
also: wait time + running time
average turnaround time = sum of turnaround times / number of processes
= ((completion time 1 - submission1) + (completion time 2 - submission time 2) .... (ct n - st n)) / n
assume submission time = 0 for all
= ((task1) + (task1 + task2) + (task1 + task2 + task3) ... sum(task1..taskn)) / n
= (n task1 + n-1 task2 + n-2 task3 .... + 1 taskn) / n
by ordering tasks from lowest to highest execution time, the coefficients next to higher n are smaller, reducing the overall expression.
also: wait time + running time
average turnaround time = sum of turnaround times / number of processes
= ((completion time 1 - submission1) + (completion time 2 - submission time 2) .... (ct n - st n)) / n
assume submission time = 0 for all
= ((task1) + (task1 + task2) + (task1 + task2 + task3) ... sum(task1..taskn)) / n
= (n task1 + n-1 task2 + n-2 task3 .... + 1 taskn) / n
by ordering tasks from lowest to highest execution time, the coefficients next to higher n are smaller, reducing the overall expression.
assume for the following processes thse execution times:
* A: a
* B: b
* C: c
* D: d
Process A finishes at time a, B finishes at time a+b, C at a+b+c and so on
ave turn around time is then: (4a+3b+2c+d)/4
* it can be seen from above equation that a contributes the most to the average turnaround time, also since a is the shortest time therefore SJF minimises turn around time
* A: a
* B: b
* C: c
* D: d
Process A finishes at time a, B finishes at time a+b, C at a+b+c and so on
ave turn around time is then: (4a+3b+2c+d)/4
* it can be seen from above equation that a contributes the most to the average turnaround time, also since a is the shortest time therefore SJF minimises turn around time
93.
Describe round robin scheduling. What is the parameter associated with the
scheduler? What is the issue in chosing the parameter?
Round robin scheduling runs each
process for timeslice t, then preempts it, puts it on the end of a ready queue.
then runs the next process for timeslice t.
If t is too large, it is unresponsive. if t is too small, much time is wasted in context switching overhead.
If t is too large, it is unresponsive. if t is too small, much time is wasted in context switching overhead.
94.
The traditional UNIX scheduler is a priority-based round robin scheduler (also
called a multi-level round robin schduler). How does the scheduler go about
favouring I/O bound jobs over long-running CPU-bound jobs?'
It uses multiple ready queues of each priority. priorities
are gradually increased over time to prevent starvation of low priority
processes.They are increased by boosting the priority based on the amount of
CPU consumed. I/O bound jobs are indirectly favoured as they consume less
CPU.
.
.
95.
In a lottery scheduler with 40 tickets. How how I distribute the tickets
amongst 4 processes (A, B, C, D) such that each process gets 10%, 5%, 60%, and
25% respectively?
A gets 4, B gets 2, C gets 24, D
gets 10.
96.
What is the problem that a fair share scheduler strives to address?
Fair share scheduling tries to
allocate CPU time fairly across users, rather than processes, so having more
processes doesn't give a larger proprortion of CPU time.
97.
In a real-time system with a periodic task set,, how are priorities assigned to
each of the periodic tasks?
In a rate monotonic scheduler,
priorities are assigned based on the period of each task.
In an earliest deadline first scheduler, priorities are assigned dynamically based on the deadlines of each task.
+ Rate monotonic : the shorter period, the higher priority the process is
+ EDF : the earlier deadline, the higher priority.
In an earliest deadline first scheduler, priorities are assigned dynamically based on the deadlines of each task.
+ Rate monotonic : the shorter period, the higher priority the process is
+ EDF : the earlier deadline, the higher priority.
98.
What is an EDF scheduler? What is its advantage over a rate monotic scheduler?
EDF is guaranteed to produce a
feasible schedule if CPU utilisation is <= 100%
RMS only provides such a guarantee if the utilisation is less than that specified in the formula in the lecture notes, which is significantly less than 100%
RMS only provides such a guarantee if the utilisation is less than that specified in the formula in the lecture notes, which is significantly less than 100%
99.
Describe why the use of spinlocks might be more appropriate than blocking locks
on a multiprocessor when compared to a uniprocessor. Is there a trade-off
between spinning and blocking on a multiprocessor? Discuss.
Spinlocking on a uniprocessor is
useless, as another thread on the same processor needs to release it, so
blocking asap is desirable.
On a multiprocessor, the thread holding the lock may be presently active on another processor, and it could release the lock at any time. On a multiprocessor, spin-locking can be worthwhile if the average time spent spinning is less than the average overheads of context switch away from, and back to, the lock requestor.
On a multiprocessor, the thread holding the lock may be presently active on another processor, and it could release the lock at any time. On a multiprocessor, spin-locking can be worthwhile if the average time spent spinning is less than the average overheads of context switch away from, and back to, the lock requestor.
100.
Is a single ready queue on a multiprocessor a good idea? Why?
No, as it is a shared resource,
which introduces lock contention when processors are trying to schedule work,
as they must all wait on a single lock on the ready queue to determine who to
schedule next.
101.
What is thread afinity. Why might it improve performance?
Thread affinity is where a thread
has a preferential processor for scheduling on a multiprocessor machine. This
increases the probability of being scheduled on the processor previously
scheduled on, which in turn increases the probability of being scheduled onto a
processor that has a hot cache. Hot cache is good, it means less cache misses
and higher performance.
No comments:
Post a Comment