Aug 1, 2021

Today I will continue to cover operating systems and real-time concepts.

• When do you need an OS?

Multiple tasks to schedule and multiple hardware resources to leverage.

• When do you need a RTOS?

Real-time requirements are enforced.

• RTOS vs. time shared OS?

Tasks are executed with deadlines in RTOS while in time-share OS there is no guarantee that a task can be finished in a specific time period.

• Give some examples of GPOS and RTOS.

  • 1. Windows, Unix, Linux.

    2. FreeRTOS, RTLinux.

• Soft real-time vs. hard real-time.

Hard real time is a system whose operation is incorrect if result is not produced according to time constraint.

Soft real time system is a system whose operation is degraded if results are not produced according to the specified timing requirement.

• What is Real time and what is RTOS?

A real-time operating system is an operating system intended to serve real-time applications that process data as it comes in.

• What is priority inversion? Why priority inversion occurs and solutions for it?

It means a task with lower priority will run in front of the task with higher priority in some circumstances.

Priority inversion occurs when a high-priority task is forced to wait for the release of a shared resource owned by a lower-priority task.

One way to solve priority inversion is to use the priority ceiling protocol, which gives each shared resource a predefined priority ceiling.

An alternative is the priority inheritance protocol, a variation that uses dynamic priority adjustments.

Most RTOS that support priority inheritance require resource locks to be properly nested, meaning the resources must be released in the reverse order to that in which they were acquired.

• What is priority inheritance?

When a low-priority task acquires a shared resource, the task continues running at its original priority level. If a high-priority task requests ownership of the shared resource, the low-priority task is hoisted above the requesting task. The low-priority task can then continue executing its critical section until it releases the resource.

• Process vs threads

Processes have separate heap and stack spaces while threads share the same.

• IPC mechanisms

Allows processes to communicate with each other and synchronize their actions.

• Mutex, semaphore, conditional variables.

A mutex provides mutual exclusion, either producer or consumer can have the key (mutex) and proceed with their work.

A semaphore is a generalized mutex that allows multiple threads to access the same resource.

• Preemptive vs non-preemptive scheduling.

Preemptive Scheduling is a CPU scheduling technique that works by dividing time slots of CPU to a given process.

Non-preemptive Scheduling is a CPU scheduling technique the process takes the resource (CPU time) and holds it till the process gets terminated or is pushed to the waiting state.

• What is scheduling? And its types?

Scheduling is a method that is used to distribute valuable computing resources.

First Come First Serve (FCFS), Shortest-Job-First (SJF), Shortest Remaining Time, Priority Scheduling, Round Robin Scheduling, Multilevel Queue Scheduling

• What is priority scheduling?

Priority scheduling is a method of scheduling processes based on priority.

• What is super loop?

A super loop is a program structure comprised of an infinite loop, with all the tasks of the system contained in that loop.

• Process states

New, ready, run, terminated, wait, suspend.

• Demand paging

In a system that uses demand paging, the operating system copies a disk page into physical memory only if an attempt is made to access it and that page is not already in memory.

• Kernel

A Kernel is a computer program that is the heart and core of an Operating System.

• Thread

A thread is the smallest sequence of programmed instructions that can be managed independently by a scheduler.

• What are device drivers?

A device driver is a program that controls the operation of a specific type of device.

• What are short-term, medium-term and Long-term Schedulers?

Long-term scheduler regulates the programs which are selected to system for processing. Takes the process from job pool.

Short-Term Scheduler ensures which program is suitable or important for processing. Takes the process from ready queue.

• What is SMP (Shared multi-processing)?

Multiple processors share a common operating system and memory.

• What is context switch?

The process of storing the state of a process or thread, so that it can be restored and resume execution at a later point.

• CPU Bound vs I/O Bound?

  • 1. CPU Bound means the processing speed is limited by the speed of the CPU. A task that performs calculations on a small set of numbers, for example multiplying small matrices, is likely to be CPU bound.

    2. I/O Bound means the processing speed is limited by the speed of the I/O subsystem. A task that processes data from disk, for example, counting the number of lines in a file is likely to be I/O bound.

    3. Memory bound means the processing speed is limited by the amount memory available and the speed of that memory access. A task that processes large amounts of in-memory data, for example multiplying large matrices, is likely to be memory bound.

    4. Cache bound means the processing speed is limited by the amount and speed of the cache available. A task that simply processes more data than fits in the cache will be cache bound.

• Memory layout of a process

  • 1. Text segment contains executables

    2. Data section contains initialized global or static variables

    3. BSS section contains uninitialized variables.

    4. Stack contains the program stack.

    5. Heap contains the dynamically allocated memory regions.

See below for a diagram, which is taken from GeeksforGeeks.

• Multithreads

Multiple threads share the same resource.

• Deadlock?

Condition where different threads or processes wait for each other hence preventing the system to function properly.

• Conditions for deadlock?

Mutual exclusion, resource holding, no preemption, circular wait.

• Detecting and avoiding deadlocks?

Distributed deadlocks can be detected either by constructing a global wait-for graph from local wait-for graphs at a deadlock detector or by a distributed algorithm like edge chasing.

• Livelock?

A livelock is similar to a deadlock, except that the states of the processes involved in the livelock constantly change with regard to one another, none progressing. Livelock is a special case of resource starvation.

• Spinlock?

A lock which causes a thread trying to acquire it to simply wait in a loop ("spin") while repeatedly checking if the lock is available.

• Race Condition?

A race condition is the condition where the system's substantive behavior is dependent on the sequence or timing of other uncontrollable events.

• Binary semaphore vs Count semaphore

A binary semaphore is restricted to values of zero or one, while a counting semaphore can assume any nonnegative integer value.

• Difference between Mutexes and Critical Sections?

Critical section is user object and Mutex is kernel object.

Mutex is visible within the system it created. It can be used to synchronize between process.

Critical section is visible only within the process it created. It can be used to synchronize the threads in the same process.

• What are reentrant Locks? Implement a reentrant lock with mutexes.

The reentrant mutex (recursive mutex, recursive lock) is a particular type of mutual exclusion (mutex) device that may be locked multiple times by the same process/thread.

• Paging

A computer stores and retrieves data from secondary storage for use in main memory. OS maintains page tables.

To reduce the translation time, the TLB memorize recent correspondences between virtual and physical page addresses.

If translation is not in the TLB, it is recreated by table walk. If all the page tables are already copied to cache memory, it will require tens of cycles. If the cache misses, the time will be hundreds of cycles to load from main memory. If main memory still does not have that page, it is a page fault, which has to be loaded from disk.

• Segmentation

A memory management technique in which the memory is divided into the variable size parts.

• Swapping

Swapping is a memory management scheme in which any process can be temporarily swapped from main memory to secondary memory so that the main memory can be made available for other processes.

• Fragmentation

As processes are loaded and removed from memory, the free memory space is broken into little pieces. It happens after sometimes that processes cannot be allocated to memory blocks considering their small size and memory blocks remains unused. This problem is known as Fragmentation.

• Thrashing

Thrashing is a condition or a situation when the system is spending a major portion of its time in servicing the page faults, but the actual processing done is very negligible.

• What is top half and bottom half of a kernel?

Top Halves: Top halves executes as soon as CPU receive the interrupt. In the top halves, context interrupt and scheduler are disabled. This part of the code only contains critical code. Execution time of this code should be as short as possible because at this time Interrupt are disabled, we don't want to miss out other interrupt by generated by the devices.

Bottom Halves: The Job of the bottom half is used to run left over (deferred) work by the top halves. When this piece of code is being executed, interrupt is enabled and scheduler is disabled. Bottom halves are scheduled by softirqs and tasklets to run deferred work.