Operating System: Purpose, Multiprogramming & Time-Sharing

Purposes of an Operating System

• Provides a user-friendly environment for program execution.
• Manages I/O device operations and control.
• Supervises user program execution, preventing errors.
• Controls computer resources and provides a base for application creation.

Multiprogramming Systems

• Several programs reside in memory simultaneously.
• Enables task switching for efficient processing and reduces idle time.
• Increases CPU and I/O utilization.
• Achieves efficiency by overlapping CPU and I/O demands from different users.
• Maximizes CPU use by having something ready to execute.
• Increases I/O utilization by running multiple tasks on different I/O devices.

Time-Sharing (Multitasking) Systems

• Allow users to perform multiple tasks at once using scheduling and multiprogramming.
• Enables interactive systems for multiple users.
• Rapidly switches the CPU between users.
• Programs read inputs from the terminal, with output displayed immediately.
• Increases CPU and I/O utilization, allows user interaction, and provides short response times.
• User programs experience quick response times, often in milliseconds, even with concurrent programs.
• Implemented by giving each user a time-share in round-robin fashion, with jobs continuing until the time-slice ends.
• CPU switches between jobs when the current process waits for an event, like I/O, without requiring timer interrupts.
• A context switch will occur when a job needs to wait.

Security in Multiprogramming and Time-Sharing Environments

• Multiple users sharing a system can lead to security issues.
• Problems include stealing or copying programs/data and unauthorized use of system resources like CPU, memory and disk space.
• Achieving the same level of security as in a dedicated machine is unlikely due to the fallibility of protection schemes.
• More complex schemes are harder to fully trust.

Operating Systems as Interrupt-Driven

• The OS waits for an event (signalled by an interrupt) when idle.
• This happens when no processes are running, no I/O is being serviced, and no users are interacting.

Privilege Instructions

• Hardware instructions executable only in monitor/system/supervisory mode.

Implementation of Privilege Instructions

• Hardware adds a mode bit: '1' for monitor, '0' for user mode.
• One bit differentiates between privilege and non-privilege instructions in each machine code.
• The OS sets the bit to user mode before giving control to user programs.
• Hardware switches the bit to monitor mode during a trap or interrupt.
• The OS can also set the bit to the system mode.

Hardware Response to Privilege Instruction Attempts in User Mode

• Hardware identifies it as an illegal instruction.
• The hardware sends a trap to the OS.

Privileged Instructions and Consequences of Not Privileging

• Set Value of Timer: Privileged, or users can change the timer, disrupting correct system operation.
• Read the Clock: Not privileged.
• Clear Memory: Privileged, or users could accidentally/intentionally delete memory.
• Turn-Off Interrupts: Privileged, or users could crash the system by turning off interrupts.
• Switch from User to Monitor Mode: Privileged; otherwise, all users can access system resources.
• Modifying Base and Limit Registers: Privileged, or users can increase their memory allocation.
• Issue a Trap Instruction: Not privileged, as system calls are traps used by user processes..
• Access I/O Device: Privileged, otherwise novice users may attempt damaging I/O device access.
• **Modify Entries in Device-Status Table: Privileged; modifying OS-managed device info can damage the system.

System Calls

• Allow user-level processes to request OS services, including I/O instructions.
• Parameters are passed to the OS, in a register, in a memory location or in a stack

Unix System Calls Categories

• Process Control
• File Manipulation
• Device Manipulation
• Information Maintenance
• Communication

Context Switch Actions

• Saving the current process state to its Process Control Block (PCB).
• Loading the next state into the processor registers from the PCB.
• Updating the Program Counter to the next instruction for execution.

Information for Context Switching

• Process State
• Program Counter
• CPU Registers
• CPU Scheduling Information
• Memory Management Information
• Accounting Information

Process Creation

• A code with three fork() calls creates 8 processes.
• The first fork() duplicates the process, then the next fork() creates four.
• The final fork() creates eight processes because each of the four turns into two.

Zombie Processes

• Completed processes still with an entry in the process table to store its exit status for the parent process.
• Consume system resources, which mainly comprise process table entries, potentially leading to resource exhaustion.
• Terminate when parent processes read their exit status using wait() or when the parent process terminates, which then init() cleans them up.

Inter-Process Communication (IPC)

• Cooperating processes use interprocess communication mechanisms.

Shared Memory vs. Message Passing

• Shared memory: Processes read/write directly to a memory area, which also requires synchronization.
• Message Passing is processes sending and receiving messages through the kernel which is secure and easier to manage but has overhead.

OS Responsibilities in IPC

• Shared memory: OS manages creation, destruction, and synchronization of segments.
• Message passing: OS handles transmission, reception, message queues, synchronization, process blocking.

Message-Passing Methods

• Synchronous: Sender/receiver blocked until operation completes.
• Asynchronous: Process continues execution.
• Automatic Buffering: OS stores messages until receiver is ready.
• Explicit Buffering: Processes manage message storage.
• Send by Copy: Copies entire message ensuring data safety (slow).
• Send by Reference: Passes reference - faster, but risk of data issues.
• Fixed-Size Messages: Simplify buffer management - can waste space or limit message size.
• Variable-Size Messages: More flexible, requires more complex management.

Threads: User-Level vs. Kernel-Supported

• User-Level Threads:
  • Managed by a library at the user level, not visible to the kernel.
  • Faster to create and manage because they don't involve system calls.
• Kernel-Supported Threads:
  • Managed directly by the OS, scheduled separately.
  • Can utilize multiple processors effectively for true parallelism.

Threads: Advantages and Disadvantages

• User-Level Threads:
  • Advantages: Less overhead, faster context switches.
  • Disadvantages: Lack true concurrency on multiprocessor systems, blocking operations can block the whole process.
• Kernel-Supported Threads: -Advantages: Better CPU utilization, true concurrency. -Disadvantages: Higher overhead due to system calls for operations and context switches involving the kernel.

Critical Section

• Ensures only one process works at a time within a code segment.
• The critical-section problem makes it so no other process is allowed to execute in their critical section when one process is already in it.

Requirements for Critical-Section Problem Solutions

• Mutual Exclusion: Ensures only one process accesses a shared resource at a time, therefore, no others can execute in their critical sections.
• Progress: If no process is in its critical section, only processes not their remainder section should participate in deciding which enters next.
• Bounded Waiting: Sets a limit on a process's wait time to enter; setting the number of other processes that can enter their section before the request is granted.

Atomic Instructions

• Defined as instructions that execute completely without interruption.
• Without atomic execution, mutual exclusion can be violated, which compromises synchronized operations.

Three Requirements for the Critical Section

• Mutual exclusion
• Progress condition
• Bound waiting

Spinlocks

• Synchronization mechanism where a thread checks a lock in a loop until available instead of blocking.
• Spinlocks implemented using atomic instructions lead to fast locking/unlocking.
• These have low overhead for critical sections.
• Spinlocks can waste CPU cycles in high contention or single-core scenarios.

Use of Spinlocks

• Solaris, Linux, and Windows 2000 utilize it on multi-processor systems.

Semaphore Code Example

Assume Initially
Q=1
S1
wait(Q)
S2
signal(Q)
S3

Pthread Functions

• *int pthread_mutex_lock(pthread_mutex_t mutex);
  • Used before accessing a shared variable to lock it.
• *int pthread_mutex_unlock(pthread_mutex_t mutex);
  • Used after finishing with a shared variable to unlock it.

Scheduling Types

• Short-term (CPU scheduler): Selects from memory and allocates the CPU.
• Medium-term: For swapping in time-sharing systems.
• Long-term (job scheduler): Determines which jobs are brought to memory.

I/O-Bound vs. CPU-Bound

• I/O-bound programs: Small computation before I/O, do not use the entire CPU quantum.
• CPU-bound programs: Fully use CPU without blocking I/O.
• Prioritizing and allowing I/O-bound programs to go first means better resource use.

Process State Transitions

• Waiting -> Running is illegal, must fire be placed in the ready queue before selection.
• Running -> Waiting is legal if requesting a resource.
• Ready -> Waiting is illegal, can only transition from Running.

Optimizing Response Time

• Optimizing response time speeds operations, optimizing CPU usage.

Result of Shortest Job First and Priority-Based

• Can result in starvation, denying CPU time to lower-priority and those with long process times.

Round Robin Algorithm with Two PCB Pointers Effect

• The process would run twice as many times.

Round Robin Algorithm with Two PCB Pointers Advantages

• Prioritization of important processes.
• Prevention of lower-priority processes from being starved.
• It does not require changes to the scheduling algorithm.

Round Robin Algorithm with Two PCB Pointers Disadvantages

• Context switching impact increases.
• Removing processes becomes significantly harder.

Altering the basic Round Robin Algorithm Without Duplicates

• Increase the quantums.

CPU utilization for Round-Robin When Time Quantum is 1 millisecond

• Scheduler incurs 0.1ms of context-switching.
• CPU utilization is about 91%.

CPU utilization for Round-Robin When Time Quantum is 10 millisecond

• CPU utilization is 94% because I/O Tasks incur context switch after 1 millisecond.

Formulas for computing Time Bursts for Scheduling

• ( 8 + (12 - 0.4) + (13 - 1)) / 3 = 10.53
• ( 8 + (9 - 1) + (13 – 0.4)) / 3 = 9.53
• ((2 - 1) + ( 6 – 0.4 ) + ( 14 - 0)) / 3 = 6.87