Define First-Come, First-Served
scheduling algorithm where process that requests the CPU first gets CPU allocation first.
| Term | Definition |
|---|---|
Define First-Come, First-Served | scheduling algorithm where process that requests the CPU first gets CPU allocation first. |
First-Come, First-Served Pros and Cons | (+) simple, low overhead (processing time), good for batch jobs
(-) short jobs can get stuck behind long ones |
Define Round-Robin | FCFS scheduling algorithm with preemption. Each process is executed for a after a fixed time (quantum) |
Round-Robin Pros and Cons | (+) Better interactivity (low average scheduling latency)
(-) performance dependent on quantum size |
Define Shortest Job First (SJF)/Shorted Retaining Time First (SRTF) | shorted job (or shortest remaining job) first |
SJF/STRF Pros and Cons | (+) optimal average waiting time
(-) need to know the future, long jobs can be starved by short jobs |
Define Timesharing (batch, multiprogramming) | allows for multiple interactive users to access a computer system through a terminal at the same time
OS Goal: optimize response time |
Timer and OS scheduler tick | OS programs a timer to generate an interrupt at every 10 ms |
OS Structure | user/kernel mode, system call, monolithic kernel/microkernel |
What is user/kernel mode? | user: restricted mode where applications run
kernel: privileged instructions where computer accesses hardware resources |
what is a system call? | Programs ask OS services (privileged) |
what is a monolithic kernel? | Implements CPU scheduling, memory management, filesystems, and other OS modules all in a single big chunk |
pros and cons of monolithic kernel | (+) overhead is low
(+) data sharing among modules is easy
(-) too big (device drivers)
(-) a bug in one part of the kernel can crash the entire system! |
What is in a process address space? | text: code
data: global variables
heap: dynamically allocated memory
stack: temporary data, grow at each function call |
what is in a process state? | running: instructions being executed
waiting: process waiting for an event
ready: process waiting to be assigned to a processor |
What is the output of this code:
int count = 0;
int main() {
int pid = fork();
if (pid == 0){
count++; printf("Child: %d\n", count);
} else{
wait(NULL);
count++;
printf("Parent: %d\n", count);
}
count++;
printf("Main: %d\n", count); return 0;
} | Child: 1
Main: 2
Parent: 1
Main: 2 |
what is IPC? | Inter-process communication;
allows for processes to communicate with each other |
What are 2 types of IPC mentioned in class? | shared memory: threads
message passing: pipes, signals |
what is a thread? | path of execution within a process. |
thread vs process | thread: run in a shared memory space
process: run in separate memory spaces |
what are benefits of threads over processes? | (+) responsiveness
(+) faster context switch
(+) effective utilization of multiprocessor system
(+) resource sharing
(+) communication is easy! |
how do threads communicate? | through shared memory (they share a common memory space)
through events: wait(), notify(),
synchronization: locks, semaphores |
pros and cons of user threads | (+)faster to create/manage,
(+)implemented with thread library,
(+)generic and can run on any OS,
(-)multi-thread apps cannot handle multiprocessing |
pros and cons of kernel threads | (-) slow to create/manage
(+) OS supports creation of kernel threads
(-) kernel thread specific to the OS
(+) can be multi-threaded |
multi-threads vs multi-processes | multi-threads:
(-) protection
(+) performance
multi-processes:
(+) performance
(-) protection |
What is (process) synchronization? | organizing execution of processes in a way that no two processes can have access to the same shared data and resources |
what is a race condition? | a condition where several processes try to access resources and modify shared data at the same time -- the outcome depends on the order of execution that can lead to data inconsistency |
what is the test&set synchronization instruction? | int TestAndSet(int *lock) {
int ret = *lock;
*lock = 1;
return ret; } |
what is spinlock implementation of test&set? | void init_lock(int *lock) {
*lock = 0;
}
void lock(int *lock) {
while (TestAndSet(lock));
}
void unlock(int *lock) {
*lock = 0;
} |
what is the bounded buffer problem? | problem on concurrent access to a shared resource:
producers block if the buffer is full,
consumers block if the buffer is empty. |
what are the 4 MUST conditions for deadlocks? | 1) mutual exclusion: one process at a time can use resource
2) no preemption: release must be voluntary
3) hold and wait: process must be holding at least one resource & wait to acquire additional resources held by other processes
4) circular wait: A waits B, B waits C, C waits A |
starvation vs deadlock | starvation: waiting for a resource that is continuously given to other processes
deadlock: resource not given due to it being held by a blocked process |
what is Mutex? | synchronizes access to a resource; a locking mechanism that makes sure only one thread can acquire the Mutex at a time and enter the critical section. |
what is a semaphore? | a signaling mechanism that uses two atomic operations, wait(arg) and signal(arg) to solve critical section |
what hardware support is needed to implement a time sharing CPU scheduler? | timer and interrupt |
T/F each thread has its own address space and stack | False, all threads in a process share the same address space |
T/F synchronization is easier on message passing | True |
T/F a spinlock is very effective to protect a long critical section | True |
Implement Test& set here:
void spinlock_lock(int *lock)
{
While (_________________);
}
void spinlock_unlock(int *lock)
{
*lock = 0;
} | TestAndSet(lock) == 1 |