Computer-system - One or more CPUs, device controllers connect through common bus providing access to shared memory

operation - I/O devices and the CPUs can execute concurrently

- The device controller (on device) determines the logical interaction between the device and the computer, each device has a local buffer
- CPU moves data from/to main memory to/from local buffers, I/O device does from the device to local buffer of controller
Interrupt - Interrupt transfers control to the interrupt service routine generally, through the interrupt vector, which contains the addresses of all the service routines
- Interrupt architecture must save the address of the interrupted instruction
- A trap or exception is a software-generated interrupt caused either by an error or a user request
- An operating system is interrupt driven
- Some device use interrupts when the I/O rate is low and switch to polling when the rate increases to the point where polling is faster and more efficient
I/O Structure - Two methods for handling I/O : wait and without wait for I/O completion
- After I/O starts, control returns to user program only upon I/O completion: Wait instruction idles the CPU until the next interrupt, Wait loop (e.g., contention for memory access), At
most one I/O request is outstanding at a time, no simultaneous I/O processing
- After I/O starts, control returns to user program without waiting for I/O completion: System call – request to the OS to allow user to wait for I/O completion , Device-status table
contains entry for each I/O device indicating its type, address, and state.
- OS indexes into I/O device table to determine device status and to modify table entry to include interrupt
Storage - Main memory: RAM (Random Access), DRAM (Dynamic), usually volatile
- Secondary Storage: HDD (Hard Disk Drives), nonvolatile, Disk surface is logically divided into tracks, which are subdivided into sectors. Nonvolatile Memory Devices (NVM), faster than
hard disks, nonvolatil.
- Hierachy: organized according to Speed(access time), Capacity, Volatility, Cost
- Caching: mechanism copying data into faster storage system, main memory can be viewed as a cache for secondary storage.
- Ranking (Large -> Small, Slow -> Fast): Magnetic Tapes -> Optical Disk -> HDD -> NVM -> Main Mem -> Cache -> Registers
Direct Memory - Used for high-speed I/O devices able to transmit information at close to memory speeds
Access Structure - Device controller transfers blocks of data from local buffer directly to main memory without CPU intervention
(DMA) - Only one interrupt is generated per block, rather than the one interrupt per byte
OS Operation - Bootstrap program – simple code to initialize the system, load the kernel: Kernel loads, Starts system daemons (services provided outside of the
kernel), Kernel interrupt driven (hardware and software), Hardware interrupt by one of the devices, Software interrupt (exception or trap): Software error (e.g., division by zero),
Request for operating system service – system call, Other process problems include infinite loop, processes modifying each other or the operating system
Multiprogramming - Single user cannot always keep CPU and I/O devices busy
Batch System - Multiprogramming organizes jobs (code and data) so CPU always has one to execute
-A subset of total jobs in system is kept in memory
- One job selected and run via job scheduling
- When job has to wait (for I/O for example), OS switches to another job
Multitasking, Time A logical extension of Batch systems– the CPU switches jobs so frequently that users can interact with each job while it is running, creating interactive computing: Response time should
sharing be < 1 second, Each user has at least one program executing in memory process , If several jobs ready to run at the same time->CPU scheduling, If processes don’t fit in memory,
swapping moves them in and out to run,Virtual memory allows execution of processes not completely in memory
Dual-mode Mode bit is provided by hardware ( Mode bit = user or Mode bit = Kernel)
Architecture - Multiprocessor: 2 types: Asymmetric Multiprocessing – each processor is assigned a special task. Symmetric Multiprocessing – each processor performs all tasks
- Dual core Design: multichip and multicore, system containing all the chips, chassis containing multiple separate systems
Cluster system Multiple systems working together: Usually sharing storage via a Storage-Area Network (SAN), Provides a high-availability service which survives failures (Asymmetric clustering has
one machine in hot-standby mode, Symmetric clustering has multiple nodes running applications), Some clusters are used for High Performance Computing (HPC), Applications must be
written to use parallelization, Some clusters have Distributed Lock Manager (DLM) to avoid conflicting operations
Computing - Traditional: Stand-alone general purpose machines(Portals provide web access to internal systems, Network computers (or thin clients) are like Web terminals, Mobile computers
Environment interconnect via wireless networks)
- Mobile: Such as handheld smartphones, tablets ( Extra feature – more OS features (e.g., GPS, gyroscope), Allows new types of apps like Augmented Reality (AR), Use IEEE 802.11
wireless, or cellular data networks for connectivity, Leaders are Apple iOS and Google Android)
- Client server: Dumb terminals supplanted by smart PCs(Many systems now servers, responding to requests generated by clients, Compute-server system provides an interface to
client to request services (i.e., database), File-server system provides interface for clients to store and retrieve files)
- Peer to peer (P2P): Another model of distributed system(P2P does not distinguish clients and servers, Instead all nodes are considered peers, May each act as client, server or both,
Node must join P2P network by Registers its service with central lookup service on network, or Broadcast request for service and respond to requests for service via discovery protocol
Examples include Napster and Gnutella, Voice over IP (VoIP) such as Skype)
- Cloud: Delivers computing, storage, apps as a service across a network,Logical extension of virtualization because it uses virtualization as the base for it functionality. Many types of
structure (Public cloud – available via Internet to anyone willing to pay, Private cloud – run by a company for the company’s own use, Hybrid cloud – includes both public and private
cloud components). Many types of services (Software as a Service (SaaS) – one or more applications available via the Internet, Platform as a Service (PaaS) – software stack ready for
application use via the Internet, Infrastructure as a Service (IaaS) – servers or storage available over Internet (i.e., storage available for backup use)). Composed of traditional OSes, plus
VMMs, plus cloud management tools. Internet connectivity requires security like firewalls. Load balancers spread traffic across multiple applications
- Real time embedded System: Real-time embedded systems most prevalent form of computers. Vary considerable, special purpose, limited purpose OS, realtime OS
SUMMARY:
CHAPTER 2: OS Structre
OS Service Operating systems provide an environment for execution of programs and services to programs and users
- User interface - Almost all operating systems have a user interface (UI). Varies between Command-Line Interface (CLI), Graphical User Interface (GUI), Touch-screen
- Program execution - The system must be able to load a program into memory, to run that program, and end execution, either normally or abnormally (error)
- I/O operations - A running program may require I/O, which may involve a file or an I/O device
- File-system manipulation - The file system is of particular interest. Programs need to read and write files and directories, create and delete them, search them, list file Information, permission
management.
- Communications – Processes may exchange information, on the same computer or between computers over a network Communications may be via shared memory or through message
passing (packets moved by the OS)
- Error detection – OS needs to be constantly aware of possible errors May occur in the CPU and memory, hardware, in I/O devices, in user program For each type of error, OS should take the
appropriate action to ensure correct and consistent computing Debugging facilities can greatly enhance the user’s and programmer’s abilities to efficiently use the system
- Resource allocation - When multiple users or multiple jobs running concurrently, resources must be allocated to each of them Many types of resources - CPU cycles, main memory, file
storage, I/O devices.
- Logging - To keep track of which users use how much and what kinds of computer resources
- Protection and security - The owners of information stored in a multiuser or networked computer system may want to control use of that information, concurrent processes should not
interfere with each other Protection involves ensuring that all access to system resources is controlled Security of the system from outsiders requires user authentication, extends to defending
external I/O devices from invalid access attempts
CLI, GUI - CLI or command interpreter allows direct command entry, Sometimes implemented in kernel, sometimes by system programs, Sometimes multiple flavors implemented – shells, Primarily
fetches a command from user and executes it, Sometimes commands built-in, sometimes just names of programs If the latter (name of program), adding new features doesn’t require shell
modification.
- GUI: User-friendly desktop metaphor interface( mouse, keyboard, and monitor, Icons represent files, programs, actions, etc, Various mouse buttons over objects in the interface cause various
actions providing information, options, execute function, open directory, Invented at Xerox PARC)
- Many systems now include both CLI and GUI interfaces
System call - Programming interface to the services provided by the OS, Typically written in a high-level language (e.g., C or C++), Mostly accessed by 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)
- Each system call is associated with a number, System-call interface maintains a table indexed according to these numbers.
- 3 types of parameter passing: registers, address, placed on stack.
- Types: Process control, File management, Device management, Info maintenance, Communication, Protection
OS Structures - Many structures: Simplest (MS-DOS), More complex (UNIX), Layered (abstraction), Microkernel (Mach)
Monolithic Structure - Original UNIX Layered Approach Micro Kernel Modules Hybrid
UNIX – limited by hardware The operating system is divided Moves as much from the kernel Many modern operating systems Most modern operating systems
functionality, the original UNIX into a number of layers (levels), into user space implement Loadable Kernel are actually not one pure model
operating system had limited each built on top of lower layers. Mach is an example of Modules (LKMs) Hybrid combines multiple
structuring. The UNIX OS consists of two The bottom layer (layer 0), is the microkernel Uses object-oriented approach approaches to address
separable parts : hardware; the highest (layer N) is Mac OS X kernel (i.e., Darwin) Each core component is separate performance, security, usability
Systems programs the user interface. partly based on Mach Each talks to the others over needs
Kernel Communication takes place known interfaces Linux and Solaris kernels in kernel
Consists of everything below the With modularity, layers are between user modules using Each is loadable as needed within address space, so monolithic,
system-call interface and above the selected such that each uses message passing model the kernel plus modular for dynamic loading
physical hardware functions (operations) and Benefits Overall, similar to layers but with of functionality
Provides the file system, CPU services of only lower-level Easier to extend a microkernel more flexible(Linux, Solaris, etc.) Windows mostly monolithic, plus
scheduling, memory management, and layers Easier to port the operating microkernel for different
other operating-system functions; a system to new architectures subsystem personalities
large number of functions for one level More reliable (less code is Apple Mac OS X hybrid, layered,
 running in kernel mode), more Aqua UI plus Cocoa
secure programming environment
Detriments:Performance Below is kernel consisting of
overhead of user space to kernel Mach microkernel and BSD Unix
space parts, plus
communication I/O kit and dynamically loadable
modules (called kernel
extensions)
SUMMARY:
CHAPTER 3: Process
Process - Program is passive entity stored on disk (e.g., executable file)
- Process is active entity
New – The process is being created
Running – Instructions are being executed
Waiting – The process is waiting for some event to occur
Ready – The process is waiting to be assigned to a processor
Terminated – The process has finished execution
PCB Process Control Block (PCB) – Information associated with each process, also called Task Control Block (TCB), includes:
- Process state – running, waiting, etc.
- Process number – identity of the process
- Program counter – location of instruction to next execute
- CPU registers – contents of all process-centric registers
- CPU scheduling info – priorities, scheduling queue pointers
- Memory-management information – memory allocated to the process
- Accounting information – CPU used, clock time elapsed since start, time limits s
- I/O status information/Open file list – I/O devices allocated to process, list of open files
Context switch When CPU switches to another process, the system must save the state of the old process and load the saved state for the new process via a context switch
Context of a process represented in the PCB Context-switch time is overhead, the system does no useful work while switching The more complex the OS and the PCB, the longer the
context switch
Process termination - Process executes last statement and then asks the operating system to delete it using the exit() system call. Parent may terminate the execution of children processes using the abort()
system call. Some reasons for doing so: The parent is exiting and the operating systems does not allow a child to continue if its parent terminates
- Cascading termination: All children, grandchildren, etc. are terminated
- The parent process may wait for termination of a child process by using the wait() system call. The call returns status information and the pid of the terminated process
ü pid = wait(&status);
ü waitpid() suspends execution of the calling process until a child specified by pid argument has changed state
If no parent waiting (did not invoke wait()), process is a zombie
If parent terminated without invoking wait(), process is an orphan

Inter Process Processes within a system may be independent or cooperating

Communication IPC SHARED MEMORY MESSAGE PASSING
- An area of memory shared among the processes that wish to communicate The Direct communication Indirect Communication
communication is under the control of the users processes, not the operating system. - Processes must name each other - Messages are directed and received from
- Major issues is to provide mechanism that will allow the user processes to synchronize explicitly: mailboxes (also referred to
their actions when they access shared memory. send (P, message) – send a message to as ports)
- Producer-Consumer relationship : Paradigm for cooperating processes, producer process P o Each mailbox has a unique ID
process produces information that is consumed by a consumer process unbounded- receive(Q, message) – receive a message o Processes can communicate only if they
buffer places no practical limit on the size of the buffer from process Q share a mailbox
bounded-buffer assumes that there is a fixed buffer size - Properties of communication link - Properties of communication link
o Links are established automatically o Link established only if processes share a
o A link is associated with exactly one pair common mailbox
of communicating processes o A link may be associated with many
o Between each pair there exists exactly processes
one link o Each pair of processes may share several
o The link may be unidirectional, but is communication links
usually bi-directional o Link may be unidirectional or bi-
O Fast, difficult to implement directional
O Slower, system overhead for every
message, easy to implement
Message passing - - Message passing may be either blocking or non-blocking
Synchronization - A valid message, or Null message Different combinations possible
- If both send and receive are blocking, we have a rendezvous
BLOCKING NON BLOCKING
- Blocking is considered synchronous - Non-blocking is considered asynchronous
- Blocking send – the sender is blocked until the message is received - Non-blocking send – the sender sends the message and continue
- Blocking receive – the receiver is blocked until a message is available - Non-blocking receive – the receiver receives:
Buffering Queue of messages attached to the link. Implemented in one of three ways
- Zero capacity – no messages are queued on a link Sender must wait for receiver (rendezvous)
- Bounded capacity – finite length of n messages Sender must wait if link full
- Unbounded capacity – infinite length Sender never waits
Pipes Acts as a conduit allowing two processes to communicate
- Ordinary pipes – cannot be accessed from outside the process that created it. Typically, a parent process creates a pipe and uses it to communicate with a child process that it created.
- Named pipes – can be accessed without a parent-child relationship.
- Ordinary Pipes allow communication in standard producer-consumer style Producer writes to one end (the write-end of the pipe) Consumer reads from the other end (the read-end of
the pipe)Require parent-child relationship between communicating processes
- Named pipes are more powerful than ordinary pipes Communication is bidirectional No parent-child relationship is necessary between the communicating processes
Socket, A socket is defined as an endpoint for communication. It is a concatenation of IP address and port – a number included at start of message packet to differentiate network services on a
Communication in host
client server E.g., The socket [Link]:1625 refers to port 1625 on host [Link]
- All ports below 1024 are well known, used for standard services
- Special IP address [Link] (loopback) to refer to system on which process is running
- Three types of sockets: Connection-oriented (TCP), Connectionless (UDP), MulticastSocket class– data can be sent to multiple recipients
Remote Procedure - Remote Procedure Call (RPC) abstracts procedure calls between processes on networked systems. Again uses ports for service differentiation
Call RPC - Stubs – proxies for the actual procedure on the server and client sides
The client-side stub locates the server and marshals the parameters
The server-side stub receives this message, unpacks the marshalled parameters, and performs the procedure on the server
- On Windows, stub code compile from specification written in Microsoft Interface Definition Language (MIDL)
Quiz - After a successful fork(), the return value to the child and parent are respectively: Child: 0; Parent: child’s pid
- Which system call pair commonly creates and then overlays a new program on UNIX? fork() then exec()
SUMMARY:
CHAPTER 4: Threads and Concurrency
Benefits of thread - Responsiveness – may allow continued execution if part of process is blocked, especially important for user interfaces
- Resource Sharing – threads share resources of process, easier than shared memory or message passing (IPC)
- Economy – cheaper than process creation, thread switching lower overhead than context switching
- Scalability – process can take advantage of multicore architectures
Multicore, Parrallel, - Multicore or multiprocessor systems putting pressure on programmers, challenges include (Dividing activities, Balance, Data splitting, Data dependency, Testing and debugging)
Concurrency - Parallelism implies a system can perform more than one task simultaneously
- Concurrency supports more than one task making progress Single processor / core, scheduler providing concurrency
- Types of parallelism
Data parallelism – distributes subsets of the same data across multiple cores, same operation on each
Task parallelism – distributing threads across cores, each thread performing unique operation
Amdahl’s Law Identifies performance gains from adding additional cores to an application that has both serial and parallel components
 S is serial portion
N processing cores
That is, if application is 75% parallel / 25% serial, moving from 1 to 2 cores results in speedup of 1.6 times
As N approaches infinity, speedup approaches 1/S
User thread vs User threads - management done by user-level threads library Three primary thread libraries: POSIX Pthreads Windows threads Java threads
Kernel thread Kernel threads - supported by the Kernel Examples – virtually all general purpose operating systems, including: Windows, Linux, Mac OS X iOS, Android
PROCESS THREAD
- A process is an instance of a program that is being executed or processed. - Thread is a segment of a process or a lightweight process that is managed by the
- Processes are independent of each other and hence don't share a memory or other scheduler independently.
resources - Threads are interdependent and share memory
- Each process is treated as a new process by the operating system. - The operating system takes all the user-level threads as a single process.
- If one process gets blocked by the operating system, then the other process can continue - If any user-level thread gets blocked, all of its peer threads also get blocked because OS
the execution. takes all of them as a single process.
- Context switching between two processes takes much time as they are heavy compared - Context switching between the threads is fast because they are very lightweight.
to thread. - Threads share data segment and code segment with their peer threads; hence are the
- The data segment and code segment of each process are independent of the other. same for other threads also.
- The operating system takes more time to terminate a process. - Threads can be terminated in very little time
- New process creation is more time taking as each new process takes all the resources. - A thread needs less time for creation.
Multi threading Many to one One to One Many to Many
model - Many user-level threads mapped to single kernel thread - Each user-level thread maps to one kernel thread - Allows many user level threads to be mapped to many
- One thread blocking causes all to block - Creating a user-level thread creates a kernel thread kernel threads
- Multiple threads may not run in parallel on multicore - More concurrency than many-to-one - Allows the operating system to create a sufficient
system because only one may be in kernel at a time - Number of threads per process sometimes restricted due number of kernel threads
- Few systems currently use this model to overhead - Windows with the ThreadFiber package
- Examples: Solaris Green Threads, GNU Portable Threads - Examples: Windows, Linux - Otherwise not very common

Thread creation Asynchronous threading Synchronous threading

- Parent and child execute concurrently and independently of one another - Parent must wait for all of its children to terminate before it resumes
- Commonly used for designing responsive user interfaces. - Involves significant data sharing among threads, parent thread may combine the results
calculated by its various children
#include<pthread.h> A pointer to a pthread_t variable, tid
pthread_t tid: declares the identifier tid for the thread - A pointer to a thread attribute object. If NULL, a thread created with the default thread
pthread_attr_t attr: represents the attributes for the thread, including stack size and attributes
scheduling information - A pointer to the thread function with type void*.
pthread attr init(&attr): set the default attributes - A thread argument value of type void*
pthread_create(): create a separate thread Thread function take a parameter of type void* and have a void* return
pthread_join(): parent thread will wait for child thread to terminate type.
pthread_exit(): child thread call to terminate
Implicit threading - Growing in popularity as numbers of threads increase, program correctness more difficult with explicit threads
- Creation and management of threads done by compilers and run-time libraries rather than programmers
Thread Pools Fork-Join Parallelism
Create a number of threads in a pool where they await work Multiple threads (tasks) are forked, and then joined.
Advantages:
- Usually slightly faster to service a request with an existing thread than create a new thread
- Allows the number of threads in the application(s) to be bound to the size of the pool
- Separating task to be performed from mechanics of creating task allows different strategies
for running task (i.e., Tasks could be scheduled to run periodically)
Signal Handling - Signals are used in UNIX systems to notify a process that a particular event has occurred.
- A signal handler is used to process signals : Signal is generated by particular event, Signal is delivered to a process, Signal is handled by one of two signal handlers (default, user-
defined)
- Every signal has a default handler that kernel runs when handling signal: User-defined signal handler can override default, For single-threaded, signal delivered to process
- Deliver the signal to the thread to which the signal applies
- Deliver the signal to every/certain thread in the process
- Assign a specific thread to receive all signals for the process
Thread termination Two general approaches:
Asynchronous cancellation terminates the target thread immediately
Deferred cancellation allows the target thread to periodically check if it should be cancelled
Thread Local Storage - Thread-local storage (TLS) allows each thread to have its own copy of data Useful when you do not have control over the thread creation process (i.e., when using a thread pool)
- TSL is persist all function calls and unique per thread, while local variables is just for 1 function
Scheduler - Typically use an intermediate data structure between user and kernel threads – lightweight process (LWP)
Activations o Appears to be a virtual processor on which process can schedule user thread to run
o Each LWP attached to kernel thread
Quiz - In many to one threading model, what is the greatest limitation on a multicore system : increase complexity of scheduling
- Reason multicore programming is harder than single-core concurrency : programs must explicitli manage parallelism to avoid idle cores
- A thread with defer cancellation, a cancellation request is sent but the thread never valls pthread_testcancel() : the cancellations request remain pending until a cancellation point is
reached
- function allow a parent to wait for a child to terminate : pthread_join()
- multithreader web server, each task is solved by a separate thread, main drawback : high overhead from excessive thread creation
- thread creation is handled by system call : clone()
- when fork() is called in a multithreaded process : only the calling thread is duplicated
- type of threading most suitable for GUI responsiveness : asynchronous threading
- FALSE about thread pool : they reduce responsiveness since thread must be created per task
SUMMARY:
CHAPTER 5: CPU Scheduler
Basic Concepts The Cycle:
- Processes do not run continuously. They alternate between two states:
- CPU Burst: Actually calculating/executing instructions.
- I/O Burst: Waiting for data (disk, network, user input).
- Trend: There are usually many short CPU bursts and few long CPU bursts.
The Scheduler vs. The Dispatcher:
- CPU Scheduler (Short-term Scheduler): The "Brain." It decides who runs next. It runs when a process switches states
- Dispatcher: The "Muscle." It performs the actual switch.
It switches the context (saves old, loads new).
It switches to User Mode.
It jumps to the proper location in the user program to restart it.
Dispatch Latency: The time it takes for the dispatcher to stop one process and start another. (This is pure overhead/waste).
Preemptive vs. Non-preemptive:
- Non-preemptive: Once the CPU is given to a process, that process keeps it until it terminates or switches to waiting state voluntarily. (Simple, but bad for multitasking).
- Preemptive: The OS can forcibly take the CPU away from a process (e.g., if a timer expires or a higher priority task arrives). (Required for modern OSs, but can cause race conditions).
Scheduling Criteria When optimizing an OS, you generally want to Maximize the good stuff and Minimize the bad stuff.
(How we measure Maximize:
success) CPU Utilization: Keep the CPU as busy as possible.
Throughput: Number of processes completed per time unit.
Minimize:
Turnaround Time: Total time from submission to completion (Exec + Wait).
Waiting Time: Total time spent sitting in the Ready Queue.
Response Time: Time from submission until the first response is produced (Crucial for UI/Interactive systems).
Scheduling
Algorithms (The
Core Theory) First come, First Serve Shortest-Job-First (SJF) Priority Scheduling Round Robin (RR) Multilevel Queue Multilevel Feedback
(FCFS) Queue
- Concept: The first process - Concept: The process - Concept: A number - Concept: Designed for - Concept: Partition the - Concept: Like Multilevel,
 to arrive gets the CPU. with the smallest next CPU (integer) is assigned to time-sharing. Each process Ready Queue into separate but processes
- Pros: Simple, easy to burst goes first. each process. Highest gets a small unit of time queues (e.g., can move between queues.
code (FIFO queue). - Pros: Provably priority runs (usually called a Time Quantum Foreground/Interactive vs.
Optimal (gives the lowest number = highest (q). After time expires, the Background/Batch). - Idea: If a process uses too
- Cons: The Convoy Effect. minimum average waiting priority). process is preempted and much CPU, move it to a
If one big CPU-heavy time). put at the back of the - Each queue has its own lower priority queue. If a
process arrives first, all the - Cons: Impossible to - Problem: Starvation. Low queue. algorithm (e.g., RR for process waits too long,
small I/O processes get implement perfectly priority processes Foreground, FCFS for move it to a higher priority
stuck behind it, destroying because we cannot predict may never execute. - The Physics of q: Background). queue (Aging).
device utilization. Average the future (we don't know If q is too large It behaves
waiting time is usually how long the next burst is). - Solution: Aging. Gradually like FCFS. -There is - This is the most complex
high. -Prediction (Exponential increase the priority of a If q is too small High scheduling between the but most flexible algorithm
Averaging): We guess the process the longer it waits overhead (too much time queues (usually Fixed
next burst size based on in the queue. spent context switching). Priority: Foreground must
previous behavior. empty before Background
- Preemptive Version - Rule of Thumb: 80% of runs).
(SRTF):Shortest Remaining CPU bursts should be
Time First. If a new process shorter than q
arrives with a shorter burst - Design for time sharing
than what is left of the
current process, preempt
the current one.
Thread scheduling - Process-Contention Scope (PCS): The thread library schedules user-level threads to run on an available LWP (Lightweight Process). This happens inside the process.
- System-Contention Scope (SCS): The Kernel decides which kernel thread runs on the physical CPU.
- Pthreads: POSIX allows you to specify scope (PTHREAD_SCOPE_SYSTEM maps one-to-one, typical in Linux/Windows).
Multi-processor - SMP (Symmetric Multiprocessing): All processors are peers; any processor can run any thread.
scheduling - Load Balancing: Keeping the work even across cores.
Push Migration: A specific task checks load and pushes tasks from overloaded to idle cores.
Pull Migration: An idle core pulls a waiting task from a busy core.
- Processor Affinity:
Soft Affinity: The OS tries to keep a process on the same core (to keep cache memory "warm"), but no guarantee.
Hard Affinity: The process specifies exactly which cores it can run on.
- Multithreaded Cores (Hardware): A single physical core has 2+ hardware threads (Intel Hyperthreading). If one thread stalls (waiting for memory), the core switches to the other
hardware thread immediately.
Real-Time CPU - Soft Real-Time: Critical processes get preference, but no guarantee when they will start.
Schedulling - Hard Real-Time: Task must be serviced by its deadline.
- Latency: The enemy of real-time.
Interrupt Latency: Time from interrupt arrival to start of service routine.
Dispatch Latency: Time to stop current process and start the real-time process.
- Algorithms:
Rate Monotonic: Static priority based on frequency (Period). Shorter period = Higher priority.
Earliest Deadline First (EDF): Dynamic priority. The task with the closest deadline runs next.
Proportional Share: Allocates TT shares total. Application gets NN shares. It is guaranteed N/TN/T of total processor time.
OS Example Linux Windows Solaris
- Uses CFS (Completely Fair Scheduler). - Priority-based, preemptive. Uses priority-based threads. Supports a "Time Sharing"
- It doesn't use standard Time Quanta. It uses a "Virtual - 32 Priority Levels. (0 = Memory management, 1-15 = class and a "Real Time" class.
Runtime" (vruntime). The task with the Variable, 16-31 = Real-time).
lowest vruntime runs next. - If a thread uses its time slice, priority is lowered (but
- Uses Red-Black trees to store tasks (Fast lookup). never below base). If it waits for I/O, priority is raised.

Algorithm - Deterministic Modeling: Take a specific workload (e.g., P1=10, P2=29) and manually calculate the Wait Time for each algo. (Simple, but specific to that input).
Evaluation - Queueing Models: Use math formulas (Little's Law) to predict performance based on arrival rates.
- Simulations: Program a model of the computer and feed it trace data (real records of past system events).
SUMMARY: