OS Midterm

OS offers user-oriented services and system oriented services

Services designed to assist users and applications by providing essential functionality

User interfaces, program execution, I/O operations, file management, communication, and error handling

Services that ensure efficient operation and resource sharing among multiple users and processes

Resource allocation, accounting, and ensuring protection and security

User Interface (UI):
Provides a way for users to interact with the system.
Common types of interfaces include: Command-Line Interface (CLI): Allows users to type commands. Graphical User Interface (GUI): Uses windows, icons, and menus.
Batch: Processes a series of commands in a batch file without direct user interaction.

Program Execution:
The OS must be able to load programs into memory and execute them.
It manages the program's life cycle, including starting, running, and handling abnormal termination due to errors.

I/O Operations:
The OS manages all Input/Output (I/O) requests from programs, whether the request involves reading/writing to a file or interacting with hardware devices like printers or keyboards.

File-System Manipulation:
Provides file-related operations such as reading, writing, creating, deleting, and searching files and directories.
The OS also manages permissions to ensure authorized access to files.

Communication:
Processes running on the same or different computers can communicate through shared memory or message passing (e.g., packets).
The OS facilitates these communication mechanisms between processes over networks or within a single system.

Error Detection:
The OS is responsible for detecting errors in CPU, memory, I/O devices, or user programs.
It should take corrective action and provide debugging tools to help programmers diagnose issues.

Resource Allocation: When multiple processes or users are running simultaneously, the OS must efficiently allocate resources like CPU time, memory, file storage, and I/O devices.

Accounting: The OS keeps track of resource usage for individual users or processes, providing data for billing or performance analysis.

Protection and Security: The OS ensures that resources are protected and secure from unauthorized access. It manages user authentication and ensures that concurrent processes do not interfere with each other. Security extends to defending the system against malicious access attempts, especially in networked environments.

Allows direct command entry
- Sometimes implemented in kernel, sometimes by systems program
- Sometimes multiple flavors implemented
- shells, are different kinds of CLIs
- Primarily fetches a command from user and executes it
- Sometimes commands built-in, sometimes just names of programs• If the latter (e.g., UNIX), adding new features doesn't require shell modification, simply add new programs

Has icons that present files, programs, actions, etc
- Various mouse buttons over objects in the interface cause various actions (provide information, options,execute function, open directory (known as a folder)
- Invented at Xerox PARC
-Many systems have CLI and GUI

Touchscreen devices require new interfaces
- Mouse not possible or not desired
- Actions and selection based on gestures
- Virtual keyboard for text entry
- Voice commands are also typically possiblesed

System calls are low-level functions provided by the operating system.
They provide a consistent interface for common operations.
E.g. the read function to read from a file descriptor.

System calls provide an interface to the services made available by an operating system.

A number is associated with each system call and the system-call interface maintains an indexed table according to these numbers
- The system call interface invokes the intended system call in kernel and returns status of the system call and any return values
- The caller does not need to know how the call is implemented
- Just needs to obey API and understand what OS will do as a result call
- API hides most of the details of the OS interface from the programmer
- API is Managed by run-time support library (set of functions built into libraries included with compiler) will take the commands written using the API and translate them into actual system calls the OS understands

• Typically written in a high-level language (C or C++)
• Mostly accessed by (user) programs via a high-level Application Programming Interface (API) rather than direct system call use
• Three most common APIs are Win32 API for Windows, POSIX API for POSIX-based systems (including virtually all versions of UNIX, Linux, and Mac OS X), and Java API for the Java virtual machine (JVM)

Three general methods used to pass parameters to the OS
- Simplest: pass the parameters in registers
In some cases, may be more parameters than registers
- Parameters stored in a block, or table, in memory, and address of block passed as a parameter in a register• This approach taken by Linux and Solaris
- Parameters placed, or pushed, onto the stack by the program and popped off the stack by the operating system
- Block and stack methods do not limit the number or length of parameters being passed

fork(), exit(), wait(), open(), read()

Process control(manage the creation, execution, and termination of processes), File management(handle operations related to file creation and manipulation), Device management(manage interaction with hardware devices), Information maintenance(retrieve or set system and process information), Communications(facilitate communication between processes, either on the same machine or across a network), Protection(manage access control and security)

Process control
- create process, terminate process
- end, abort
- load, execute
- get process attributes, set process attributes
- wait for time- wait event, signal event
- allocate and free memory
- Dump memory if error
- Debugger for determining bugs, single step execution
- Locks for managing access to shared data between processes

File management
- create file, delete file
- open, close file
- read, write, reposition
- get and set file attributes

Device management
- request device, release device
- read, write, reposition
- get device attributes, set device attributes
- logically attach or detach devices

Information maintenance
- get time or date, set time or date
- get system data, set system data
- get and set process, file, or device attributes

Communications
- create, delete communication connection
- send, receive messages if message passing model to host name or process name
From client to server
- Shared-memory model create and gain access to memory regions
- transfer status information
- attach and detach remote devices

Protection
- Control access to resources
- Get and set permissions
- Allow and deny user access

Single-tasking: MS-DOS can run only one process at a time.
Shell invoked at startup: The shell (command interpreter) starts when the system boots up.
Program execution: Programs are loaded into memory, overwriting everything except the kernel. Once a program finishes execution, the shell is reloaded.
No process creation: Unlike modern OSes, MS-DOS does not create separate processes for running programs.

They provide a convenient environment for program development and execution
- System programs act as intermediaries between users and the operating system, offering tools and functionalities that simplify tasks
- Most users' view of the operation system is defined by system programs, not the actual system calls

File management and modification: Programs to create, delete, copy, rename, or manipulate files.

Status information: Programs that retrieve and display system information (e.g., memory usage, available disk space).

Programming language support: Tools like compilers, assemblers, debuggers, and interpreters to support software development.

Program loading and execution: Utilities that load programs into memory and manage their execution.

Communications: Programs for messaging, file transfers, and remote login.

Background services: Processes that run in the background to perform system tasks like error logging and process scheduling.

Application programs: General-purpose user programs not considered part of the OS.

File management programs allow users to: Create, delete, copy, rename, print, list, and dump files and directories.
Tools include text editors and commands that search or modify the contents of files.

Status information programs retrieve data like system date, time, available memory, disk space, and number of active users.
Others provide detailed performance, logging, and debugging information
- Typically, these programs format and print the output to the terminal or other output devices
Some systems implement a registry (used to store and retrieve configuration information)

Operating systems may provide compilers, assemblers, debuggers, and interpreters for program development in various programming languages.

Tools like loaders, linkage editors, relocatable loaders, and debugging systems allow users to load, relocate, and execute programs at the machine level or higher levels.

These programs provide mechanisms to create virtual connections among processes, users, and computer systems.
Allows users to send messages to other users' screens, send emails, browse web pages, log in remotely, and transfer files between machines.

Background services launch at system startup and run continuously or terminate once specific tasks are completed.
These services include functions like disk checking, error logging, process scheduling, and printing.
Services, subsystems, daemons are background programs that provide essential system functions without user intervention.

Application programs are software that users run for specific tasks but are not considered part of the operating system.
Examples include word processors, web browsers, and media players.
These programs are launched by users, typically through a command-line interface, mouse click, or touch screen

Internal structure of different Operating Systems can vary widely

Start the design by defining goals and specifications
Affected by choice of hardware, type of system

Much variation
- Early OSes in assembly language
- Then system programming languages like Algol, PL/1
- Now C, C++

Actually usually a mix of languages
- Lowest levels in assembly
- Main body in C- Systems programs in C, C++, scripting languages like PERL, Python, shell scripts

Higher-level languages are easier to port to other hardware but are generally slower. Emulation allows an OS to run on non-native hardware.

OS structures can be simple (MS-DOS), Non simple structure (UNIX), layered (an abstraction), or microkernel (Mach)

A simple structure is designed to provide the most functionality in the least amount of space

Although MS-DOS has some structure, its interfaces and levels of functionality are not well separated

A layered OS structure has modularity, where each layer only uses services and functions from the layers below. The lowest layer is the hardware, and the top layer is the user interface (UI). It also uses privilege levels to ensure kernel instructions are executed by users with appropriate access, primarily dealing with I/O and hardware resources.

A microkernel structure moves as much functionality from the kernel into user space. This makes it easier to extend, more portable to new architectures, more reliable (less code is running in kernel mode), and more secure (than simple or traditional UNIX). However, there is a performance overhead due to communication between user space and kernel space via message passing.

Modern OSes often use loadable kernel modules in an object-oriented approach. Each core component is separate, communicates through known interfaces, and can be loaded as needed within the kernel. This provides more flexibility compared to layered models.

- User goals: operating system should be convenient to use, easy to learn, reliable, safe, and fast
- System goals: operating system should be easy to design, implement, and maintain, as well as flexible, reliable, error-free, and efficient

Policy: What will be done? → How to specify a requirement?Mechanism: How to do it? → How to achieve a requirement?• Mechanisms determine how to do something, policies decide what will be done
The separation of policy from mechanism is a very important principle, it allows maximum flexibility, if policy decisions are to be changed later

UNIX - limited by hardware functionality, the original UNIX operating system had limited structuring. Beyond simple but not fully layered

The UNIX OS consists of two separable parts
- Systems programs
- The kernel, consists of everything below the system-call interface and above the physical hardware
Provides the file system, CPU scheduling, memory management, and other operating-system functions; a large number of functions for one level

OSes create log files with information for debugging and use performance tuning to optimize system performance.

Log files contain information about errors that occur within the system, which can be used for debugging.

A core dump file captures the memory state of a process when an application fails, helping developers understand the state of the application at the time of the failure.

A crash dump file captures the kernel's memory state when the operating system fails.

Performance tuning involves removing system bottlenecks to improve efficiency, often by profiling, which uses periodic sampling and instruction pointers to detect statistical trends.

Moves as much from the kernel into user space
• Mach example of microkernel
- Mac OS X kernel (Darwin) partly based on Mach

• Communication takes place between user modules using message passing

Most modern OSes use hybrid models that combine multiple approaches to address system needs.

Linux and Solaris kernels in kernel address space, so monolithic, plus modular for dynamic loading of functionality
- Windows mostly monolithic, plus microkernel for different subsystem personalities
• Apple Mac OS X hybrid, layered, Aqua UI plus Cocoa programming environment

Profiling involves periodic sampling and using the instruction pointer to detect statistical trends in system performance.

An OS is generated to run on any class of machine. It must be configured for each specific computer system using the SYSGEN program, which gathers information about the system's hardware configuration.

The SYSGEN program collects information about the specific hardware configuration of a system and is used to build a system-specific compiled kernel. This allows for the generation of more efficient code than a general-purpose kernel.

An OS has two types of programs: batch system programs (jobs) and time-shared system programs (user programs or tasks).

A process is a program in execution, which forms the basis of all computation.

The components of a process include:
Text section: Program code.
Current activity: Includes the program counter and process registers.
Stack: Contains temporary data like function parameters, return addresses, and local variables.
Data section: Contains global variables.
Heap: Contains dynamically allocated memory during runtime

The states of a process include:
New: The process is being created.
Running: Instructions are being executed.
Waiting: The process is waiting for an event to occur (e.g., I/O).
Ready: The process is waiting to be assigned to a processor.
Terminated: The process has finished execution.

Threads are lightweight processes that share the same resources but execute independently, allowing for more efficient task execution within a process.

iOS is structured on Mac OS X with added functionality for mobile devices.

iOS uses a different CPU architecture (ARM vs. Intel), which prevents it from running Mac OS X applications natively.

OS uses the Cocoa Touch and Objective-C API for app development.

iOS's media services layer supports graphics, audio, and video.

iOS provides cloud computing capabilities and database management.

The iOS kernel is based on the Mac OS X kernel.

Android was developed by the Open Handset Alliance, primarily Google, and it is an open-source mobile operating system.

Android is based on a modified version of the Linux kernel.

The Android kernel provides process, memory, device-driver management, and power management.

Android uses a runtime environment that includes a core set of libraries and the Dalvik virtual machine.

Android apps are developed in Java using the Android API. Java class files are compiled into bytecode and then translated into executable code for the Dalvik virtual machine.

Android includes libraries for web browsing (webkit), databases (SQLite), multimedia, and a smaller libc.

A program becomes a process when it is loaded into memory. A program is a passive entity, whereas a process is active. Programs are stored on disks as executable files and become processes when loaded into memory.

One program can become several processes, such as multiple users running the same program simultaneously.

A process control block (PCB) contains information associated with each process, including:
Process state: Current state of the process
Program counter - location of instruction to next execute• CPU registers - contents of all process-centric registers
• CPU scheduling information- priorities, scheduling queue pointers
• Memory-management information - memory allocated to the process
• Accounting information - CPU used, clock time elapsed since start, time limits
• I/O status information - I/O devices allocated to process, list of open files

The scheduler selects which process should run next, while the dispatcher is responsible for giving control of the CPU to the process selected by the scheduler.

Using a task_struct C structure

The task_struct contains:
CPU registers: Contents of process-specific registers.
CPU scheduling information: Includes priorities and scheduling queue pointers.
Memory management information: Memory allocated to the process.
Accounting information: CPU usage, clock time elapsed since the process started, and time limits.
I/O status information: Includes I/O devices allocated to the process and a list of open files.

During a context switch, the CPU saves the state of the current process into the process control block (PCB) and reloads the state of the next process from its PCB into the CPU.

A process has a single thread of execution, while a thread has multiple. Threads can have multiple program counters in the PCB, allowing multiple parts of the program to execute simultaneously.

The OS uses a process scheduler to maximize CPU efficiency by selecting which process to run next and deciding when to switch between processes.

A process scheduler selects which process should be executed next on the CPU. It maintains various scheduling queues of processes.

The types of process queues include:
Job queue: The set of all processes in the system.
Ready queue: The set of processes residing in main memory and ready to execute.
Device queues: The set of processes waiting for an I/O device.

Processes migrate among different queues (job queue, ready queue, and device queue) based on their state and CPU or I/O needs.

There are three types of schedulers:
Short-term scheduler: Selects which process should be executed next. Is invoked frequently (milliseconds) ➔ (must be fast)
Medium-term scheduler: Handles swapping processes in and out of memory.
Long-term scheduler: Decides which processes should be admitted to the system for execution. Is invoked infrequently (seconds, minutes) ➔ (may be slow), controls the degree of multiprogramming

Multitasking in mobile systems allows multiple processes to be run concurrently, often by rapidly switching between them.

Context switching is when the system saves the state of the current process and loads the state of a new process. The context of a process is represented in its process control block (PCB). The system does no useful work during a context switch, and the time taken depends on the complexity of the PCB and the hardware.

A queueing diagram represents queues, resources, and the flow of processes through the system.

Swapping is the process of removing a process from memory and storing it on disk. When needed again, the process is loaded from the disk back into memory to continue execution. This is typically handled by the medium-term scheduler.

The medium-term scheduler can be added if the degree of multiprogramming needs to decrease. It removes processes from memory and stores them on disk, and later reloads them when necessary.

iOS: Typically runs a single foreground process controlled via the UI, with multiple background processes running in memory but not on display. Background processes have limits, such as handling short tasks, event notifications, or audio playback.
Android: Runs foreground and background processes with fewer limits. Background tasks are often handled by services that can continue running even if the main process is suspended.

A parent process creates child processes, forming a tree of processes. Processes are managed and identified using a process identifier (PID).

Resources can be shared between parent and child processes in three ways:
Completely shared.
Partially shared.
Not shared at all.

The time it takes for a context switch depends on the complexity of the process control block (PCB) and the hardware. Systems with multiple sets of registers per CPU can load multiple contexts at once, reducing switch time.

I/O-bound process: Spends more time performing I/O operations than computations, with many short CPU bursts.
CPU-bound process: Spends more time performing computations with fewer, but longer, CPU bursts.

The long-term scheduler strives for a good mix of I/O-bound and CPU-bound processes to optimize system performance.

If the hardware has multiple sets of registers per CPU, multiple contexts can be loaded at once, reducing the time required for context switching.

A child can have the same address space as the parent or have a new program loaded into it. In UNIX, fork() creates the child process, and exec() replaces the child's memory space with a new program

The exit() system call asks the OS to terminate the process after it executes its last statement. The status data is returned to the parent via wait(), and then the OS deallocates the process's resources.

A parent can terminate its child using abort() if:
The child has exceeded allocated resources.
The child's task is no longer required.
The parent is exiting, and the OS doesn't allow a child to continue if the parent terminates (cascading termination).

Cascading termination occurs when the OS initiates the termination of a child process because its parent has terminated, and the OS doesn't allow the child to continue running.

A zombie process occurs when a child process has completed execution, but its parent process has not called wait() to retrieve its exit status. The process is still in the process table.

In UNIX, the init process adopts orphaned processes and periodically invokes wait() to clean up zombie processes.

Single-process web browsers may crash or hang if one website causes issues, as the entire browser runs as a single process.

Multiprocess browsers, like Google Chrome, have three types of processes:Browser process: Manages the user interface (UI), disk, and network I/O.
Renderer process: Renders web pages and handles HTML and JavaScript. A new renderer is created for each website, running in a sandbox to restrict disk and network I/O, minimizing security risks.
Plug-in process: Manages each type of plug-in separately.

Independent processes: Cannot affect or be affected by the execution of other processes.
Cooperating processes: Can affect or be affected by the execution of other processes, often through shared data.

The Producer-Consumer problem is a common paradigm where a producer process generates information and stores it in a buffer until the consumer process consumes it. Synchronization is required to prevent the producer from producing data when the buffer is full and the consumer from consuming data when the buffer is empty.

Synchronization refers to coordinating the execution of processes to ensure that shared data is accessed in a safe and orderly manner, avoiding conflicts such as race conditions.

- Information sharing
- Computation speedup
- Modularity
- Convenience

Dependent processes communicate using interprocess communication (IPC), which can involve shared memory or message passing.

Unbounded buffer: The producer can produce indefinitely without waiting.
Bounded buffer: The buffer has limited space, so synchronization is required to prevent the producer from producing when the buffer is full, and the consumer from consuming when the buffer is empty.

Shared memory: Processes communicate by accessing common memory. The OS does not manage the communication, and synchronization must be handled by the processes.
Message passing: Processes send and receive messages through standard communication operations. Message size can be fixed or variable, and a communication link must be established.

Communication links can be through shared memory, hardware buses, or networks. Links can communicate directly or via a mailbox, in real-time or with delays, and may be automatically buffered or require explicit handling.

Links are established automatically.
Each link is associated with exactly one pair of communicating processes.
There is exactly one link between each pair of processes.
The link may be unidirectional or bi-directional.

In indirect communication, messages are sent to and received from mailboxes (or ports). Processes can communicate only if they share a mailbox. Messages are sent to uniquely identified ports. Links are created only if processes share a port. Links can be shared by multiple processes and can be bidirectional or unidirectional. Since port sharing is allowed, it can be unclear which process is meant to receive a message.

Possible solutions include:
Restricting the link to two processes.
Allowing only one process to receive messages at a time.
Having the system arbitrarily select the receiver.

Synchronization is the process by which processes communicate and wait for each other when passing messages. Processes can use blocking (synchronous) or non-blocking communication.

Blocking send: The sender waits until the message is received by another process.
Blocking receive: The receiver waits until a message is available to be received.

Non-blocking send: The sender continues executing tasks after sending a message.
Non-blocking receive: The receiver can either receive a valid message or a null message if no message is available.

A rendezvous occurs when both the sender and receiver are blocking. The sender only sends when the receiver is ready to receive, and the receiver waits for a message.

Buffering is a queue of messages attached to the link between processes.

Zero capacity: No messages are queued on the link; the sender must wait for the receiver.
Bounded capacity: Messages have a finite length (n), and the sender must wait if the link is full.
Unbounded capacity: The message length can be unlimited.

Examples of IPC include POSIX (using shared memory) and Windows (using advanced local procedure call - LPC).

shm_open(name, O_CREAT | O_RDWR, 0660): Creates a shared memory segment or opens an existing one.
ftruncate(shm_fd, SIZE): Sets the size of the shared memory object.
sprintf(shared_memory, "message"): Writes a message into the shared memory.
mmap(0, SIZE, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0): Memory maps the shared memory object.
shm_unlink(memory_name): Removes the shared memory object.

The client opens a handle to the subsystem's connection port.
The client sends a connection request, and the server creates two private communication ports.
The server returns the handle to one of the communication ports to the client.
The client and server use the handle to send messages and listen for replies. LPC works only between processes on the same system.

The shm_unlink() function removes the shared memory object, effectively deallocating the shared memory segment.

Create or open a shared memory segment using shm_open().
Set the size of the shared memory using ftruncate().
Write into the shared memory using sprintf().
Map the memory using mmap().
Remove the shared memory object using shm_unlink() when it's no longer needed.

The server creates two private communication ports and returns a handle to one of them for the client. The client and server use this handle to send messages and listen for replies.

Shared memory is an area of memory shared among processes that wish to communicate. The communication is controlled by the user processes, not the operating system.

The major issue is ensuring that user processes synchronize their actions when accessing shared memory to avoid conflicts.

Message passing is a mechanism for processes to communicate and synchronize their actions without using shared variables. It involves sending and receiving messages between processes.

The two operations are:
send(message): To send a message to another process.
receive(message): To receive a message from another process.

They need to:
Establish a communication link between them.
Exchange messages using sendeceive operations.

How are communication links established?
Can a link be associated with more than two processes?
How many links can exist between each pair of communicating processes?
What is the capacity of a link?
Is the message size fixed or variable?
Is the link unidirectional or bi-directional?

Physical: Shared memory, hardware bus, or network.
Logical: Direct or indirect, synchronous or asynchronous, automatic or explicit buffering.

In direct communication, processes must explicitly name each other in messages. For example, send(P, message) sends a message to process P, and receive(Q, message) receives a message from process Q.

Create a new mailbox (port).
Send and receive messages through the mailbox.
Destroy the mailbox.

Multiple processes can share a mailbox. For example, if P1 sends a message to mailbox A, both P2 and P3 (who share the mailbox) can receive it. However, only one process (P2 or P3) should receive the message, which introduces ambiguity.

A socket is an endpoint for communication. It includes the IP address and port number to differentiate network services on a host.

Ports below 1024 are used for standard services. The IP address 127.0.0.1 (loopback) refers to the system on which the process is running.

TCP Socket: Connection-oriented.
UDP Socket: Connectionless.
Multicast Socket: Allows data to be sent to multiple recipients.

An RPC allows a program to execute a procedure on another computer across a network, appearing as if it's calling a local function.

RPC uses ports to differentiate between services and employs stubs (client-side placeholders) for the actual procedure that runs on the server.

Client-side stub: Locates the server and packages the parameters to be sent.
Server-side stub: Unpacks the parameters, performs the procedure, and sends the results back to the client.

Stub code is compiled from specifications written in Microsoft Interface Definition Language (MIDL).

RPC uses External Data Representation (XDR) to manage differences in data formats, such as big-endian vs little-endian.

RPC guarantees that messages are delivered exactly once, reducing the chances of lost or duplicated messages during remote communication.

The operating system typically provides a rendezvous/matchmaker service to connect clients and servers by finding a port number for communication.

Pipes act as conduits for two processes to communicate. There are two types of pipes:
Ordinary pipes: Only accessible within the process that created them, usually used between a parent and a child process.
Named pipes: Accessible without a parent-child relationship and can be used for bidirectional communication between processes. These are called anonymous pipes in Windows.

Ordinary pipes: Can only be accessed by processes within a parent-child relationship and are unidirectional.
Named pipes: Can be accessed without a parent-child relationship, allow bidirectional communication, and can be used by multiple processes.

Named pipes have a read end (0) and a write end (1), and they are more powerful than ordinary pipes as they support bidirectional communication and can be used by several processes.

A thread is the fundamental unit of CPU utilization and forms the basis of multithreaded computer systems. Threads allow multiple tasks to run within a single application.

Thread creation is lightweight compared to process creation, and threads run within the same application, allowing for more efficient CPU utilization.

Threads can simplify code by allowing for parallel tasks and can increase efficiency by utilizing shared resources within a process, reducing the complexity compared to shared memory or message passing.

Multithreading allows for multiple tasks to be handled concurrently, which improves performance and responsiveness, especially when parts of a process are blocked. It is also more efficient and scalable, taking advantage of multiprocessor architectures.

The benefits include:
Continuation of execution if part of the process is blocked.
Easier resource sharing within the process, compared to shared memory or message passing.
Cheaper than process creation.
Lower overhead than context switching.
Scalability, allowing the system to take advantage of multiprocessor architectures.

The challenges include:
Dividing activities into tasks.
Balancing workloads.
Splitting data across cores.
Managing data dependencies.
Testing and debugging parallel processes.

Parallelism: The ability of a system to perform multiple tasks simultaneously.
Concurrency: The ability to make progress on multiple tasks, even if they are not running simultaneously (e.g., using a scheduler on a single core).

Data parallelism: Data is distributed across multiple cores, and the same operation is applied to each piece of data.
Task parallelism: Threads are distributed across cores, with each thread performing a unique operation.

CPUs provide hardware threads per core, which helps support multithreading by allowing multiple threads to run on a single core simultaneously.

Amdahl's Law identifies the potential gains in performance from adding more processors to an application that has both serial (non-parallel) and parallel components. It highlights the limitations of parallel processing based on the portion of the program that cannot be parallelized.

The serial portion of an application disproportionately affects performance gains when adding more cores, as it limits how much of the program can benefit from parallel execution.

User threads are managed by a user-level thread library, such as Pthreads, Windows threads, or Java threads.

Kernel threads are supported by the kernel and are used by most general-purpose operating systems, such as Windows, Linux, UNIX, and macOS.

The key multithreading models include:
Many-to-One Model: Multiple user threads are mapped to a single kernel thread. If one thread blocks, all threads block. No parallelism is possible. Examples include Solaris green threads and GNU portable threads.
One-to-One Model: Each user thread is mapped to a kernel thread. This model allows more concurrency, but thread creation may be limited due to overhead. Examples include Windows and Linux.
Many-to-Many Model: Multiple user threads are mapped to multiple kernel threads, allowing better scalability and concurrency. Examples include Solaris (prior to version 9).
Two-Level Model: Similar to the many-to-many model but allows user threads to be bound to specific kernel threads. Examples include IRIX and HP-UX.

In the Many-to-One model, multiple user threads are mapped to one kernel thread. The drawback is that if one thread blocks, all threads block, and no parallelism is possible because only one thread can be in the kernel at a time.

In the One-to-One model, each user thread is mapped to a kernel thread, allowing more concurrency. However, creating a new user thread also creates a kernel thread, which can lead to overhead, and some systems limit the number of threads per process due to this.

The Many-to-Many model allows multiple user threads to be mapped to multiple kernel threads, giving the operating system flexibility in managing thread resources and allowing for better scalability.

The Two-Level model is similar to the Many-to-Many model, but it also allows user threads to be bound to specific kernel threads. This provides greater flexibility and control over thread execution.

Thread libraries provide an API for creating and managing threads. These libraries can be implemented either in user space or with kernel-level support. Examples include Pthreads, Windows threads, and Java threads.

Pthreads, or POSIX threads, can be implemented at the user or kernel level. They specify the behavior of a thread library and are commonly used in UNIX systems. Examples of Pthread functions include:
pthread_create(): To create a new thread.
pthread_join(): To wait for a thread to complete.
pthread_exit(): To terminate a thread.

Java threads are managed by the Java Virtual Machine (JVM) and implemented using the thread model provided by the underlying operating system. They are created by extending the Thread class or implementing the Runnable interface.

As the number of threads grew, manually managing them became difficult. It became the job of compilers and runtime libraries to manage threads, making threading more efficient and less error-prone.

A thread pool creates a fixed number of threads that wait for work. Using an existing thread from the pool is faster than creating a new one. It also binds the number of threads in an application to the size of the pool, allowing for different strategies for running tasks.

OpenMP is a set of compiler directives and an API for C, C++, and FORTRAN that identifies parallel regions (blocks of code that can run in parallel) and provides support for parallel programming in shared-memory environments, creates as many threads as there are cores.

Grand Central Dispatch (GCD) is used in Mac OS and iOS to handle parallelism and multithreading. It identifies parallel sections, manages most threading details, and places code blocks in dispatch queues for execution. Assigned to available thread in thread pool when removed from queue

Serial queues: Blocks are removed in FIFO (First In, First Out) order, with each process having a main serial queue.
Concurrent queues: Blocks can be removed in parallel, allowing multiple blocks to be executed at once. GCD provides three system-wide concurrent queues with different priority levels (low, default, high).

Threading issues can occur during parallel execution. Examples include:
Behavior of fork() and exec() system calls.
Signal handling (synchronous and asynchronous). Notify a process when a specific event has occurred. A signal handler processes these signals and can either be the default handler run by the kernel or a user-defined handler.
Thread cancellation (asynchronous or deferred).
Thread-local storage (TLS).

A signal is generated by an event.
The signal is delivered to a process.
The signal is handled by a signal handler, which could be the default kernel handler or a user-defined one.

It is usually faster to service a request with an existing thread than to create a new one.
It binds the number of threads in the application to the size of the pool.
It separates the task to be performed from the mechanics of creating the task, allowing different strategies for running the task (e.g., tasks can be scheduled to run periodically).

The Windows API supports thread pools, allowing for efficient task management and execution.

fork() behavior: Some UNIX systems have two versions of fork(). One version duplicates all threads, and the other duplicates only the thread that invoked the fork() system call.
exec() behavior: exec() usually replaces the running process, including all threads, with the new program.

Signals are used to notify a process that an event has occurred. A signal handler processes the signal, and it can be either the default handler provided by the kernel or a user-defined handler.

Possible options include:
Deliver the signal to the thread to which the signal applies.
Deliver the signal to every thread in the process.
Deliver the signal to certain threads in the process.
Assign a specific thread to receive all signals for the process.

Asynchronous cancellation: Immediately stops the target thread.
Deferred cancellation: Allows the target thread to periodically check if it should be canceled.

In Pthreads, a thread must have cancellation enabled for the cancellation to take effect. The default cancellation type is deferred, meaning the thread is canceled when it reaches a cancellation point and invokes the cleanup handler.

TLS allows each thread to have its own copy of data, which is useful when you don't control thread creation. TLS data exists across multiple function calls for a specific thread, unlike local variables, which are visible only during individual function calls. TLS is similar to static data.

The OS maximizes CPU utilization through multiprogramming, where processes alternate between CPU bursts (computation) and I/O bursts (waiting for input/output). The CPU scheduler allocates CPU time to processes, while a dispatcher handles the actual switching of processes to ensure efficient CPU usage.

Process execution consists of a cycle of CPU bursts followed by I/O bursts. During a CPU burst, the process performs computations, and during an I/O burst, it waits for input or output operations to complete.

Short-term scheduler selects from among the processes in ready queue, and allocates the CPU to one of them. It makes decisions when a process switches from running to waiting, running to ready, waiting to ready, or terminates.

Non-preemptive scheduling: Happens only when a process transitions from running to waiting or waiting to ready. The process is not interrupted.
Preemptive scheduling: Can interrupt a process to allocate CPU time to another process and needs special care for handling shared data, kernel mode, and interrupts during OS activities.

The dispatcher gives control of the CPU to the process selected by the short-term scheduler. It performs tasks such as switching context, moving from kernel to user mode, and jumping to the correct location in the user program to resume execution.

Dispatch latency is the time it takes for the dispatcher to stop one process and start another.

The OS uses several criteria to evaluate CPU scheduling algorithms:
CPU utilization: Measures how busy the CPU is.
Throughput: The number of processes completed in a given time period.
Turnaround time: The total time it takes for a process to complete, from submission to termination.
Waiting time: The total time a process spends waiting in the ready queue.
Response time: The time it takes from submitting a request until the first response is produced.

CPU utilization measures how busy the CPU is, with the goal of keeping the CPU as busy as possible to maximize efficiency.

Throughput is the number of processes that complete their execution per unit of time

Turnaround time is the total time taken to execute a particular process, including the time spent waiting in memory, waiting in the ready queue, executing on the CPU, and performing I/O operations.

Waiting time is the amount of time a process spends waiting in the ready queue before it gets CPU time.

Response time is the time from when a request is submitted until the system produces the first response. This is important in time-sharing environments where user interaction (UI) is involved.

The goals are to maximize CPU utilization and throughput while minimizing turnaround time, waiting time, and response time.

FCFS scheduling executes processes in the order they arrive. It can lead to a "convoy effect," where short processes get stuck behind long ones, resulting in inefficient CPU usage.

SJF scheduling selects the process with the shortest CPU burst time to execute next. It provides the minimum average waiting time but is difficult to implement because the length of the next CPU burst must be estimated.

In preemptive SJF, the process with the shortest remaining CPU burst time is executed next. If a new process arrives with a shorter CPU burst time, the OS preempts the currently running process and switches to the new one.

In priority scheduling, each process is assigned a priority number, and the CPU is allocated to the process with the highest priority. SJF is a special case of priority scheduling where priority is inversely proportional to CPU burst time. A potential issue is starvation, where low-priority processes may never execute. The solution is aging, where the priority of a process increases over time.

RR scheduling allocates a small unit of CPU time (time quantum) to each process. Once the time has elapsed, the process is preempted and added to the end of the ready queue. It provides better response time but has the worst average turnaround time if the time quantum is too large or too small.

If the time quantum is large, RR behaves like FCFS. If it is small, there may be too many context switches, leading to overhead. The optimal time quantum should be larger than 80% of CPU bursts.

In multilevel queue scheduling, processes are divided into multiple queues, each with its own scheduling algorithm. For example, interactive processes may use Round Robin in the foreground queue, while batch processes use FCFS in the background queue. Scheduling must also occur between the queues.

Multilevel feedback queue scheduling allows processes to move between queues based on their behavior. . It defines parameters such as the number of queues, scheduling algorithms for each queue, and methods to promote or demote processes between queues. Aging can be implemented to prevent starvation. Processes that do not finish within a time quantum can be moved to a lower-priority queue.

Kernel-level threads are scheduled by the OS, and they compete with all threads in the system (system contention scope - SCS). User-level threads are managed within the process and can be scheduled according to user-defined criteria.

Admission control ensures that the system only accepts processes that can meet their deadlines. If a new process would cause the system to miss a deadline, it is not admitted.

PCS refers to the scope where user-level threads compete for CPU time within the same process. It is usually managed by the programmer who sets priorities for threads.

SCS is when kernel-level threads compete with all threads in the system. It is managed by the operating system and typically used in systems like Windows, Linux, and Solaris.

The key challenges include managing interrupt latency (time between interrupt arrival and start of service) and dispatch latency (time it takes to stop the current process and switch to a new one). Real-time scheduling also needs to prioritize tasks based on deadlines, especially for hard real-time systems where tasks must be completed by a strict deadline.

The two phases are:
Preemption of any process running in kernel mode.
Release of resources held by low-priority processes, allowing high-priority processes to proceed.

RMS is a static priority scheduling algorithm where tasks with shorter periods are given higher priority. It is the best static priority algorithm for periodic tasks but can miss deadlines if CPU utilization exceeds a certain threshold.

EDF is a dynamic scheduling algorithm that prioritizes tasks with the earliest deadlines, adjusting priorities as tasks approach their deadlines.

Proportional Share Scheduling allocates CPU time based on shares assigned to each process. Each process receives a proportion of CPU time according to the number of shares it holds.

POSIX real-time scheduling defines two main scheduling classes for real-time threads:
SCHED_FIFO: A first-come, first-served algorithm with no time slicing for threads of equal priority.
SCHED_RR: Similar to SCHED_FIFO but with time slicing for threads of equal priority.
SCHED_OTHER

The Completely Fair Scheduler (CFS) is a scheduling algorithm in Linux that prioritizes tasks based on their virtual runtime (vruntime) rather than fixed time slices. It uses scheduling classes, where each class has a specific priority. The scheduler picks the task with the highest priority from the highest scheduling class. Instead of using a fixed quantum, CFS calculates the quantum based on the proportion of CPU time and the task's nice value (ranging from -20 to +19, with lower values indicating higher priority). CFS supports two default scheduling classes: default and real-time, with the option to add other

Queueing models describe the probabilistic arrival of processes and their CPU/I/O bursts. By knowing arrival rates and service rates, the model computes metrics like average throughput, utilization, waiting time, and queue length

Little's Formula relates the average queue length (n), average arrival rate (λ), and average waiting time (W) in a steady-state system: n = λ × W. It helps calculate queue metrics in a system.

The most accurate way is to implement the scheduler in a real system and observe its performance. However, this method is high-cost and high-risk.

Process synchronization ensures the consistency of shared data when multiple processes access the same resources. It addresses the critical section problem to prevent data inconsistencies.

The length of the next CPU burst can be estimated by using the length of previous CPU bursts, often with exponential averaging.

tn = actual length of nth CPU burst
τn = predicted value for the last CPU burst
τn+1 = predicted value for the next CPU burst
α, 0 ≤ α ≤ 1

Τn+1 = α(tn) + (1 - α)Τn
Typically, α is set to ½.

PTHREAD_SCOPE_PROCESS (PCS): Schedules threads within a single process.
PTHREAD_SCOPE_SYSTEM (SCS): Schedules threads across the entire system.
Note: Some operating systems, like Linux and macOS, only support SCS.

In real-time scheduling, the scheduler must support preemptive, priority-based scheduling. This guarantees soft real-time performance, but for hard real-time systems, it must also ensure tasks meet their deadlines.

Linux version 2.5 moved to O(1) scheduling time, making it preemptive and priority-based. It had two priority ranges: 0-99 for real-time tasks and 100-140 for nice values. Higher priority tasks received larger time slices, and tasks were organized into two priority arrays (active and expired).

Deterministic modeling is an analytic evaluation method that applies a specific, predetermined workload to evaluate the performance of various CPU scheduling algorithms. It calculates metrics like average waiting time for each algorithm.

Simulations create a programmed model of the system and run it under different scheduling algorithms. Performance data is gathered using random number generators and distributions to drive the simulation. Simulations provide more accurate performance metrics than analytical models.

When concurrent processes share data, there is a risk of data inconsistency if data is accessed or modified simultaneously. This leads to a race condition, where the final outcome depends on the execution order, which can result in incorrect data updates or results.

The Producer-Consumer problem occurs when the producer increments a counter while the consumer decrements it. If both processes access the counter simultaneously, it can lead to a race condition, resulting in incorrect values.

The Critical Section Problem occurs when multiple processes need access to shared resources. To prevent conflicts, no two processes can be in their critical section (the part of the code where shared data is accessed) at the same time.

A process generally has three sections:
Entry section: Requests permission to enter the critical section.
Critical section: The section of code where shared resources are accessed.
Exit section: Signals that the process has finished using the shared resources.

Peterson's solution is a simple software algorithm for two processes that ensures mutual exclusion. It uses two shared variables: a flag array and a turn variable to communicate which process is allowed to enter the critical section. It satisfies mutual exclusion, progress, and bounded waiting. In Peterson's Solution, process i enters the critical section only if flag[j] = false or turn = i, ensuring mutual exclusion;

Multiprocessor systems use special atomic instructions such as test-and-set and compare-and-swap which allows for non-interruptible operations, to ensure that only one process can enter its critical section at a time, preventing race conditions.

Test-and-set: Tests a memory location and sets its value in one atomic step.
Compare-and-swap: Compares a memory location to a value and swaps it with a new value if they match.

A semaphore is an integer variable used to control access to shared resources by multiple processes. It can be incremented or decremented using wait() and signal() functions to ensure safe access to shared data. It can be implemented with or without busy waiting. Unlike a mutex, a semaphore can manage more than one resource

Counting semaphore: Can range over an unrestricted domain and is used to manage multiple instances of a resource.
Binary semaphore: Can have only two values (0 or 1) and is used like a mutex lock.

Busy waiting occurs when a process continuously checks if it can enter the critical section. It is inefficient for long wait times but can be faster than sleeping and waking up when wait times are short.

Spinlocks are a simple synchronization mechanism where a process repeatedly checks if it can enter the critical section. Spinlocks are efficient for short wait times but waste CPU resources if wait times are long.

Semaphores can be implemented without busy waiting by associating a waiting queue with each semaphore. When a process must wait, it is blocked and placed in the semaphore's waiting queue. A wake-up() function removes a process from the waiting queue and moves it to the ready queue when the semaphore value allows it to proceed.

Deadlock occurs when two or more processes are indefinitely waiting for an event that can only be caused by one of the waiting processes. This results in the processes being unable to proceed.

A mutex lock ensures mutual exclusion by requiring processes to acquire the lock before entering their critical section and releasing it after exiting. It prevents multiple processes from accessing the critical section simultaneously.

Starvation occurs when a process is never removed from the semaphore queue in which it is suspended, meaning it may never get a chance to execute.

Priority inversion happens when a lower-priority process holds a lock needed by a higher-priority process. It can be solved using the priority-inheritance protocol, where the lower-priority process temporarily inherits the higher priority to finish its task and release the lock.

The Bounded-Buffer Problem is a classical synchronization problem where producer processes place items into a buffer and consumer processes remove items from the buffer. Synchronization must ensure that producers and consumers do not modify the buffer simultaneously, avoiding race conditions.

In the Bounded-Buffer Problem, semaphores are used to synchronize producer and consumer processes. A semaphore empty tracks the number of empty slots in the buffer, full tracks the number of filled slots, and mutex ensures mutual exclusion when accessing the buffer. The producer process waits on empty and mutex before adding an item, and signals full after adding it. The consumer waits on full and mutex before removing an item, and signals empty after removing it

The Bounded-Buffer Problem uses three semaphores:
empty: Represents the number of empty buffer slots.
full: Represents the number of filled buffer slots.
mutex: Ensures mutual exclusion while accessing the buffer

The Readers-Writers Problem involves shared data accessed by multiple readers and writers. Multiple readers can read simultaneously, but no reader and writer should access the data at the same time. Writers must have exclusive access to modify the data.

In the Readers-Writers Problem, semaphores are used to synchronize access to shared data between reader and writer processes. A rw_mutex semaphore ensures mutual exclusion for writers, allowing only one writer or multiple readers to access the data at any time. A mutex semaphore is used to update the reader count safely

rw_mutex: Ensures that either one writer or multiple readers can access the data but not both simultaneously.
mutex: Protects access to the shared reader count variable, ensuring mutual exclusion when updating the reader count;

The Dining Philosophers Problem involves five philosophers who alternately think and eat. To eat, they need two chopsticks, one from the left and one from the right. The problem can lead to deadlock if all philosophers pick up one chopstick and wait indefinitely for the other.

In the Dining Philosophers Problem, semaphores are used to avoid deadlock and ensure that philosophers can only pick up chopsticks (represented as semaphores) when both are available. A semaphore for each chopstick ensures that only one philosopher can hold a chopstick at a time. An additional solution might involve limiting the number of philosophers allowed to pick up chopsticks simultaneously to avoid circular waiting

The Dining Philosophers Problem uses one semaphore for each chopstick. Each philosopher must wait for both semaphores (representing the left and right chopsticks) before eating. After eating, the philosopher signals (releases) the semaphores to make the chopsticks available for other philosophers

Possible solutions include:
Allowing at most four philosophers to sit at the table simultaneously.
Allowing a philosopher to pick up both chopsticks only if both are available.
Using an asymmetric solution where odd-numbered philosophers pick up the left chopstick first, and even-numbered philosophers pick up the right chopstick first.

Windows provides:
Interrupt-masks for protecting access to global resources in uniprocessor systems.
Spinlocks for ensuring that a thread holding a lock cannot be preempted in multiprocessor systems.
Dispatcher objects that act as mutexes, semaphores, events, and timers.

Linux provides:
Preemptive and non-preemptive kernels.
Semaphores, atomic integers, spinlocks, and reader-writer locks.
In single-CPU systems, spinlocks are replaced by enabling and disabling kernel preemption.

Pthreads are OS-independent and provide:
Mutex locks and condition variables to block threads until conditions are met.
Non-portable extensions include read-write locks and spinlocks.

A deadlock occurs when processes are unable to proceed because they are waiting for resources held by other processes. Deadlock arises when the following four conditions hold simultaneously: mutual exclusion, hold and wait, no preemption, and circular wait.

Mutual exclusion: A resource can only be held by one process at a time.
Hold and wait: A process holding at least one resource is waiting to acquire additional resources held by other processes.
No preemption: Resources cannot be forcibly taken from a process.
Circular wait: A circular chain of processes exists where each process is waiting for a resource held by the next process in the chain.

Resource Allocation Graphs help visualize the allocation of resources and waiting processes. If the graph contains a cycle, it indicates the possibility of a deadlock, especially in systems using synchronization mechanisms like mutex locks.

Claim edge Pi → Rj indicated that process Pi may request resource Rj; represented by a dashed line
Claim edge converts to request edge when a process requests a resource
Request edge converted to an assignment edge when the resource is allocated to the process
When a resource is released by a process, assignment edge reconverts to a claim edge
Resources must be claimed a priori in the system

The three issues are Mutual Exclusion, Progress, and Bounded Waiting

Mutual Exclusion ensures that if a process is executing in its critical section, no other processes can be executing in their critical sections

Progress ensures that if no process is in its critical section and some processes want to enter, the selection of the next process cannot be postponed indefinitely

Bounded Waiting guarantees that a bound exists on the number of times other processes can enter their critical sections after a process requests to enter its critical section before that request is granted

The two approaches are Preemptive (allows preemption in kernel mode) and Non-preemptive (process runs until it exits kernel mode, blocks, or yields the CPU).

The test-and-set() instruction locks a shared boolean variable and allows a process to enter the critical section if the lock is available. Once the process exits, the lock is released.

The two operations are wait() (decreases the semaphore value) and signal() (increases the semaphore value).

Each entry in the waiting queue has two data items: an integer value and a pointer to the next record in the list.

The three methods are:
Deadlock prevention or avoidance: Ensures that deadlock never occurs.
Deadlock detection and recovery: Allows deadlock to occur but detects and resolves it.
Ignore the problem: Pretends deadlocks never occur, which is used by many OS, including UNIX;

Deadlock prevention modifies the way processes request and hold resources, ensuring that one or more of the conditions necessary for deadlock are not satisfied. Mutual exclusion is not required for shareable resources so only enforce it when necessary

For example, processes may request all resources at once, or allow process to request resources only when the process has none allocated to it. Suffers from Low resource utilization since processes are holding resources they aren't immediately using; starvation possible

Deadlock avoidance ensures that the system only grants resource requests if doing so will keep the system in a safe state. It requires knowledge of the maximum resources a process might request and continuously evaluates the system's resource allocation state to avoid circular wait

A system is in a safe state if there is a sequence of processes such that each process can complete its tasks with the currently available resources or by resources released by other processes. If a system is in a safe state, no deadlock will occur

The Banker's algorithm is used to allocate resources safely by checking if granting a resource request keeps the system in a safe state. It simulates resource allocation to ensure no circular wait condition will arise, ensuring that deadlock is avoided

Deadlock can occur if two threads or processes acquire mutex locks in different orders and then wait for the other to release a lock, causing a circular wait situation

A resource-allocation graph is a directed graph used to represent processes and resources in a system. The graph contains edges that show requests for resources and assignments of resources to processes. Cycles in the graph can indicate deadlock

If a resource-allocation graph contains no cycles, there is no deadlock. If a cycle exists and there is only one instance per resource type, a deadlock has occurred. If there are multiple instances, a cycle indicates the possibility of a deadlock

Deadlock detection involves checking for cycles in a wait-for graph or examining resource allocation matrices. If a cycle is found, a deadlock has occurred, and recovery procedures must be initiated

A wait-for graph is a simplified version of a resource-allocation graph where edges represent processes waiting for other processes to release resources. A cycle in the wait-for graph indicates a deadlock

An algorithm to detect a cycle in a graph requires an order of n^2 operations

The two approaches are:
Process termination: Abort one or more deadlocked processes to break the deadlock cycle.
Resource preemption: Force processes to release resources, potentially rolling them back to a safe state or restarting them

The safety algorithm checks if the system is in a safe state by simulating the allocation of requested resources and verifying that all processes can eventually complete their tasks. If the system remains in a safe state, resources are allocated, otherwise, the request is denied

Criteria for selecting a victim process may include process priority, the amount of work completed, the resources the process holds or needs, and the overall system cost of aborting or rolling back the process

A process utilizes a resource in three steps: request, use, and release

Deadlock can occur when multiple threads acquire mutex locks in different orders. For example, if thread one locks mutex A and then tries to lock mutex B while thread two locks mutex B and tries to lock mutex A, both threads can be deadlocked

Available: A vector of available resources.
Max: A matrix that defines the maximum resources each process may request.
Allocation: A matrix that defines the resources currently allocated to each process.
Need: A matrix that shows the remaining resources each process still requires (Need = Max - Allocation);

The deadlock detection algorithm follows these steps:
Initialize vectors Work and Finish.
Find a process that is not finished and whose request can be satisfied with available resources.
Simulate allocation of resources, mark the process as finished, and repeat.
If any process is still unfinished, a deadlock has occurred

Algorithm requires an order of O(m x n^2) operations to detect whether the system is in deadlocked state

Single instance or resource type use graph, multiple use Banker's algorithm

Each process must a priori claim maximum use
When a process requests a resource it may have to wait
When a process gets all its resources it must return them in a finite amount of time