Operating Systems

Chapter 1

• Operating system is a program that acts intermediary between a user

of a computer and the computer hardware (can be in any device).
- Main goal à to solve users problems
- Is a resource allocator that decides between conflicting requests for
efficient and fair resource use. (solves the problem between
hardware & software)
- Is a control program to prevent errors and improper use of the
computer
- Depends on the point of view, ease of use and good performance

• Computer system:-
1. Hardware - CPU, memory, I/O devices
2. OS - controls and coordinates use of hardware
3. Application hardware – solve computing problems
4. Users – could be people, machines, computers

• Kernel: the one program that is running at all times in the computer aka
“the boss”
• Bootstrap program: loaded at power-up or reboot (helper, wakes the
kernel, exist in every hardware)
- Stored in ROM or EPROM
- Known as firmware

• Each device controller has a local buffer to control the speed and not
loose data
• Interrupt: the way of how devices communicate
1. Trap or Exception is a software generated interrupt
- Trap à when user does something wrong
- Exception à when there is an error
2. OS is interrupt driven because it communicates through hardware
or software
3. Polling and Vectored are hardware interrupt
- Polling à CPU asks every 1 second if there is a task to do, so
always busy but important
- Vectored à CPU will wait for the task to be given

• System call: request the OS to allow user to wait for I/O completion –
request is received by the CPU to perform the task
• Device – status table: contains entry for each I/O device indicating its
type, address and state.
• A Bit contains 0 and 1 – A Byte is 8 bits
- kilobyte, or KB, is 1,024 bytes
- megabyte, or MB, is 1,0242 bytes
- gigabyte, or GB, is 1,0243 bytes
- terabyte, or TB, is 1,0244 bytes
- petabyte, or PB, is 1,0245 bytes

• Main memory: only large storage media that the CPU can access
directly
- Random access
- Volatile “ when power is off everything is erased “

• Secondary storage: provides large nonvolatile storage capacity

• Hard disks: rigid metal or glass platters covered with magnetic
recording material
- Disk surface is logically divided into tracks, which are subdivided
into sectors
- The disk controller determines the logical interaction between the
device and the computer
• Solid-state disks – faster than hard disks, nonvolatile
- Various technologies
- Becoming more popular
• Storage systems organized in hierarchy (speed, cost, volatility)
• Caching: copying information into faster storage system; main memory
can be viewed as a cache for secondary storage
• Device Driver for each device controller to manage I/O
- Provides uniform interface between controller and kernel
• Multiprocessors: systems growing in use and importance AKA parallel
systems, tightly-coupled systems
Advantages:
- Increased throughput
- Economy of scale
- Increased reliability
1. Asymmetric Multiprocessing: each processor is assigned a specie task (no
shared memory)
2. Symmetric Multiprocessing: each processor performs all tasks (shared
memory)

• Clustered system: multi PCs work together

- Sharing storage via storage – area network (SAN)
- Clusters are for high-performance computing (HPC)
- Parallelization: dividing into separate chapters or clusters each
separate program handle a different task
1. Asymmetric clustering: one machine in hot standby mode
2. Symmetric clustering: multiple nodes running applications,
maintaining each other

• Multiprogramming: (Batch system) needed for efficiency, each

program can be run separately
• Timesharing: (multitasking) which CPU switches jobs, creating
interactive computing
- Response time should be less than1 second
- Each user has at least one program executing in memory à
process
- 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

- When application is (0) it’s coming from kernel, request is

preformed directly
- When application is (1) it’s coming from user, request should be
approved by kernel first then preformed

• Program counter: reminds the CPU when you stopped reading or

preforming something the last time.
• Deadlock handling: if 2 process want to request for the same thing at
the same time, for instance a printer.

• Memory management: execute a program, all the data should be in

the memory
- Determines what and when is in memory
- Keep track on the memory (when & who is using it)
- Allocating memory space as needed

• Storage Management: uniform, logical view of information storage

- Files are stored in it and they are usually organized into directories
- Access control to determine who can access and what
- Deleting files, to manipulate files, mapping files, backup files
• Mass-Storage Management: disks used to store data that does not fit
in main memory or data that must be kept for a “long” period of time
- Should keep managed to access easily
- Speed of accessing file depends on storage management
- Free-space management, storage allocation, disk scheduling

Level 1 2 3 4 5
Name registers cache main memory solid state disk magnetic disk
Typical size < 1 KB < 16MB < 64GB < 1 TB < 10 TB
Implementation custom memory on-chip or CMOS SRAM flash memory magnetic disk
technology with multiple off-chip
ports CMOS CMOS SRAM
Access time (ns) 0.25 - 0.5 0.5 - 25 80 - 250 25,000 - 50,000 5,000,000
Bandwidth (MB/sec) 20,000 - 100,000 5,000 - 10,000 1,000 - 5,000 500 20 - 150
Managed by compiler hardware operating system operating system operating system
Backed by cache main memory disk disk disk or tape

• I/O Subsystem: hardware devices

- Including buffering, caching, spooling(overlapping of output of one
job with input of other)
- Device-driver à any hardware should have driver which is a set of
instructions that allow hardware to connect to each other
- Specific hardware devices

• Protection – any mechanism for controlling access of processes or users

to resources defined by the OS “protect the OS from users issues”
• Security – defense of the system against internal and external attacks
• Privilege escalation: allows user to change to effective ID with more
rights
• Kernel Data Structures: set of program written in linked list
• Computing Environments – Traditional: Stand-alone general
purpose machines
- Portals provide web access to internal systems
- Network computers (thin clients) are like Web terminals
- Mobile computers interconnect via wireless networks
- Firewalls to protect home computers from Internet attacks

1. Mobile à smartphones, tablets, etc

- More OS features (GPS, gyroscope)
- Apple iOS and Google Android

2. Distributed à possibly heterogeneous, systems networked together

- Network is a communications path, TCP/IP most common
 3. Client server à 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
4. Peer-to-Peer à not distinguish clients and servers
- Nodes are considered peers

5. Virtualization à run applications within other OSes

processes

processes

processes processes

programming
kernel kernel kernel
interface
VM1 VM2 VM3
kernel
virtual machine
manager
hardware
hardware

(a) (b)

6. Cloud computing à “storage in internet”

- 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
- 3 ways to communicate with cloud computing à Software as a
Service (SaaS) , Platform as a Service (PaaS) , Infrastructure as a
Service (IaaS)

7. Real-Time Embedded Systems à Vary considerable, special

purpose, limited purpose OS, real-time OS

• Open-Source Operating Systems: ex -- “smart watch”

- Source-code format rather than just binary closed-source
- Counter to the copy protection and Digital Rights Management
(DRM) movement
- Free Software Foundation (FSF), like GNU/Linux, BSD UNIX
and Mac OS X
 Operating-System Structures
Chapter 2

• There are 9 features that the companies work to enhance and to make the
environment friendly

1. User interface (UI) – command line (CLI) which is a way of

communication between OS & user, graphic user interface (GUI) ,
batch which is between CLI & GUI
2. Program execution – load a program into memory and run that
application, execution normally or abnormally
3. I/O operations – running program may require I/O, involve a file or
an I/O device
4. File-system manipulation – read and write files and directories, create,
delete, search, list file information and permission management
5. Communications – ability to share or exchange files via shared
memory or through message passing
6. Error detection – constantly aware of possible errors, occur in the
CPU and memory hardware, in I/O devices, in user program, if there
is an error it would take the proper action
7. Resource allocation – makes CPU acts or moves faster to handle many
requests
8. Accounting – tracks the user, which users use how much and what
kinds of computer resources
9. Protection and security – owner control use of information
- Protection à ensuring that all access to system resources is
controlled
- Security à requires user authentication, extends to defending
external I/O devices from invalid access attempts

• Command interpreter - (CLI) allows direct command entry

- Sometimes implemented in kernel, sometimes by systems program
- Sometimes multiple flavors implemented – shells “set of
commands”

• GUI: User-friendly desktop metaphor interface

- Usually mouse, keyboard, and monitor
- Icons represent files, programs, actions, etc

• Application Programming Interface - (API): group of system

communicate with software
- Win32 API for windows , Linux , Mac OS X , Java API
• System-call interface maintains a table indexed according to these
numbers
- Invokes the intended system call in OS kernel and returns status of
the system call and any return values
- The caller need not be aware of the implementation of the system
call.
• System call parameter passing
- Often, more information is required than simply identity of desired
system call à according to OS and call
- Three general methods used to pass parameters to the OS
o Simplest: pass the parameters in registers, may be more
parameters than registers
o Parameters: stored in a block, or table, in memory, and
address of block passed as a parameter in a register
o Register: is fast and have limitation, important messages
while block & stack are slow with no limit

• Types of system calls:

1. Process control
- Create process, end, load, execute, debugger for determining bugs,
single step execution, locks for managing access to shared data
between processes

2. File management
- Create, delete, open, close, write, read, get, set files

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

4. Information maintenance
- Get or set time & date, get or set system data, get or set process file

5. 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

6. Protection
- Control access to resources, get and set permissions, allow and
deny user access
• Example: MS-DOS
- Single-tasking , Shell invoked when system booted, Simple method
to run program
- No process created
- Single memory space

• System Programs: System programs provide a convenient

environment for program development and execution.

1. File management à Anything related to files

o Create, delete, copy, rename, print, dump, list, and generally
manipulate files and directories

2. Status information à checks status of the program

o Some ask the system for info - date, time, amount of
available memory, disk space, number of users
o Some systems implement a registry - used to store and
retrieve configuration information

3. File modification à Text editors to create and modify files , search

contents of files or perform transformations of the text

4. Programming-language support à Compilers, assemblers,

debuggers and interpreters sometimes provided

5. Program loading and execution à Absolute loaders, relocatable

loaders, linkage editors, and overlay-loaders, debugging systems for
higher-level and machine language

6. Communications à Provide the mechanism for creating virtual

connections among processes, users, and computer systems, allow
users to send messages
 7. Background Services à logistic for all applications
o Run in user context not kernel context
o Known as services, subsystems, daemons

8. Application programs à Don’t pertain to system, run by users, not

typically considered part of OS, launched by command line, mouse
click, finger poke

• Operating System Design and Implementation:

- There is always a better improvement and enhancement “solvable”
- Start the design by defining goals and specifications
- Affected by choice of hardware, type of system

- User goals and System goals

o User goals – OS should be convenient to use, easy to
learn, reliable, safe, and fast
o System goals – OS should be easy to design, implement,
maintain, flexible, reliable, error-free, and efficient

- Policy (can be changed easily): What will be done?

- Mechanism (patent): How to do it?
- The separation of policy from mechanism is very important à it
allows maximum flexibility if decisions are going to be changed
later
- Specifying and designing an OS is highly creative task of software
engineering

• Emulation: can allow an OS to run non-native hardware (installed in

any hardware)

• Operating system structure:

- Simple structure – MS-DOS
- More complex – UNIX
- Layered – an abstraction
- Microkernel – Mach

• Simple structure - MS-DOS:

- Not divided into modules
- Its interfaces and levels of functionality are not well separated
• Non-simple structure - UNIX: the UNIX OS consists of two separable
parts
o Systems programs
o 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

• Layered approach: OS is divided into number of layers (levels), with

modularity, layers are selected such that each uses functions (operations)
and services of only lower-level layers

• Microkernel system structure

- Message passing à communication takes
place between user modules
Benefits:
o Easier to extend a microkernel
o Easier to port the operating system to new
architectures
o More reliable (less code is running in kernel
mode)
o More secure
Detriments:
o Performance overhead of user space to kernel space
communication

• Modules: Many modern operating systems implement loadable kernel

modules
- Uses object-oriented approach
- Each core component is separate
- Each talks to the others over known interfaces
- Each is loadable as needed within the kernel
- Overall, similar to layers but with more flexible à Linux , Solaris

• Solaris modular approach

• Hybrid Systems: not one pure model
- Combines multiple approaches to address performance, security,
usability needs
- Windows mostly monolithic, plus microkernel for different
subsystem personalities
- Apple Mac OS X hybrid, layered, Aqua UI plus Cocoa
programming environment

• Operating-System Debugging: Debugging is finding and fixing errors,

or bugs
- OS generate log files containing error information
- Core dump à file capturing memory of the process “related to
applications”
- Crash dump à file containing kernel memory
- Profiling is periodic sampling of instruction pointer to look for
statistical trends

• Performance tuning: improve performance by removing bottlenecks,

can be accessed in both windows and mac
• Operating System Generation:
- SYSGEN program obtains information concerning the specific
configuration of the hardware system
o Used to build system-specific compiled kernel or system-tuned
o Can general more efficient code than one general kernel

• System Boot: when power initialized on system, execution starts at a

fixed memory location
- Firmware ROM used to hold initial boot code
- Available to hardware so hardware can start it
- Small piece of code – bootstrap loader, stored in ROM or EEPROM
locates the kernel, loads it into memory, and starts it
 Processes
Chapter 3

• An operating system executes a variety of programs:

- Batch system – jobs
- Time-shared systems – user programs or tasks

• Process – a program in execution; process execution must progress in

sequential fashion
- The program code, also called text section
- Current activity including program counter, processor registers
- Stack containing temporary data
- Data section containing global variables
- Heap containing memory dynamically allocated during run
time

• Program is passive entity stored on disk (executable file), process is active

- Program becomes process when executable file loaded into
memory
• Execution of program started via GUI mouse clicks, command line entry
of its name, etc.
• One program can be several processes
- Consider multiple users executing the same program

• As a process executes, it changes state

- 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
• Information associated with each process (also called task control block)
1. Status :-
- Process state – running, waiting, etc.
2. CPU :-
- Program counter – location of instruction to next execute
- CPU registers – contents of all process-centric registers
- CPU scheduling information – priorities, scheduling queue
pointers
3. Memory :-
- Memory-management information – memory allocated to the
process
- Accounting information – CPU used, clock time elapsed since
start, time limits
4. I/O :-
- I/O status information – I/O devices allocated to process, list of
open files

• A process has a single thread of execution

- Multiple program counters per process
- Multiple locations can execute at once
o Multiple threads of control à threads

• Process Scheduling: Maximize CPU use, quickly switch processes

onto CPU for time sharing
- Process scheduler selects among available processes for next
execution on CPU
- Maintains scheduling queues of processes
o Job queue – set of all processes in the system
o Ready queue – set of all processes residing in main
memory, ready and waiting to execute
o Device queues – set of processes waiting for an I/O
device
- Processes migrate among the various queues
• Queueing diagram
represents queues, resources,
flows

• Schedulers
- Short-term scheduler (or CPU scheduler) – selects which
process should be executed next and allocates CPU
o Sometimes the only scheduler in a system
o Short-term scheduler is invoked frequently
(milliseconds) Þ (must be fast)
- Long-term scheduler (or job scheduler) – selects which
processes should be brought into the ready queue
o Long-term scheduler is invoked infrequently (seconds,
minutes) Þ (may be slow)
o The long-term scheduler controls the degree of
multiprogramming
- Processes can be described as either:
- I/O-bound process – spends more time doing I/O than
computations, many short CPU bursts
- CPU-bound process – spends more time doing computations

• Medium-term scheduler: can be added if degree of multiple

programming needs to decrease
- Remove process from memory, store on disk, bring back in
from disk to continue execution: swapping

• Multitasking in Mobile Systems: allow only one process to run,

others suspended
• Due to screen real estate, user interface limits iOS provides for a
o Single foreground process – controlled via user interface
 o Multiple background processes– in memory, running, but not on
the display, and with limits
o Limits include single, short task, receiving notification of events,
specific long-running tasks like audio playback
• Android runs foreground and background, with fewer limits
o Background process uses a service to perform tasks
o Service has no user interface, small memory use

• 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
- Represented in the PCB
- Context-switch time is overhead; the system does no useful work
while switching
o The more complex the OS and the PCB à the longer
the context switch
- Time dependent on hardware support
o Some hardware provides multiple sets of registers per
CPU à multiple contexts loaded at once

• Operations on Processes: System must provide mechanisms for:

1. Process creation

o Parent process create children processes, which, in turn

create other processes, forming a tree of processes
o Process identified and managed via a process identifier
(pid)
- Resource sharing options
o Parent and children share all resources
o Children share subset of parent’s resources
o Parent and child share no resources
- Execution options
o Parent and children execute concurrently
o Parent waits until children terminate
- Address space
o Child duplicate of parent
o Child has a program loaded into it
- UNIX examples
o fork() system call creates new process
o exec() system call used after a fork() to replace
the process’ memory space with a new program
2. Process termination
- Process executes last statement and then asks the operating
system to delete it using the exit() system call.
o Returns status data from child to parent
o Process’ resources are deallocated by operating system
- Parent may terminate the execution of children processes using
the abort() system call. Some reasons for doing so:
o Child has exceeded allocated resources
o Task assigned to child is no longer required
o The parent is exiting and the operating systems does
not allow a child to continue if its parent terminates

- Some operating systems do not allow child to exists if its parent

has terminated. If a process terminates, then all its children
must also be terminated.
o Cascading termination. All children, grandchildren, etc.
are terminated.
o The termination is initiated by the operating system.
- 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);

• Multi-process Architecture – Chrome Browser

- Many web browsers ran as single process
o If one web site causes trouble, entire browser can hang or
crash
- Google Chrome Browser is multi-process with 3 different types
of processes:
o Browser – process manages user interface, disk and
network I/O
o Renderer – deals with programming
4 Runs in sandbox
o Plug-in – process for each type of plug-in

• Inter-process Communication
- Independent – process cannot affect or be affected by the
execution of another process
- Cooperating – process can affect or be affected by the execution
of another process
 - Advantages of process cooperation
o Information sharing
o Computation speed-up
o Modularity
o Convenience
- Cooperating processes need inter-process communication (IPC)
o Two models of IPC
§ Shared memory
§ Message passing

• Synchronization: message passing may be either blocking or non-

blocking
- Blocking is considered synchronous
o Blocking send -- the sender is blocked until the message
is received
o Blocking receive -- the receiver is blocked until a
message is available
- Non-blocking is considered asynchronous
o Non-blocking send -- the sender sends the message and
continue
o Non-blocking receive -- the receiver receives:
§ A valid message, or
§ Null message
- Different combinations possible
o If both send and receive are blocking, we have a
rendezvous

• Buffering: queue of messages attached to the link.

- implemented in one of three ways
1. Zero capacity – no messages are queued on a link.
Sender must wait for receiver (rendezvous)
2. Bounded capacity – finite length of n messages
Sender must wait if link full
3. Unbounded capacity – infinite length
Sender never waits

• Examples of IPC Systems – Windows

- Message-passing centric via advanced local procedure call
(LPC) facility
o Only works between processes on the same system
o Uses ports (like mailboxes) to establish and maintain
communication channels
o Communication works as follows:
 1. The client opens a handle to the subsystem’s
connection port object.
2. The client sends a connection request.
3. The server creates two private communication ports
and returns the handle to one of them to the client.
4. The client and server use the corresponding port
handle to send messages or callbacks and to listen for
replies.

• Communications in
Client-Server Systems
- Sockets
- Remote Procedure
Calls
- Pipes
- Remote Method
Invocation (Java)

• Sockets: is defined as an endpoint for communication

- Concatenation of IP address and port – a number included at
start of message packet to differentiate network services on a
host
- The socket [Link]:1625 refers to port 1625 on host
[Link]

• Remote Procedure Calls

- Remote procedure call (RPC) abstracts procedure calls between
processes on networked systems
o Again uses ports for service differentiation
- On Windows, stub code compile from specification written in
Microsoft Interface Definition Language (MIDL) à
communication protocol / runs in windows
- Remote communication has more failure scenarios than local

• Pipes: acts as a conduit allowing two processes to communicate

- Issues:
o Is communication unidirectional or bidirectional?
o In the case of two-way communication, is it half or full-
duplex?
o Must there exist a relationship (i.e., parent-child)
between the communicating processes?
o Can the pipes be used over a network?
 - 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)
- Ordinary pipes are therefore unidirectional
- Require parent-child relationship between communicating
processes
- Windows calls these anonymous pipes

• Named Pipes: are more powerful than ordinary pipes

- Communication is bidirectional
- No parent-child relationship is necessary between the
communicating processes
- Several processes can use the named pipe for communication
- Provided on both UNIX and Windows systems
 Threads
Chapter 4

• Motivation: Most modern applications are multithreaded

- Threads run within application
- Multiple tasks with the application can be implemented by separate
threads
o Update display
o Fetch data
o Spell checking
o Answer a network request
- Process creation is heavy-weight while thread creation is light-weight
- Can simplify code, increase efficiency
- Kernels are generally multithreaded

• Benefits
- 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
- Economy – cheaper than process creation, thread switching lower
overhead than context switching
- Scalability – process can take advantage of multiprocessor
architectures

• Multicore Programming
- Multicore or multiprocessor systems putting pressure on programmers,
challenges include:
o Dividing activities
o Balance
o Data splitting
o Data dependency
o Testing and debugging
- Parallelism implies a system can perform more than one task
simultaneously
- Concurrency supports more than one task making progress
o Single processor / core, scheduler providing concurrency

• Multicore Programming (Cont.)

- Types of parallelism
o Data parallelism – distributes subsets of the same data across
multiple cores, same operation on each
 o Task parallelism – distributing threads across cores, each thread
performing unique operation
- As # of threads grows, so does architectural support for threading
o CPUs have cores as well as hardware threads

• Concurrent execution on single-core system:

single core T1 T2 T3 T4 T1 T2 T3 T4 T1 …
time

• Parallelism on a multi-core system:

core 1 T1 T3 T1 T3 T1 …

core 2 T2 T4 T2 T4 T2 …
time

code data files code data files

registers stack registers registers registers

stack stack stack

thread thread

single-threaded process multithreaded process

• Amdahl’s Law
- Identifies performance gains from adding additional cores to an
application that has both serial and parallel components
o S is serial portion
o 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
 - Serial portion of an application has disproportionate effect on
performance gained by adding additional cores

• User Threads: management done by user-level

threads library
- Three primary thread libraries:
o POSIX Pthreads
o Windows threads
o Java threads

• Kernel Threads: Supported by the Kernel

- Examples – virtually all general purpose operating systems, including:
o Windows
o Solaris
o Linux
o Tru64 UNIX
o Mac OS X

• Multithreading Models
1. Many-to-One
o Many user-level threads mapped to single kernel thread
o One thread blocking causes all to block
o Multiple threads may not run in parallel on multicore
system because only one may be in kernel at a time
o Few systems currently use this model
o Examples: Solaris Green Threads, GNU user thread

Portable Threads

k kernel thread

2. One-to-One
o Each user-level thread maps to kernel thread
o Creating a user-level thread creates a kernel thread
o More concurrency than many-to-one
o Number of threads per process sometimes restricted due to
overhead
o Examples: Windows, Linux, Solaris 9 and user thread

later
k k k k kernel thread
 3. Many-to-Many
o Allows many user level threads to be mapped to many kernel
threads
o Allows the operating system to create a
sufficient number of kernel threads user thread

k k k kernel thread

4. Two-level Model
o Similar to M:M, except that it allows a user thread to be
bound to kernel thread
o Examples: Tru64 UNIX user thread

k k k k kernel thread

• Thread Libraries: provides programmer with API for creating and

managing threads
- Two primary ways of implementing
o Library entirely in user space
o Kernel-level library supported by the OS

• Implicit Threading: creation and management of threads done by

compilers and run-time libraries rather than programmers
- Three methods explored
o Thread Pools
o OpenMP
o Grand Central Dispatch

• Thread Pools: create a number of threads in a pool where they await

work
- Advantages:
o Usually slightly faster to service a request with an existing
thread than create a new thread
o Allows the number of threads in the application(s) to be bound
to the size of the pool
o Separating task to be performed from mechanics of creating
task allows different strategies for running task
• Threading Issues
- Semantics of fork() and exec() system calls
- Signal handling
o Synchronous and asynchronous
- Thread cancellation of target thread
o Asynchronous or deferred
- Thread-local storage
- Scheduler Activations

• Signal Handling: signals are used in UNIX systems to notify a process

that a particular event has occurred

• Thread Cancellation:
- Terminating a thread before it has finished
- Thread to be canceled is target thread
- Two general approaches:
o Asynchronous cancellation terminates the target thread
immediately
o Deferred cancellation allows the target thread to periodically
check if it should be cancelled
- If thread has cancellation disabled, cancellation remains pending until
thread enables it
- Default type is deferred
o Cancellation only occurs when thread reaches cancellation
point
- On Linux systems, thread cancellation is handled through signals

• Thread-Local Storage: allows each thread to have its own copy of data
(backup for all threads)
- Useful when you do not have control over the thread creation process
- Different from local variables
o Local variables visible only during single function invocation
o TLS visible across function invocations
- Similar to static data
o TLS (managed by OS) is unique to each thread

• Scheduler Activations
- Both M:M and Two-level models require communication to maintain
the appropriate number of kernel threads allocated to the application
- Typically use an intermediate data structure between user and kernel
threads – lightweight process (LWP)
o Appears to be a virtual processor on which process can schedule
user thread to run
 o Each LWP attached to kernel thread
o How many LWPs to create?
- Scheduler activations provide upcalls - a communication mechanism
from the kernel to the upcall handler in the thread library
- This communication allows an application to maintain the correct
number kernel threads

• Operating System Examples

1. Windows Threads
The primary data structures of a thread include:
o ETHREAD (executive thread block) – includes pointer to process
to which thread belongs and to KTHREAD, in kernel space
o KTHREAD (kernel thread block) – scheduling and
synchronization info, kernel-mode stack, pointer to TEB, in
kernel space
o TEB (thread environment block) – thread id, user-mode stack,
thread-local storage, in user space
ETHREAD

thread start
address

pointer to
parent process KTHREAD

scheduling
and
synchronization
• information
•
•
kernel TEB
stack

thread identifier

• user
• stack
•
thread-local
storage

•
•
•
2. Linux Threads kernel space user space

o Linux refers to them as tasks rather than threads

o Thread creation is done through clone() system call
o clone() allows a child task to share the address space of the parent task
(process)
 CPU Scheduling
Chapter 5

• Maximum CPU utilization obtained with multiprogramming

• CPU–I/O Burst Cycle – Process execution consists of a cycle of CPU
execution and I/O wait
• CPU burst followed by I/O burst
• CPU burst distribution is of main concern
• CPU Scheduler
- Short-term scheduler selects from among the processes in ready
queue, and allocates the CPU to one of them
o Queue may be ordered in various ways
- CPU scheduling decisions may take place when a process:
1. Switches from running to waiting state
2. Switches from running to ready state
3. Switches from waiting to ready
4. Terminates
- Scheduling under 1 and 4 is nonprimitive
- All other scheduling is preemptive
o Consider access to shared data
o Consider preemption while in kernel mode
o Consider interrupts occurring during crucial OS activities

• Dispatcher: gives control of the CPU to the process selected by the

short-term scheduler; this involves:
o switching context
o switching to user mode
o jumping to the proper location in the user program to restart that
program
- Dispatch latency – time it takes for the dispatcher to stop one process and
start another running

• Scheduling Criteria
- CPU utilization – keep the CPU as busy as possible
- Throughput – number of processes that complete their execution per
time unit
- Turnaround time – amount of time to execute a particular process
- Waiting time – amount of time a process has been waiting in the ready
queue
- Response time – amount of time it takes from when a request was
submitted until the first response is produced, not output
• Scheduling Algorithm Optimization Criteria
1. Max CPU utilization
2. Max throughput
3. Min turnaround time
4. Min waiting time
5. Min response time

• First- Come, First-Served (FCFS) Scheduling

Process Burst Time
P1 24
P2 3
P3 3
- Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:
P
3
P
2
P
1

03 72 42 0

- Waiting time for P1 = 0; P2 = 24; P3 = 27

Average waiting time: (0 + 24 + 27)/3 = 17

• FCFS Scheduling (Cont.)

Suppose that the processes arrive in the order:
P2 , P3 , P1
- The Gantt chart for the schedule is:

P2 P3 P1
0 3 6 30

- Waiting time for P1 = 6; P2 = 0; P3 = 3

- Average waiting time: (6 + 0 + 3)/3 = 3
- Much better than previous case
- Convoy effect - short process behind long process
o Consider one CPU-bound and many I/O-bound processes

• Shortest-Job-First (SJF) Scheduling

- Associate with each process the length of its next CPU burst
o Use these lengths to schedule the process with the shortest time
- SJF is optimal – gives minimum average waiting time for a given set of
processes
o The difficulty is knowing the length of the next CPU request
o Could ask the user
• Priority Scheduling
- A priority number (integer) is associated with each process
- The CPU is allocated to the process with the highest priority (smallest
integer º highest priority)
o Preemptive
o Nonprimitive
- SJF is priority scheduling where priority is the inverse of predicted next
CPU burst time
- Problem º Starvation – low priority processes may never execute
- Solution º Aging – as time progresses increase the priority of the process

• Round Robin (RR)

- Each process gets a small unit of CPU time (time quantum q), usually 10-
100 milliseconds. After this time has elapsed, the process is preempted
and added to the end of the ready queue.
- If there are n processes in the ready queue and the time quantum is q,
then each process gets 1/n of the CPU time in chunks of at most q time
units at once. No process waits more than (n-1)q time units.

• Example of RR with Time Quantum = 4

Process Burst Time
P1 24
P2 3 P P P 1 1 1
P
1
P
1
P
3
P
2
P
1

P3 3 03 62 22 81 41 01 7 4 0

- Typically, higher average turn around than SJF, but better response
- q should be large compared to context switch time

• Multilevel Queue: Ready queue is partitioned into separate queues, eg:

- foreground (interactive)
- background (batch)
- Process permanently in a given queue
- Each queue has its own scheduling algorithm:
o foreground – RR
o background – FCFS
- A process can move between the various queues; aging can be implemented
this way
- Multilevel-feedback-queue scheduler defined by the following parameters:
o number of queues
o scheduling algorithms for each queue
o method used to determine when to upgrade a process
o method used to determine when to demote a process
o method used to determine which queue a process will enter when that
process needs service
 - Three queues:
o Q0 – RR with time quantum 8 milliseconds
o Q1 – RR time quantum 16 milliseconds
o Q2 – FCFS

- Scheduling
o A new job enters queue Q0 which is served
FCFS
§ Gains CPU à job receives 8
milliseconds
§ If it’s not finish in 8 milliseconds à job is moved to queue Q1
o At Q1 job is again served FCFS and receives 16 additional milliseconds
§ If it still does not complete, it is preempted and moved to queue
Q2

• Multiple-Processor Scheduling: CPU scheduling more complex when multiple

CPUs are available
- Homogeneous processors
- Asymmetric multiprocessing
- Symmetric multiprocessing (SMP)
- Processor affinity
 File-System Interface
Chapter 6

• File Concept: Contiguous logical address space

• Types:
o Data: numeric, character, binary
o Program

• File Structure:
1. None - sequence of words, bytes
2. Simple record structure
a. Lines
b. Fixed length
c. Variable length
3. Complex Structures
a. Formatted document
b. Relocatable load file
- Who decides: Operating system

• File Attributes
- Name – only information kept in human-readable form
- Identifier – unique tag (number) identifies file within file system
- Type – needed for systems that support different types
- Location – pointer to file location on device
- Size – current file size
- Protection – controls who can do reading, writing, executing
- Time, date, and user identification – data for protection, security, and usage
monitoring
- Information about files are kept in the directory structure, which is
maintained on the disk

• File Operations: File is an abstract data type

- Create, write, read, reposition within file, Delete, Truncate
- Open (Fi) – search the directory structure on disk for entry Fi, and move the
content of entry to memory
- Close (Fi) – move the content of entry Fi in memory to directory structure on
disk
• Open Files
- File pointer: pointer to last read/write location, per process that has the file
open
- File-open count: counter of number of times a file is open – to allow removal
of data from open-file table when last processes closes it
- Disk location of the file: cache of data access information
- Access rights: per-process access mode information

• File Types – Name, Extension

• Access Methods
- Sequential Access
o read next
o write next
o reset
o no read after last write
o (rewrite)
- Direct Access
o read n
o write n
o position to n
o read next
o write next
o rewrite n

• Directory Structure: A collection of nodes containing information about

all files
• Disk Structure
- Disk can be subdivided into partitions
- Disks or partitions can be RAID protected against failure
- Disk or partition can be used raw – without a file system, or formatted with a
file system
- Partitions also known as minidisks, slices
- Entity containing file system known as a volume
- Each volume containing file system also tracks that file system’s info in
device directory or volume table of contents
- As well as general-purpose file systems there are many special-purpose file
systems, frequently all within the same operating system or computer
• Operations Performed on Directory
- Search for a file
- Create a file
- Delete a file
- List a directory
- Rename a file
- Traverse the file system

• Organize the Directory (Logically) to Obtain

- Efficiency – locating a file quickly
- Naming – convenient to users
o Two users can have same name for different files
o The same file can have several different names
- Grouping – logical grouping of files by properties, (e.g., all Java programs, all
games, …)

• Single-Level Directory: A single

directory for all users
- Naming problem
- Grouping problem

• Two-Level Directory: Separate

directory for each user
- Path name
- Can have the same file name for different
user
- Efficient searching

• Tree-Structured Directories (Cont)

- Efficient searching
- Grouping Capability
- Current directory (working directory)
- cd /spell/mail/prog
• Acyclic-Graph Directories: Have shared subdirectories and files

• File Sharing – Multiple Users

- User IDs identify users, allowing permissions
and protections to be per-user
- Group IDs allow users to be in groups,
permitting group access rights

• Protection
- File owner/creator should be able to control:
o what can be done
o by whom
- Types of access
o Read
o Write
o Execute
o Append
o Delete
o List

• Access Lists and Groups

- Mode of access: read, write, execute
- Three classes of users
RWX
a) owner access 7 Þ 111
RWX
b) group access 6 Þ 110
RWX
c) public access 1 Þ 001