Reading...
Play button
Play button
Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
105 Cards in this Set
- Front
- Back
|
Describe the Process Model.
|
All run-able software is organized into a number of sequential processes.
A process is an instance of an executing program, including the program counter, registers, and variables. A process is a way to group related resources together. It has an address space with program, open files, as well as resources. It has a thread of execution having a program counter that tracks what to do next and registers and a stack. These threads can be regarded as entities scheduled on the CPU. Since the CPU switches from process to process must not be programmed with build-in assumptions about timing. If a program is running twice it counts as two process. |
|
|
What are the four events that cause processes to be created?
|
System initialization: When a system is booted usually several process are started, some interact with humans, some are background processes (daemons).
Execution of a process creation system call: a running process can issue system calls to create process helping him (fetching data from a disk and processing data can be done by two processes) A user request to create a new job like starting a program. Initiation of a batch job by the OS. |
|
|
Give an example of Process Creation in UNIX.
|
There is only one system call to create a process (fork). It creates an exact clone, the two processes have the same memory image, open files,..) But theses are physically copies. After that the execve() (execute process) system call transforms the child into a new process (with different memory and program).
|
|
|
Give an example of Process Creation in Windows.
|
Windows has a function CreateProcess that creates a new process and loads the new program. The call has 10 parameters.
|
|
|
What are the four exit conditions of a process termination?
|
Normal exit because the work is finished. This is done by a system call (exit in UNIX)
Error Exit, the compiler is asked to compile a non-exiting program. Then a pop-up window might be displayed. Fatal Error, for ex. division by 0. Killed by another process, for ex. the kill call in UNIX. |
|
|
What is a process tree?
|
A process hierarchy where processes can have children, the children can have children, ....
|
|
|
What are the differences in process hierarchy between Windows and UNIX?
|
UNIX: a process and all its children form a group. When a user sends a signal from the keyboard the signal is delivered to all processes of the group. They can individually decide what to do with the signal.
Windows has no process hierarchy. |
|
|
Explain UNIX init.
|
When UNIX is started a process init is present in the boot image. When it starts it reads a file telling it how many terminals are active. Then it forks of one new process per terminal. Their processes wait for someone to log in. If a login is successful the login process executes a shell accepting commands. These commands can create new processes belonging to the same tree with init at its root.
|
|
|
What are the process states?
|
Running: uses the CPU at the moment
Ready: job waits for the CPU Blocked: job is blocked and it waits for an input |
|
|
How does the OS maintain the states of the process
|
The OS maintains a process table with one entry per process.
The entry contains the state of the process, program counter, register, all the information necessary to run the process after being blocked or stopped |
|
|
How is the illusion of multiple sequential processes maintained?
|
Each I/O class has a fixed location in main memory called the interrupt vector. It contains the address of the interrupt service procedure.
Suppose a user process is running when a disk interrupt happens. The interrupt hardware pushes PC, PSW, register, onto the current stack. The computer jumps to the address specified in the interrupt vector. The information pushed onto the stack by the interrupt is removed and the stack pointer is set to a temporary stack position. A C program is called to deal with the interrupt. The scheduler decides which job should run next. Registers and memory map is loaded for the new process. |
|
|
What is the difference between Threads and Process?
|
Threads work in the same address space whereas processes have their own address space.
|
|
|
Why do we use threads?
|
enables "parallel" processes - sharing memory.
easier and faster to create, compared to processes. in case with extensive I/O and computing, having threads allows computer and I/O to overlap. great in systems with multiple CPUs. |
|
|
Explain how threads work for a work processor.
|
A word processor usually displays the document in the same way it will appear on a printed page. Changing one word can results in a change of every page in the document.
Having one thread that interacts with the user and one that formats the document helps. A third thread could now do regular security copies on the disk. |
|
|
What is an alternative to parallelism via Finite-State machine?
|
For ex. Web application
When a request comes in it is examined by "the only thread". If it can not be satisfied by the cache a non-blocking disk operation is called. The information about the request is stored in a table and the next event is processed. This might be a new request or a reply from a disk. If it is a reply from a disk the reply has to be processed in the form of an interrupt or signal. |
|
|
What components/features are private to a thread? Which ones are shared by threads?
|
Private: Program counter, register, stack and state
Shared: Address space, global variables, open files, child process, alarms, signals No protection between threads. |
|
|
Describe what happens when a process creates a new thread.
|
Processes usually start with one thread. The thread has the ability to create new threads with create_thread. The call specifies the name of the new thread. It does not need any memory. Threads can have child threads. When a thread is finished it calls thread_exit. Or threads can wait for some specific threads by calling thread_joint.
Another command is thread_yield where a thread allows a thread to voluntarily give up the CPU, threads wait for another thread to finish. |
|
|
What are Pthreads and what are some of their functions?
|
POSIX threads defines a set of C programming language types, functions and constants. Pthread procedures include thread management, mutexes, conditions variables, and synchonize.
|
|
|
What does pthread_create do?
|
creates a new thread and the id of the thread is returned as function value. The fall is similar to fork.
|
|
|
What does pthread_exit do?
|
stops the thread and releases the stack.
|
|
|
What does pthread_join do?
|
waits for another thread to finish.
|
|
|
What does pthread_yield do?
|
allows another thread to run.
|
|
|
What does pthread_attr_init do?
|
creates teh attributes structure associated with a thread and initializes it to the default values. These values can then be changed.
|
|
|
What does pthread_attr_destroy do?
|
removes all attributes
|
|
|
What are the two ways to implement a thread package?
|
In the user space or in the kernel
|
|
|
Explain the implementation of threads in the user space.
|
Kernel knows nothing about threads. Such a packet can be implemented over an OS without threads. Threads run on top of a run time system, which is a collection of procedures that manage threads. Each process has own thread table to keep track of the threads. The runtime system has to do the scheduling.
|
|
|
What are the problems of blocking system calls?
|
If a thread makes a blocking system call then the process will be blocked. Hence, the parallelism is gone. Here one would need non-blocking system calls or other fixes.
|
|
|
What are the advantages and disadvantages of implementing threads in user space?
|
Advantage: Fast if the machine has instructions to save register. Processes can have their own scheduling system.
Disadvantage: Scheduler has to work without clock interrupts, making it impossible to schedule threads in round robin fashion. Unless a thread enters the run time system of its free will the scheduler will get no chance. Parallelism is gone if a thread makes a blocking system call. |
|
|
Explain the implementation of threads in the Kernel.
|
The Kernel has the thread table and keeps track of all threads. Calls that might block a thread are implemented as system calls which is more expensive than run time system procedures. The scheduler can then schedule a thread from the same or from another process.
|
|
|
What is the advantage of implementing threads in the kernel? Disadvantages?
|
Advantage: There are no problems with blocking system calls. The kernel can take the CPU away.
Disadvantage: The cost of system calls is much higher. |
|
|
What are the 3 main issues with interprocess communication?
|
How can a process pass information to another one?
How to make sure that the processes do not get in each other's way? How to enforce proper sequencing? |
|
|
What are race conditions?
|
a race condition may occur if commands to read and write a large amount of data are received at almost the same instant, and the machine attempts to overwrite some or all of the old data while that old data is still being read. The result may be one or more of the following: a computer crash, an "illegal operation," notification and shutdown of the program, errors reading the old data, or errors writing the new data.
|
|
|
Explain race condition with the printer spooler example.
|
When a process wants to print it enters the file name in a special spooler directory. The process printer daemon periodically checks if there are many files to be printed. If yes it removes the name and prints the file. Usually the spooler directory has a large number of slots, each one can hold a file name. There are two shared variables out pointing to the next file to be printed and in pointing to the next available slot. The variables are available to all processes. Now Process A and Process B decide more or less to print at the same time. A could read in (ex. in = 7) and store the value in a local variable. Then the CPU decides that now process B should get the CPU. B stores the file name it wants to print in slot 7. At one point the CPU decides that it is again A's turn and A overwrites the file name of B. B will now wait forever.
|
|
|
What is the solution to race conditions?
|
prohibit more than one process from reading and writing the shared data at the same time: Mutual exclusion.
|
|
|
What is a critical region?
|
part of a process where the shared memory is accessed or other things are done which result in races.
|
|
|
What 4 conditions are needed to avoid races?
|
No two processes may be simultaneously inside their critical regions.
No assumptions may be made about speeds or the number of CPU's. No process running outside its critical region may block other processes. No process should have to wait forever to enter its critical region. |
|
|
How do process A and process B enter the critical region?
|
process A enters the critical regions at time T1. At T2 > T1 process B attempts to enter its critical regions but it fails because of A. B is temporarily suspended until time T3, when A leaves its critical regions. Now B can enter its critical region.
|
|
|
What are the disadvantage of disabling interrupts?
|
this does not help if a system has multiple CPUs.
User processes should never be able to stop interrupts. For ex, what happens if a process never allows interrupts again? or the process has problems and goes into an endless loop. |
|
|
Describe the critical region with lock variables.
|
A lock variable can have the values 0 and 1. Lock = 0 means no process is in a critical region, and lock = 1 means a process is in its critical region. A process that wants to enter its critical region is only allowed to do so if lock = 0.
|
|
|
What are the disadvantage of using the lock variable in the critical region?
|
A process could read lock and then be disabled because there is no protection on the lock.
|
|
|
Describe the critical region with variable turn and lock.
|
Turn = 0 means that process A can go into its critical region. After leaving the critical region it sets turn to 1.
Lock = 1 means that process B can go into its critical region. After leaving the critical region it sets turn to 0. Hence only one process at a time can be in critical region. |
|
|
What are the disadvantages of using the lock and turn variable in the critical region?
|
The processes have to take turns. If process A left the critical region it can only go into the critical region again if B was in its critical region. This might never happen and the processes might have different speeds. A process can be blocked by a process that is not in its critical region.
|
|
|
What is Peterson's solution?
|
Before entering its critical region each process calls enter_region with its own process number as parameter. This will cause it to wait if necessary. After being finished with the critical region it calls leave_region.
|
|
|
What is the TSL instruction?
|
TSL stands for "test and set lock." It reads the contents of the memory word lock into the register and stores a nonzero value at the memory address lock. The operation is indivisible. It locks the memory bus to prohibit other CPUs from accessing memory until it is done.
|
|
|
What are the disadvantages of busy waiting?
|
a process that can not enter the critical region sits in a loop waiting until it is allowed to do so, it wastes CPU time and can have unexpected effects called priority inversion.
|
|
|
Explain why busy waiting doesn't work?
|
Assume a computer has two process H and L. H has high priority and L has low priority. H runs whenever it is in the ready state. At a certain moment, with L in its critical region, H becomes ready to run. Hence the CPU schedules H. If H wants to enter the critical region it starts busy waiting. Hence, L never gets the CPU. As a result, both processes will be blocked forever.
|
|
|
What do the Consumer-Producer do?
|
Two processes share a common fixed-size buffer of size N. A variable count counts the number of items in the buffer. The producer puts in some information and the consumer consumes it. The consumer can not put an item into a full buffer and the consumer can not read items out of an empty buffer. The consumer goes to sleep when the buffer is empty to be awakened when the producer puts something into the buffer. The producer goes to sleep if the buffer is full and will be awakened if the consumer deleted one item.
|
|
|
What is the problem with Consumer-Producer?
|
Assume the buffer is empty and the consumer has just read count which is 0. The scheduler stop the consumer. The producer inserts an item and increments count. Seeing that count was 0 it calls wakeup. The consumer is not asleep and the wakeup is lost.
|
|
|
What are semaphores?
|
an integer variable that counts the number of wakeups. There are two operations for sempahores, up and down.
|
|
|
What does the down operation of the semaphore do?
|
Checks if the semaphore is > 0. If so it decrements the value and continues. If it is 0 the process is put to sleep.
|
|
|
What does the up operation of the semaphore do?
|
Increments the value of the semaphore. If one or more processes were sleeping on the semaphore (unable to do a down operation) one of them is allowed to complete the down. The value of the semaphore will still be 0 after that.
|
|
|
What are binary semaphores?
|
These semaphores are initialized with 1 and used by two or more processes to ensure that only one of them can enter its critical region. Each process does a down just before entering the critical region and an up after leaving it. This ensures mutual exclusion.
|
|
|
Describe Producer-Consumer with three semaphores.
|
3 semaphores: full, empty, and mutex.
Empty counts the number of empty slots. Initially we have empty = N. Full counts the number of used slots. Initially full = 0. Mutex makes sure the producer and consumer do not access the buffer at the same time. initially mutex = 1. |
|
|
What is a deadlock?
|
When the buffer is full and the producer calls down on mutex. Then the consumer would be blocked from emptying the buffer.
|
|
|
What are the three solutions to a deadlock?
|
Semaphores can be stored in the kernel and accessed by system calls.
Many OS allow processes to share some of their memory space. In the worst case a shared file has to be used. |
|
|
What are mutexes used for?
|
Simplified version of semaphores if counting is not needed. They manage only mutual exclusion. 0 means unlocked and every other value locked
|
|
|
What is mutex_lock?
|
Used if a process wants to enter the critical region. If the mutex is unlocked the call succeeds and the calling thread is free to enter the region.
|
|
|
What is mutex_unlock?
|
Called by the thread after leaving the critical region. If multiple threads are blocked on the mutex one is chosen at random and unblocked.
|
|
|
What are monitors?
|
Monitors are a language concept that makes it easier to write correct programs. It is a collection of procedures, variables and data structures that are all grouped together in special kind of module or packet.
|
|
|
True or False: Processes can access directly the monitor's internal data from procedures declared outside of the monitor
|
False. Processes might call all the procedures in a monitor whenever they want though. Only one process can be active in a monitor at any point of time.
|
|
|
How many process can be active in a monitor at any point of time?
|
one
|
|
|
What component implements mutual exclusion on monitor entries?
|
It is up to the compiler. A common way is to use a mutex or binary semaphore. Typically the first instructions of monitor procedures will check if an other process is currently active in the monitor. If so calling process will be suspended.
|
|
|
How do condition variables assist monitors?
|
Producer-consumer ex: assume monitor procedure cannot continue because the buffer is full (empty). The procedure does a wait on some condition variable full(empty). This causes the calling process to be blocked. Now another process can enter the monitor. The consumer/producer can wake up the other process. They do a signal on the condition variable. If a signal is done on a condition variable on which several processes are waiting, only one of them, determined by the scheduler, is revived. It has to be decided if the process that is responsible for the signal remains in the monitor or the one that got the signal will be allowed to enter the monitor.
|
|
|
How does message passing occur?
|
Library procedure send(destination, &mesg) sends the message to the destination.
Library procedure receive(source, &mesg) receives the message send by the source. If no message is available the receiver can block until one arrives or return with an error code. |
|
|
Describe Consumer Producer with message passing.
|
The consumer starts out with sending N empty messages to the producer. The producer takes an empty message and sends back a full one. The consumer can read a full message and send an empty one back to the producer. If all messages are full the producer will be blocked. If all messages are empty the consumer will be blocked.
|
|
|
What component decides which jobs the CPU runs?
|
The scheduler
|
|
|
Why is switching processes expensive?
|
one or more system calls has to be performed.
the whole memory map has to be exchanged the whole memory cache is invalidated. |
|
|
What activities do process alternate?
|
bursts of computation
with disk I/O requests |
|
|
What are compute-bound processes?
|
Processes with long CPU bursts.
|
|
|
What are I/O-bound processes?
|
processes that have short CPU bursts.
|
|
|
What is the consequence of the modern CPU getting faster and faster?
|
the fraction of I/O bound jobs gets larger. Disk access does not improve that fast.
|
|
|
What is a good scheduling rule?
|
For I/O bound jobs it is a good strategy to schedule a job as fast as possible when it wants to run. Most probably, it will only run for a short time and then wait again.
Compute-bound processes have to be scheduled fair. |
|
|
When are scheduling decisions needed?
|
a new process is created
a process exits a process blocks/un-blocks an I/O interrupts occurs |
|
|
What is a non-preemptive scheduling algorithm?
|
picks a process to run and lets it run until it blocks or exits.
|
|
|
What is a preemptive scheduling algorithm?
|
requires a clock interrupt to give the CPU control back to the scheduler.
|
|
|
Why is preemption not necessary in real-time systems?
|
preemption is often not necessary because the processes know that they may not run for long periods of time. Often the jobs are very quick. Real time systems run only programs that are intended to further the application at hand.
|
|
|
Describe the first come first serve batch system.
|
All jobs are stored in a queue. The first job out of the queue is scheduled. There is no preemption. A job that arrives at the system is put on the end of the queue. When the running job blocks, the first job of the queue is scheduled and the blocked job is put at the end of the queue.
|
|
|
What are the advantages and disadvantages of the first come first serve batch system?
|
advantages: easy to program, easy to understand, fair
disadvantages: very bad for a mixture of compute-bound and I/O-bound processes. |
|
|
Describe the shortest job first batch system.
|
Assume that we have an estimation how long jobs will take. The turnaround time of a job is the time between entering the system and leaving it. The scheduling rule is to run the shortest job first. The strategy has no preemption.
|
|
|
What are the advantages and disadvantages of shortest job first batch system?
|
Advantages: The rule minimizes the average turnaround time if all jobs arrive at the same time. Easy to understand
Disadvantages: long jobs wait for ages. Fairness? |
|
|
Describe the shortest remaining time batch system.
|
Assume that we have an estimation of how long jobs will take. The scheduling rule is to run the shortest job first. The strategy has preemption, if a shorter job arrives the new job is scheduled.
|
|
|
What are the advantages and disadvantages of shortest remaining time batch system?
|
Advantages: The rule minimizes the average turnaround time. Easy to understand.
Disadvantages: long jobs wait for ages. Fairness? |
|
|
What are other rules of the batch system?
|
longest in system
longest job first |
|
|
Describe the round robin interactive system.
|
The processes are hold in a list. The first process of the list is assigned a quantum during which it can run. If the process is still running at the quantum the CPU is preempted and given to the next job in the list. The preempted job is put at the end of the list. Usually, if a process blocks it will be suspended too.
|
|
|
What are the advantages and disadvantages of round robin interactive systems?
|
advantages: fair, good performance if the quantum time is chosen properly, easy to understand
disadvantages: bad performance if the quantum time is not chosen properly |
|
|
Describe the priority scheduling interactive system.
|
Assume that there are important and not important processes. Each process is assigned a priority and the runnable job with the highest priority is allowed to run. To prevent jobs from running forever, the CPU might decrease the priority of the running job by every clock tick. If the priority now is below that of another job, this job will be scheduled. Each process might have a maximum time quantum it is allowed to run. Priorities can be assigned statically or dynamically.
|
|
|
Describe the priority scheduling with multiple queues.
|
Processes are grouped into priority classes. Priority scheduling is used among the classes and round robin scheduling within each class. Whenever there are jobs in the highest priority class schedule these jobs in a round robin fashion. if not schedule the next priority class, and so on. Again, priorities might be adjusted or other rules might be used to prevent "starving" of jobs with a low priority.
|
|
|
Give an example of priority scheduling with multiple queses using timesharing system.
|
Time sharing system that can hold only one process in memory. Large quanta save time for context switches, but they are bad for interactive systems. There are k priority classes. Jobs in Class k are run for 1 quanta. Jobs in class i are run for 2^(k-i) quanta. Whenever a job used up all quanta allocated to it, it is moved down one class. Classes with high priority are preferred to classes with low priority. Hence, jobs are scheduled less and less, saving time for short interactive jobs. For a job that needs 100 quanta only 7 swaps are needed (1+2+4+8+18+32+64)
|
|
|
Give an example of priority scheduling with multiple queses using XDS 940.
|
There are 4 priority classes, called terminal, I/O, short quantum, long quantum. Processes that were waiting for a terminal input and awakened go into class terminal. Processes that were waiting for a disk block that became ready went into the second class. Processes that were still running when the first quantum ran out were moved to Class 3. Jobs that used up their quantum too many times were moved into Class 4.
|
|
|
Describe the Shortest Process Next Interactive Systems.
|
Try to predict the runtime of a new job based on the runtime of previous jobs. Assume the estimated time for some terminal is T0. Let T1 be its next run. Then an estimate would be αT0 + (1 - α)(T1). α determines how fast old runtimes are neglected
|
|
|
Describe how the OS gives guarantees to the users on scheduling.
|
Each of n users gets a fraction of 1/n of the CPU time. The CPU calculates for every job the fraction of time that job got and compares it with the required time. A ration of 0.5 means the job got only half of its time. THe scheduler schedules the process with the lowest ratio until its ratio has moved above the second highest ratio.
|
|
|
Explain the lottery scheduling.
|
Each process holds a certain number of tickets. The scheduler randomly draws a ticket and schedules the owner of a ticket for, say 20 ms, then it holds a new lottery. This is very flexible. An importnat job can get many tickets, unimportant jobs can get less. New jobs get tickets and can be scheduled immediately. Cooperating processes might exchange tickets. Every user could get a fixed amount of tickets. The number of tickets can depend on the job requirements like frames per second for video servers.
|
|
|
What are some examples of scheduling in real time systems?
|
compact disc player, autopilot, hospital intensive care unit
|
|
|
How is real time behavior achieved?
|
Dividing the program into a number of processes. The behavior of the processes is predictable and known in advance. The processes are usually short lived, under one second. Jobs can be preemptable or not preemptable. The job of teh scheduler is to schedule the jobs so that the deadlines are met. Jobs can be periodic and aperiodic.
|
|
|
What are the types of algorithms available to real time systems scheduling?
|
static or dynamic
|
|
|
What is rate monitor scheduling?
|
A classical scheduling for preemptable and periodic processes. It can be used for processes where each periodic process must complete within its period, no process is dependent on other processes, any nonperiodic processes have no deadlines, and process preemption occurs instantaneously and with no overhead.
|
|
|
How does the rate monitor scheduling algorithm work?
|
It assigns each process a fixed priority equal to the frequency. Hence, A has priority 33, B has priority 25 and C has 20. The scheduler always runs the highest priority ready process. If a process becomes ready that has a higher priority than the running job, the running job will be preempted.
|
|
|
Describe the earliest deadline first real time systems.
|
A dynamic algorithm that does not require periodic jobs or the same runtime per job. The CPU holds a list of all ready jobs sorted on deadline. The scheduler schedules the job with the closest deadline. New jobs are inserted into the list. If the deadline is earlier than the deadline of the running job , the running job is preempted.
|
|
|
What are the difference between rate monitor scheduling and earliest deadline first?
|
RMS is guaranteed to work for periodic processes if the usage is at most m(2^(1/m) - 1). EDF always works but the complexity is higher.
|
|
|
Describe thread scheduling on the user level.
|
Kernel is not aware that threads exist. It only schedules processes. The processes decide which thread should run. This could be one thread or several threads. The run time system can have a scheduler but there is no clock interrupt. Mostly round robin or priority scheduling is used.
|
|
|
Describe thread scheduling on the kernel level.
|
The kernel schedules the threads. It can take into account to which process a thread belongs but it is not necessary.
|
|
|
What is the dining philosophers problem?
|
Five philosophers are sitting around a round table. each of them has a plate of spaghetti and there is a fork between every pair of plates. Every philosopher needs two forks. Each philosopher can be in one of two states: eating and thinking. When a philosopher gets hungry he tries to get the left and the right fork, in either order. If they are finished with eating they put down the fork.
|
|
|
What are the solutions to the philosophers problem?
|
First take the left fork, then the right fork. If the right fork is no available put the left one down again.
Protect the five statements with a mutex variable |
|
|
What is the reader-writer problem?
|
Reader and writer processes want to access a database. Several reader can access the database at the same time but only one writer.
|
|
|
What is a solution to the reader-writer problem?
|
The writer has to wait until there is no active reader.
When a reader arrives and a writer is waiting, the reader is suspended behind the writer instead of being admitted immediately. |
