Key Concepts in Operating Systems: Memory, Processes, and Programs

Posted on Jan 25, 2025 in Computers

Dynamic Partitioning: An Example

A hole of 64K is left after loading 3 processes: not enough room for another process.

Eventually, each process is blocked. The OS swaps out process 2 to bring in process 4.

Another hole of 96K is created.

Eventually, each process is blocked. The OS swaps out process 1 to bring in process 2 again, and another hole of 96K is created…

Compaction would produce a single hole of 256K.

Difference Between Fixed and Dynamic Partitioning

Fixed Partitioning

Partitions main memory into a set of non-overlapping regions called partitions.
Partitions can be of equal or unequal sizes.
Any process whose size is less than or equal to a partition size can be loaded into the partition.
If all partitions are occupied, the operating system can swap a process out of a partition.
A program may be too large to fit in a partition. The programmer must then design the program with overlays.
When the module needed is not present, the user program must load that module into the program’s partition, overlaying whatever program or data are there.
Main memory use is inefficient. Any program, no matter how small, occupies an entire partition. This is called internal fragmentation.
Unequal-size partitions lessen these problems, but they still remain…
Equal-size partitions were used in early IBM’s OS/MFT (Multiprogramming with a Fixed number of Tasks).

Dynamic Partitioning

Partitions are of variable length and number.
Each process is allocated exactly as much memory as it requires.
Eventually, holes are formed in main memory. This is called external fragmentation.
Must use compaction to shift processes so they are contiguous and all free memory is in one block.
Used in IBM’s OS/MVT (Multiprogramming with a Variable number of Tasks).

What is the Critical Section Problem?

In concurrent programming, concurrent accesses to shared resources can lead to unexpected or erroneous behavior, so parts of the program where the shared resource is accessed are protected. This protected section is the critical section or critical region. It cannot be executed by more than one process. Typically, the critical section accesses a shared resource, such as a data structure, a peripheral device, or a network connection, that does not allow multiple concurrent accesses.

The critical section problem refers to the problem of how to ensure that at most one process is executing its critical section at a given time. Important: Critical sections in different threads are not necessarily the same code segment! If there are sections, then one of these threads will get into the critical section.

The solution to the Critical Section Problem must meet three conditions:

Mutual exclusion: If a process is executing in its critical section, no other process is executing in its critical section.
Progress: If no process is executing in its critical section and there exist some processes that wish to enter their critical sections, then only those processes that are not executing in their remainder section can participate in the decision of which will enter its critical section next, and this decision cannot be postponed indefinitely.

If no process is in the critical section, can decide quickly who enters.
Only one process can enter the critical section, so in practice, others are put on the queue.

Bounded waiting: There must exist a bound on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted.

The wait is the time from when a process makes a request to enter its critical section until that request is granted.
In practice, once a process enters its critical section, it does not get another turn until a waiting process gets a turn (managed as a queue).

Program

A computer program is a collection of instructions that performs a specific task when executed by a computer. A computer requires programs to function and typically executes the program’s instructions in a central processing unit.

A computer program is usually written by a computer programmer in a programming language. From the program in its human-readable form of source code, a compiler can derive machine code—a form consisting of instructions that the computer can directly execute. Alternatively, a computer program may be executed with the aid of an interpreter.

A part of a computer program that performs a well-defined task is known as an algorithm. A collection of computer programs, libraries, and related data are referred to as software. Computer programs may be categorized along functional lines, such as application software or system software.

Page Fault

When the page (data) requested by a program is not available in the memory, it is called a page fault. This usually results in the application being shut down. A page fault (sometimes called #PF, PF, or hard fault) is a type of interrupt, called a trap, raised by computer hardware when a running program accesses a memory page that is not currently mapped by the memory management unit (MMU) into the virtual address space of a process. Logically, the page may be accessible to the process but requires a mapping to be added to the process page tables and may additionally require the actual page contents to be loaded from a backing store such as a disk. The processor’s MMU detects the page fault, while the exception handling software that handles page faults is generally a part of the operating system kernel. When handling a page fault, the operating system generally tries to make the required page accessible at the location in physical memory or terminates the program in case of an illegal memory access.

Handling of Page Fault

The memory address requested is first checked to make sure it was a valid memory request.
If the reference was invalid, the process is terminated. Otherwise, the page must be paged in.
A free frame is located, possibly from a free-frame list.
A disk operation is scheduled to bring in the necessary page from disk. (This will usually block the process on an I/O wait, allowing some other process to use the CPU in the meantime.)
When the I/O operation is complete, the process’s page table is updated with the new frame number, and the invalid bit is changed to indicate that this is now a valid page reference.
The instruction that caused the page fault must now be restarted from the beginning (as soon as this process gets another turn on the CPU).

Difference Between Dynamic Loading and Dynamic Linking

Dynamic loading is concerned with loading the subroutines of a program as and when required during run-time, instead of loading all the subroutines at once before the program execution starts. This is useful in efficient memory usage since many subroutines may not be called at all.

Dynamic linking is concerned with linking library routines at run-time instead of combining them with the executable program code before the program execution starts, i.e., static linking. To achieve this, a small code called a ‘stub’ is inserted in the program code wherever a library routine is required. The stub contains information about where to find the routine if it is not already in the main memory and how to load it into the main memory. If the library routine is already present in the main memory, then the stub replaces itself with the address of the routine and executes it. So, like dynamic loading, dynamic linking also helps in efficient memory usage.

Advantages of Round Robin and FCFS

Advantages of RR

There is fairness since every process gets an equal share of the CPU.
The newly created process is added to the end of the ready queue.
A round-robin scheduler generally employs time-sharing, giving each job a time slot or quantum.

Advantages of FCFS

The advantage of the FCFS algorithm is that it is very easy to implement.
Simplest form of disk scheduling algorithm.
Easy to program.
Intrinsically fair.

Paging vs. Segmentation

Question: What are the differences between paging and segmentation?	Paging	Segmentation
1	A page is a physical unit of information.	A segment is a logical unit of information.
2	A page is invisible to the user’s program.	A segment is visible to the user’s program.
3	A page is of fixed size, e.g., 4KB.	A segment is of varying size.
4	The page size is determined by the machine architecture.	A segment size is determined by the user.
5	Fragmentation may occur.	Segmentation eliminates fragmentation.
6	Page frames on main memory are required.	No frames are required.

Process vs. Thread

Difference between Process and Thread	Process	Thread
1	Process is heavyweight or resource-intensive.	Thread is lightweight, taking fewer resources than a process.
2	Process switching needs interaction with the operating system.	Thread switching does not need to interact with the operating system.
3	In multiple processing environments, each process executes the same code but has its own memory and file resources.	All threads can share the same set of open files and child processes.
4	If one process is blocked, then no other process can execute until the first process is unblocked.	While one thread is blocked and waiting, a second thread in the same task can run.
5	Multiple processes without using threads use more resources.	Multiple threaded processes use fewer resources.
6	In multiple processes, each process operates independently of the others.	One thread can read, write, or change another thread’s data.

Multi-User vs. Multitasking vs. Multithreading Operating Systems

Multi-User Operating System

A multi-user operating system is a computer operating system (OS) that allows multiple users on different computers or terminals to access a single system with one OS on it. These programs are often quite complicated and must be able to properly manage the necessary tasks required by the different users connected to it. The users will typically be at terminals or computers that give them access to the system through a network, as well as other machines on the system such as printers. A multi-user operating system differs from a single-user system on a network in that each user is accessing the same OS at different machines.

Multitasking Operating System

Multitasking is a logical extension of a multiprogramming system that supports multiple programs to run concurrently. In multitasking, more than one task is executed at the same time. In this technique, the multiple tasks, also known as processes, share common processing resources such as a CPU. In the case of a computer with a single CPU, only one job can be processed at a time. Multitasking solves the problem by scheduling and deciding which task should be the running task and when a waiting task should get a turn. This attempt is done with the help of an interrupt (a signal) which is attended by the CPU by keeping the current activity aside, saving its present status in a buffer, and returning to another important job whatever task it was doing earlier. The act of re-assigning a CPU from one task to another one is known as a context switch.

Multithreading

In computer architecture, multithreading is the ability of a central processing unit (CPU) or a single core in a multi-core processor to execute multiple processes or threads concurrently, appropriately supported by the operating system. This approach differs from multiprocessing, as with multithreading the processes and threads share the resources of a single or multiple cores: the computing units, the CPU caches, and the translation lookaside buffer (TLB).

Where multiprocessing systems include multiple complete processing units, multithreading aims to increase the utilization of a single core by using thread-level as well as instruction-level parallelism. As the two techniques are complementary, they are sometimes combined in systems with multiple multithreading CPUs and in CPUs with multiple multithreading cores.

System Programs vs. System Calls

System Programs

System programs provide a convenient environment for program development and execution.

They can be divided into:

File manipulation
Status information
File modification
Programming language support
Program loading and execution
Communications
Application programs

Most users’ view of the operating system is defined by system programs, not the actual system calls.

System Calls

A system call is usually a request to the operating system (kernel) to do a hardware/system-specific or privileged operation. As of Linux-1.2, 140 system calls have been defined. System calls like close() are implemented in the Linux libc. This implementation often involves calling a macro which eventually calls syscall(). Parameters passed to syscall() are the number of the system call followed by the needed arguments. The actual system call numbers can be found in linux/unistd.h while sys/syscall.h gets updated with a new libc. If new calls appear that don’t have a stub in libc yet, you can use syscall(). As an example, you can close a file using syscall() like this (not advised):

#include <unistd.h>

extern int syscall(int, ...);

int my_close(int filedescriptor)
{
  return syscall(SYS_close, filedescriptor);
}

System calls provide an interface between the process and the operating system. System calls allow user-level processes to request some services from the operating system which the process itself is not allowed to do. In handling the trap, the operating system will enter kernel mode, where it has access to privileged instructions, and can perform the desired service on behalf of the user-level process. It is because of the critical nature of operations that the operating system itself does them every time they are needed. For example, for I/O a process involves a system call telling the operating system to read or write a particular area, and this request is satisfied by the operating system.

System programs provide basic functioning to users so that they do not need to write their own environment for program development (editors, compilers) and program execution (shells). In some sense, they are bundles of useful system calls.