- definition: a system state in which processes, are busy swapping pages in and out due to a small number of frames available

- effect the system spends more time paging rather than executing

- We have to provide appropriate number of frames to process to prevent trashing

- page fault frequency method:

- Directly measure and control p.f.r (page fault rate) to prevent trashing

- The upper and lower bounds for p.f.r are set

- At regular intervals, measure the p.f.rs and take some frames from the processes with p.f.r below the lower bound, and give them to the processes with pfr higher than the upper bound

method 2: Working set Model Method

- Based on the notion of program locality “program locality”

- During a short period of program execution memory references tend to cluster around certain location (locality)

- A program is generally composed of several different localities, and the localities shift slowly - Localities are influenced by the programs control structures (loops) and data structures (arrays)

- Is the set of pages in the most recent Δ (Delta)number of memory refrences - Is used for approximating program localities

1. At regular interval, check the working set window, and get the working set.

2. The operating system monitors the working set of each process and allocate to it enough frames to hold at least its working set

3. If the sum of the total workup set is greater than the number of frames available then suspend some processes

goal:how to allocate disk space to files so that disk space is effectively utilized and files can be quickly accessed .

contiguous allocation, linked, and indexed allocation

- Each file occupies a set of contiguous blocks

- Directory entry for each file indicates the address of the starting block and the length of the area allocated.

adv: access is fast

disadvantage

1.  Causes external fragmentation of disk space

2. Have to determine in advance how much space is needed for a file(test q)

- Each file is a linked list of disk blocks

- Each block contains a pointer to the next block

- Directory entry has a pointer to the first block of the file adv:

1. No external fragmentation of disk space

2. No need to declare the file size at creation time disadvantage:

1. File access is slow

2. Cannot be used for direct access files

- Bring all pointers together into one location (index block)

- Index block(s) for each file

adv: can support direct access without suffering from external fragmentation

disadv: space overhead for index blocks- however small a file is, there must be an index block

goal: to reduce the disk service time

- Seek time = move the read write head to the desired track

Rotational delay = wait until the desired sector rotates under the head

- Transfer time = transfer data

- Inorder to reduce the service time, we try to reduce the total seek time for various requests

- total seek time is proportional to total distance of heads movement

1. FCFS (First Came First Serve)

- The simplest form and easy to implement

- The performance may not be good  

 Disk Scheduling Algorithm 

Scan

CScan

-     The head starts at one end of the desk, and moves toward the other end, securing requeist along the way at the other end, the direction of head movement is reserved and servicing continuous. (also known as “elevator algorithm”)

 C-SCAN (Circular Scan)

 - A variant of SCAN

-  When the head reaches the end, it immediately return to the beginning of the desk (no servicing during the return trip)

adv: can provide a more uniform wait time to all request

- An improvement over SCAN and C-SCAN - The head is only moved as far as the last request in each direction

def: a set of processes is in the deadlock state when every process in the set is waiting for an event that cannot occur

Effect: in a dead lock, processes cannot finish their task and system resources get tied up.

- A variant of SCAN - When the head reaches the end, it immediately return to the beginning of the desk (no servicing during the return trip)

can provide a more uniform wait time to all requests

- Deadlock occurs if and only if the following four conditions simultaneously in a system

(1) Mutual exclusion

- A resource can be used only by one process at a time

(2) Hold and wait

- A process that is holding at least one resource, is waiting to get additional resources that are currently held by other processes

(3) No preemption

- Resources cannot be preempted. They can only be released voluntarily after the process has completed its task

(4) Circular wait

- There must be a circular chain of two or more processes, each of which is waiting for a resource held by the next member in the chain.

Resource allocation Graph (RAG)

-  A directed graph that can be used to detect a deadlock in a system

-      -    Consists of nodes and edges

(1)    Nodes

Circular node - represent a process

Square node- represents a resource

(2)    Edges

Assignment edge – from a resource to a process

Request edge – from a process to a resource

3 Strategies for handling deadlocks

Strategy #1: Ignore the deadlock problem

Reasons:

a. - The cost to deal with deadlocks is very high

-   - Deadlocks occurs vey rarely

Approach:

-          Pretend there is no deadlock problem and reboot the system if it happens

Strategies for handling deadlocks

Strategy #2: Detection and recovery

-          Use the RAG

-          Every time a resource is requested, check The RAG to see if any cycle exists

-          If a cycle is detected, terminate the processes to break the cycle

problem: may have to recover any modified files

Strategies for handling deadlocks

Strategy #3 Deadlock prevention

idea: prevent the deadlock by ensuring that at least one of the four necessary conditions cannot hold .

(1)    Method 1: Denying the mutual exclusion condition

how: Simultaneously sharable resources do not require  mutual exclusion à cannot be involved in a deadlock

problem: many resources are not sharable

(2)    Method 2: Denying hold and wait Conditions

how : allocate all resources requested at the same time or allocate none of them

a.       Resource utilization may be very low

b.      Starvation of a process is possible

(3)    Method 3: Denying the no preemption condition

how: a resource held by a process can be taken away

problem: some resources may cause problems when they are taken away(sequential access device such as type drive)

(4)    Method 4: denying the circular wait condition

how: impose a total ordering of all resources and enforce the following rule- “ no process can request a resource lower than that what it is already holding”

problem: high overhead for maintaining the ordering

Strategies for handling deadlocks

Strategy  # 4 Deadlock avoidance

idea: to ensure that the system will always remain in a “safe state”

how: whenever a process request additional resources check the system state to see if it will still be in safe state after the requested resources are allocated.

-If yes – the request is granted

-If no- the request is not granted

“safe state”

-          A state is safe if the system can allocate resources in some order and still avoid a deadlock

-          A system is in safe state if there exist a safe sequence

-          Maintains the following info

1.       Maximum demand of each process (max)

2.       Resource currently allocated to each process(Allocation)

3.       Remaining resource need of each process (Need)

= max – allocation

4.       Available resources(availible)

Initial available = Total system resource –(sum of allocations)

-          Safe sequence in Banker’s algorithm a resource in which all needs are satisfied  by

(Initial available)+(the sum of allocation of al preceding processes)

Security :

1.      Internal threats – controlled access

2.      External threats – intrusion from outside

“Authentication” problem

è How to determine if a user’s identity is authentic

-          Authentication can be based on one or more of 3 factors

User possession – a key or card

User knowledge – user id and password

User attribute (biometrics)- finger print; retina scan

 Passwords:

-   - The most common approach

-   - Easy to understand and use

     problem : difficulty of keeping a password secret

è Being guessed or accidently exposed.

·         Some variants of password approach:

1.      Change the password frequently or periodically

(ex) “one time” password

2.      Using a function (algorithm) as a password 

Other techniques to improve security

1.      Threat monitoring(test question)

When logging in, count the number of incorrect passwords tried, and prevent guessing a password

2.      Audit log

-          Records the time, user and type of accesses

-          After security has been violated, determine how/when the problem occurred and check the damage.

Security or transmission

-          To protect data transfred over the network; esp sensitive (classified) info.

-          “encryption”: the most common method of protecting info  transmitted over unsecured links.(important)

Basic Mechanism:

1.      the info (text) is encrypted from its initial readable form (clear text) to an internal form (cipher text) this internal form does not make any sense

2.      The cipher text can be transmitted over unsecured links

3.      Decrypt the cipher text back into the clear text

Disk scheduling algorithm

   Shortest -seek -time- first

    Select request with minimum seek time from the current head position

problem: may cause starvation of some requests

Disk Scheduling Algorithm 

look

CLook

-          An improvement over SCAN and C-SCAN

-          The head is only moved as far as the last request in each direction.