• Running
  
  • A process in the running state has all of the resources that it needs for further execution, including a processor.
    

• Blocked
  
  • A process that needs some resource other than a processor for further execution is in a blocked state. It is usually placed in a queue waiting for the needed resource.
    

• Ready
  
  • A process in the ready state has all of the resources that it needs for further execution except for a processor. It is normally held in a ready queue until a processor becomes available.
    

• Interrupts
• Interrupts are special signals sent by hardware or software to the CPU.
• It's as if some part of the computer suddenly raised its hand to ask for the CPU's attention in a lively meeting.
• Sometimes the operating system will schedule the priority of processes so that interrupts are masked -- that is, the operating system will ignore the interrupts from some sources so that a particular job can be finished as quickly as possible.
• There are some interrupts (such as those from error conditions or problems with memory) that are so important that they can't be ignored. These non-maskable interrupts (NMIs) must be dealt with immediately, regardless of the other tasks at hand.
• An event that change the sequence in which a processor execute instructions
• Prevents a process from monopolizing the system
• OS sets interrupting clock/interval timer to allow user to run in a specific time interval.
  
  • If process does not free CPU in interval time, interrupting clock generates an interrupt that cause OS to regain control
  • OS turn the previously running process to ready, and makes the first process on the ready list running
    

• Medium-Term Scheduler
• The mid-term scheduler may decide to swap out a process which :
  
  • Has not been active for some time, or a process which has a low priority, or
  • A process which is page faulting (kesalahan muka surat) frequently, or
  • A process which is taking up a large amount (julat) of memory in order to free up main memory for other processes, swapping the process back in later when more memory is available, or
  • When the process has been unblocked and is no longer waiting for a resource.
    

• Short-Term Scheduler
• Also known as the dispatcher.
• Decides which of the ready, in-memory processes are to be executed (allocated a CPU) next following a clock interrupt, an IO interrupt, an operating system call or another form of signal.
• Makes scheduling decisions much more frequently than the long-term or mid-term schedulers
• Short-term scheduler
  
  • Short-term scheduler (or CPU scheduler) – selects which process should be executed next and allocates CPU
  • Short-term scheduler is invoked very frequently (milliseconds)  (must be fast)
• Processes can be described as either:
  
  • I/O-bound process – spends more time doing I/O than computations, many short CPU bursts
• CPU-bound process – spends more time doing computations; few very long CPU bursts
  

• Long-Term Scheduler
• The long-term, or admission, scheduler decides which jobs or processes are to be admitted to the ready queue.
• When an attempt is made to execute a program, its admission to the set of currently executing processes is either authorized or delayed by the long-term scheduler.
• Thus, this scheduler dictates what processes are to run on a system, and the degree of concurrency to be supported at any one time
• Long-term scheduler
  
  • Long-term scheduler (or job scheduler) – selects which processes should be brought into the ready queue
  • Long-term scheduler is invoked very infrequently (seconds, minutes)  (may be slow)
  • The long-term scheduler controls the degree of multiprogramming
    

• Differentiate between preemptive and non-preemptive technique in scheduling.
• In computing, preemption (more correctly ”pre-emption”) is the act of temporarily interrupting a task being carried out by a computer system, without requiring its cooperation, and with the intention of resuming the task at a later time
• Such a change is known as a context switch.
• It is normally carried out by a privileged task or part of the system known as a preemptive scheduler, which has the power to preempt, or interrupt, and later resume, other tasks in the system.
• CPU scheduling decisions may take place when a process:
  
  • 1. Switches from running to waiting state
  • 2. Terminates
  • 3. Switches from waiting to ready
  • 4. Switches from running to ready state
  • When scheduling takes place only under circumstances 1 and 2, we say that the scheduling scheme is non-preemptive; otherwise, its called preemptive
• Under non-preemptive scheduling, once the CPU has been allocated to a process, the process keep the CPU until it release the CPU either by terminating or by switching to waiting state. (Windows 95 and earlier)
• Preemptive scheduling incurs a cost associated with access to share data.
• Consider the case of two processes that share a data. It is preemptive so that while one process is updating the data, the second process then tries to read the data, which are in an inconsistent state

Shortest Job First

• When the CPU is available, it is assigned to the process that has the smallest next CPU burst.
• If the next CPU bursts of two processes are the same, FCFS scheduling is used to break the tie.

Priority, Multilevel Queue

• A priority is associated with each process, and the CPU is allocated to the process with the highest priority (high priority and low priority).
• We assume that low numbers represent lower priority. (1, 2, 3, 4, 5 : 5 is highest priority
• Non-preemptive.
  

Round Robin Scheduling

• The round-robin (RR) scheduling algorithm is designed especially for timesharing systems.
• It is similar to FCFS scheduling, but preemption is added to switch between processes.
• A small unit of time, called a time quantum or time slice, is defined. (A time quantum is generally from 10 to 100 milliseconds.)
• The ready queue is treated as a circular queue. The CPU scheduler goes around the ready queue, allocating the CPU to each process for a time interval of up to 1 time quantum.
• To implement RR scheduling, we keep the ready queue as a FIFO queue of processes.
• New processes are added to the tail of the ready queue. The CPU scheduler picks the first process from the ready queue, sets a timer to interrupt after 1 time quantum, and dispatches the process.
  

Multilevel Feedback Queue

• Has a number of queues, each assigned a different priority level.
• A job that is ready to run can only be on a single queue.
• It allows a process to move between queues. The idea is to separate processes according to the characteristics of their CPU bursts.
• If a process uses too much CPU time, it will be moved to a lower-priority queue.
• For example, consider a multilevel feedback-queue scheduler with three queues, numbered from 0 to 2 (0,1 and 2)
• The scheduler first executes all processes in queue 0. Only when queue 0 is empty will it execute processes in queue 1. Similarly, processes in queue 2 will only be executed if queues 0 and 1 are empty.
• A process that arrives for queue 1 will preempt a process in queue 2. A process in queue 1 will in turn be preempted by a process arriving for queue 0.
  

First In First Out (FIFO)

• The process that requests the CPU first is allocated to the CPU first
• Whichever process that first placed their request will get the CPU first.
  
  • 1. How many processes?
  • 2. What are the sequence of the processes?
  • 3. Calculate “Waiting Time”
  • 4. Label Waiting Time into the Gantt Chart.
       

Multilevel Queue

• Processes are easily classified into different groups.
• It partitions the ready queue into several separate queues.
• Each queue has its own scheduling algorithm
• Ready queue is partitioned into separate queues:
  
  • foreground (interactive)
  • background (batch)
• Scheduling must be done between the queues.
• Partitions the ready queue into several separate queues.
• Each queue has its own scheduling algorithm
• There must be scheduling between the queues
• The processes are permanently assigned to one queue based on some property of the process. For example :
  
  • Interactive process
  • Batch process
    

• Thread
  
  • A thread is the smallest unit of processing that can be performed in an OS. In most modern operating systems, a thread exists within a process - that is, a single process may contain multiple threads.
    

• Threads Relationship to Processes
  
  • At least one kernel thread exists within each process. If multiple kernel threads can exist within a process, then they share the same memory and file resources.
  • A thread represents a line of execution within a process. Processes can be multithreaded, that is, they can have several different lines of execution occurring simultaneously.
    

• Conditions For A Deadlock To Occur
  
  • 1.Mutual exclusion condition: a resource that cannot be used by more than one process at a time.
  • 2.Hold-and-wait condition: each thread holds one resource while waiting for another.
  • 3.No preemption condition: thread can only release resources voluntarily. No other thread (or OS) can force the thread to release.
  • 4.Circular wait condition: two or more processes form a circular chain where each process waits for a resource that the next process in the chain holds
  • All four conditions must occur before the deadlock happens.
  • There will be no deadlock if at least one of the conditions unhold.
• 3 ways to deal with deadlock
• We can deal with the deadlock problem in one of three ways:
  
  • Use a protocol to prevent or avoid deadlocks, ensuring that the system will never enter a deadlock state. OR
  • Allow the system to enter a deadlock state, detect it, and recover. OR
  • Ignore the problem altogether and pretend that deadlocks never occur in the system.
• Deadlock Prevention
  
  • Mutual Exclusion: The mutual-exclusion condition must hold for non-sharable resources. (Weaknesses: resource utilization may be low, and starvation)
  • Hold and Wait: whenever a process requests a resource, it does not hold any other resources
  • No Preemption: no preemption of resources that have already been allocated. (often applied to resources whose state can be easily saved and restored later, such as CPU registers and memory space)
  • Circular Wait: to ensure that this condition never holds is to impose a total ordering of all resource types and to require that each process requests resources in an increasing order of enumeration.
  • Deadlock Avoidance
  • Prevent deadlocks by restraining how requests can be made
  • The restraints ensure that at least one of the necessary conditions for deadlock cannot occur and, hence, that deadlocks cannot hold.
• Deadlock Solution
  
  • 1.Non-blocking synchronization algorithm
  • a non-blocking algorithm ensures that threads competing for a shared resource do not have their execution indefinitely postponed by mutual exclusion. A non-blocking algorithm is lock-free if there is guaranteed system-wide progress; wait-free if there is also guaranteed per-thread progress.
• 2.Serializing tokens
  
  • serializing tokens are a concept in concurrency control arising from the ongoing development of DragonFly BSD. According to Matthew Dillon, they are most akin to SPLs, except a token works across multiple CPUs while SPLs only work within a single CPU's domain.
• 3.Lock-free and wait-free algorithm
  
  • Lock-free data structures guarantee the progress of at least one thread when executing multithreaded procedures, thereby helping you avoid deadlock
• 4.Resource hierarchy solution
  
  • The resource hierarchy solution avoids deadlocks, it is not always practical, especially when the list of required resources is not completely known in advance.
  • For example, if a unit of work holds resources 3 and 5 and then determines it needs resource 2, it must release 5, then 3 before acquiring 2, and then it must re-acquire 3 and 5 in that order.
  • Computer programs that access large numbers of database records would not run efficiently if they were required to release all higher-numbered records before accessing a new record, making the method impractical for that purpose.