HOME


Top 10 List of Week 08

  1. CPU Scheduling
    Most programs that run on a computer rely on being able to alternate the cycle of CPU number-crunching and waiting for I/O. The time it takes to wait for I/O is relatively long compared to how long it takes for the CPU to do its thing. So, to prevent the CPU from just wasting time waiting for I/O, a concept known as CPU scheduling is used to utilize the CPU in the mean time. However, the challenge here is to make the overall system as efficient and fair as possible when it comes to the many conditions it may face.

  2. The CPU-I/O Burst Cycle
    So in the previous point I’ve mentioned that CPU scheduling makes use of the time spent waiting for the I/O to utilize the CPU more. The way this works is that upon the execution of a process, there occurs a CPU burst, followed by an I/O burst; alternating until the process is completed or a termination signal is received. Now, CPU scheduling decisions may be made during the down-times in a process, where it is in a waiting or ready state, or upon termination.

  3. Pre-emptive Scheduling
    Pre-emptive scheduling is the scheduling method used when either a process switches from a running state to a ready state, or from a waiting state to a ready state. In this method, the resources are allocated to another process for a limited amount of time, then taken away to the ready queue. There are yet more algorithms which are based on preemptive scheduling, such as Round Robin scheduling, Shortest Remaining Time First, etc.

  4. Non-Preemptive Scheduling
    Unlike the previous method which I mentioned earlier, non-preemptive scheduling is used when a process terminates, or when it switches from running state to a waiting state. In this method, the running process holds onto the system resources until it either gets terminated, or reaches a waiting state. This does not involve interruption of a running process, instead opting to wait for the process to complete its CPU burst time, then allocating resources to another process.

  5. States of a Process
    Earlier I’ve mentioned states of a process, such as the waiting state, etc. To clarify, this sort of ties back to the material of previous weeks somewhat. There are various states of a process, which are as follows:
    • New: The process is about to be created.
    • Ready: Self explanatory, assigned after the creation of a process.
    • Running: Under execution by the CPU
    • Blocked/Waiting: Waiting for I/O in the main memory, not actively running in the CPU
    • Terminated/Completed: Process is killed
    • Suspend Ready: Was ready, but now swapped into external storage
    • Suspend Wait/Blocked: See above.
  6. The Scheduler
    There are three main types of schedulers:
    • Long-term Scheduler: Selects jobs from a pool and loads them onto the main memory (ready queue), also known as the Job-scheduler
    • Short-term Scheduler: Select a job from the ready queue and assigns it to the CPU with the help of the Dispatcher (see below). Also known as the CPU Scheduler. This scheduler makes use of one of many scheduling algorithms, which I will mention at a later point.
    • Medium-term Scheduler: Switches out a process from main memory to the waiting queue upon I/O wait. When it is completed, it goes back to the ready queue.

  7. The Dispatcher
    The Dispatcher (sounds like the title to some kind of action movie) is a module which connects the CPU to the process which was selected by the scheduler. This module is largely in charge of switching the CPU from one process to another, which may result in Dispatch Latency. This module is also responsible for jumping to the proper location in the program to start execution.

  8. Scheduling Algorithms
    • First-Come, First-Served (FCFS): A traditional queue, usually poor in performance
    • Shortest-Job-Next: Best approach for minimizing waiting times, executes based on estimated execution times.
    • Priority Scheduling: FCFS with priority per process, basically a priority queue.
    • Shortest Remaining Time: Pre-empive version of SJN, cannot be implemented in systems where required execution time is unknown.
    • Round Robin: Each process given a fixed time to execute called a quantum. Context-switching used at the end of each time period.
    • Multiple-Level Queue: Consists of multiple queues which make use of other existing algorithms.

  9. Scheduler in Linux
    The Completely Fair Scheduler (CFS) is the scheduling system used in linux currently. It is based on the rotating staircase deadline scheduler, and equally divides cpu time among all processes. An alternative to this scheduler, not currently implemented in the linux kernel is the Brain F**k Scheduler (keeping it family-friendly)

  10. Linux From Scratch
    You know, I may have jynxed myself when I mentioned a few weeks ago about how I was probably never gonna try an installation of Arch Linux. Turns out we might be doing something a lot more in-depth than that. Linux From Scratch is project which aims to help people build their own custom systems using the Linux kernel. I’ll be honest when I say this seems really daunting, though a part of me is also a little excited to see what’s ahead of us.