operating systems

here we have graphs , codes then definitions of all final part of this course

Base and Limit Registers

    Multistep Processing of a User Program

paging hardware

Hierarchical Page Tables

Address-Translation Scheme

Three-level Paging Scheme

Hashed Page Table

Inverted Page Table Architecture

Schematic View of Swapping

Base register

holds the smallest legal physical memory address

Limit register

specifies the size of the range.

Logical address space

is the set of all logical addresses generated by a program

Physical address space

is the set of all physical addresses generated by a program

relocation register

Base Register used at execution time to perform logical-to-physical address translation.

dynamic loading

a technique where a routine is not loaded into memory until it is called during execution.

Static linking

system libraries and program code combined by the loader into the binary program image

Dynamic linking

linking postponed until execution time

Hole

block of available memory; holes of various size are scattered throughout memory (are gaps of unused memory between partitions.)

External Fragmentation

total memory space exists to satisfy a request, but it is not contiguous

Internal Fragmentation

allocated memory may be slightly larger than requested memory; this size difference is memory internal to a partition, but not being used

Paging

memory-management scheme that allow the physical address space of a process to be non-contiguous (logical memory chucnks)

frames

Divide physical memory into fixed-sized blocks (physical memory chunks)

page table

data structure used by the operating system to map logical pages to physical memory frames.

used to translate logical addresses to physical addresses in a paging memory system.

Page-table base register (PTBR)

points to the page table

Page-table length register (PTLR)

indicates size of the page table

swapped

process can be swapped temporarily out of memory to a backing store, and then brought back into memory for continued execution

Ready Queue

the list of all processes that are ready to run and are waiting for CPU time.

deadlock graph

Deadlock

situation where a set of processes are block because each process is holding resource and waiting for another resource that is acquired by some other process.

E is partitioned into two types

• request edge – directed edge Pi > Rj

 • assignment edge – directed edge Rj > Pi

 

Resource-Allocation Graph

Mutual Exclusion

not required for sharable resources (e.g., read-only files); must hold for non-sharable resources

Hold and Wait

must guarantee that whenever a process requests a resource, it does not hold any other resources

Circular Wait

Impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration

A safe state

when the system can guarantee that all processes can finish eventually — one at a time — without causing a deadlock.

claim edge

Process might ask for this resource late

Rollback

return to some safe state, restart process from that state

Starvation

same process may always be picked as victim, process will never finish its designated tasks (most common solution is to include the number of rollbacks in the cost factor)

Cooperating process

one that affect or be affected by other processes executing in the system.

Race condition

when two or more processes try to use or change shared data at the same time, and the final result depends on which one finishes first, which can lead to unexpected or incorrect results

Critical section problem

is to design a protocol that the processes can use to synchronize their activity so as to cooperatively share data.

 

requirements for solution to critical-section problem

1-     Mutual exclusion

2-     Progress

3-     Bounded waiting

Peterson’s solution

is restricted to two processes that alternate execution between their critical sections and remainder sections

The compare_and_swap  Properties

• Executed atomically

 • Returns the original value of passed parameter value

 • Set the variable value the value of the passed parameter new_value but only if *value == expected is true. That is, the swap takes place only under this condition

block

place the process invoking the operation on the appropriate waiting queue

wakeup

remove one of processes in the waiting queue and place it in the ready queue

monitors

A high-level abstraction that provides a convenient and effective mechanism for process synchronization.

Condition Variables graph

livness

set of properties that a system must satisfy to ensure processes make progress.

Starvation

indefinite blocking, A process may never be removed from the semaphore queue in which it is suspended

Priority Inversion

Scheduling problem when lower-priority process holds a lock needed by higher-priority process

condition construct

used inside monitors to allow a process to wait (pause) and later be signaled (resumed) by another process.

Virtual memory

separation of user logical memory from physical memory

Virtual address space

logical view of how process is stored in memory

Virtual Memory That is Larger Than Physical Memory graph

Demand paging

Could bring entire process into memory at load time OR bring a page into memory only when it is needed.

Lazy swapper

never swaps a page into memory unless page will be needed

Demand paging graph

page fault

During MMU address translation, if valid–invalid bit in page table entry is i

Page replacement

find some page in memory, but not really in use, page it out

Over-allocation

giving out more memory than what’s available, which causes performance problems like thrashing

modify (dirty) bit

shows if a page has been changed .

if not, it doesn’t need to be saved to disk when replaced.

Page Replacement graph

Thrashing

A process is busy swapping pages in and out. In other words, a process is thrashing if it is spending more time paging than executing