System Programming In Linux
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View System Programming In Linux as PDF for free.
More details
- Words: 20,553
- Pages: 308
SYSTEM
PROGRAMMING
IN LINUX UTTAM K. ROY
Dept. of Information Technology, Jadavpur University, Kolkata
System Programming in Linux
2
Topics to be discussed
Advanced Java Programming
Introduction to Operating Systems and Linux Internals
SYSTEM
General Introduction to Operating Systems Process management Scheduling Memory Management File Management
PROGRAMMING Linux Systems Programming Files and Directories Input/Output System Files Process Control Signals Interprocess Communication Network programming
Linux System Administration Linux Shells and Commands Systems management Managing File Systems Network Management
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
Books
Advanced Java Programming
“Operating System Concepts”,
•
Silberschatz Galvin, Wesley publication
•
Andrew S. Tanenbaum,
•
William Stallings,
•
•
3
SYSTEM
Addison
“Operating Systems”
“Operating Systems”,
Prentice-Hall India
PROGRAMMING Richard Stones & Neil Matthew, “Beginning Programming”, A Wrox publication Sumitabha Das, publication
Linux
“Unix Shell Programming”,
IN LINUX
•
Olaf Kirch, Terry Dawson, “Linux Guide”, A O’relly publication
•
Daniel P. Bovet, Marco Cesati, “Understanding Kernel”, O’Reilly publication
| U. K. Roy |
A Tata McGraw-Hill
Network Administrator's the Linux [
]
INTRODUCTION TO OPERATING SYSTEM
System Programming in Linux
5
Computer System Organization
Advanced Java Programming
Computer-system operation
SYSTEM
One or more CPUs, device controllers connect through common bus providing access to shared memory Concurrent execution of CPUs and devices competing for memory cycles
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
6
Components of a Computer System
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
7
Components (Contd.)
Advanced Java Programming
SYSTEM PROGRAMMING
A computer system consists of
IN LINUX hardware
system programs
application programs
| U. K. Roy |
[
]
System Programming in Linux
8
Components (Contd.)
Advanced Java Programming
SYSTEM
Computer system components
Hardware – provides basic computing resources • CPU, memory, I/O devices
Operating system • Controls and coordinates use of hardware among various applications and users
PROGRAMMING Application programs – define the ways in which the system resources are used to solve the computing problems of the users • Word processors, compilers, web browsers, database systems, video games
Users
IN LINUX
• People, machines, other computers
| U. K. Roy |
[
]
System Programming in Linux
9
What is an Operating System?
Advanced Java Programming
SYSTEM
A program that acts as an intermediary between a user of a computer and the computer hardware.
PROGRAMMING
Operating system goals:
Execute user programs and make solving user problems easier. Make the computer system convenient to use.
IN LINUX
Puspose:
Use the computer hardware in an efficient manner.
| U. K. Roy |
[
]
System Programming in Linux
10
Operating System Functions?
Advanced Java Programming
Process Management The The The The
creation and deletion of both user and system process suspension and resumption of process provision of mechanisms for process synchronization provision of mechanism for deadlock handling
SYSTEM
Main Memory Management
PROGRAMMING
Keep track of which parts of memory are being used and by whom Decide which processes are to be loaded into the memory when memory space becomes available Allocates and deallocates memory as and when needed
| U. K. Roy |
IN LINUX
File Management
Creation and deletion of files Creation and deletion of directories The support of primitives for manipulating files and directories [
]
System Programming in Linux
11
Operating System Functions?
Advanced Java Programming
I/O System Management A memory management component including buffering, caching and spooling A general device driver interface Drivers for specific hardware interface
SYSTEM
Secondary Storage Management
PROGRAMMING Free space management Storage allocation Disk Scheduling
Networking
IN LINUX
Communication task
Command Interpreter System Command line interpreter
| U. K. Roy |
[
]
PROCESS
MANAGEMENT
System Programming in Linux
13
Process Management
Advanced Java Programming
SYSTEM
Process Management
Creating and deleting both user and system processes Suspending and resuming processes Providing mechanisms for process synchronization Providing mechanisms for process communication Providing mechanisms for deadlock handling
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
14
Process—Basic Concept
Advanced Java Programming
SYSTEM
A process is a program in execution. It is a unit of work within the system. Program is a passive entity, process is an active entity.
Process needs resources to accomplish its task
PROGRAMMING CPU, memory, I/O, files Initialization data
Process termination requires reclaim of any reusable resources
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
15
Process—Basic Concept
Advanced Java Programming
Single-threaded process has one program counter specifying location of next instruction to execute
SYSTEM
Process executes instructions sequentially, one at a time, until completion
Multi-threaded process has one program counter per thread
Typically system has many processes, some user, some operating system running concurrently on one or more CPUs
PROGRAMMING IN LINUX
Concurrency by multiplexing the CPUs among the processes / threads
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
16
Process States
SYSTEM PROGRAMMING
Possible process states
IN LINUX
running—Instructions are being executed Blocked—Process is waiting for some event to occur Ready—The process in waiting to be assigned to a processor
| U. K. Roy |
Transitions between states shown
[
]
System Programming in Linux
17
Process Control Block(PCB)
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX Fields of a Process Control Block entry | U. K. Roy |
[
]
System Programming in Linux
18
Scheduling—Basic Concept
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX Three level scheduling | U. K. Roy |
[
]
System Programming in Linux
19
Process Scheduling
Advanced Java Programming
Multiprogramming needed for efficiency
SYSTEM
Single user cannot keep CPU and I/O devices busy at all times Multiprogramming organizes jobs (code and data) so CPU always has one to execute
PROGRAMMING A subset of total jobs in system is kept in memory One job selected and run via job scheduling
When it has to wait (for I/O for example), OS switches to another job
| U. K. Roy |
IN LINUX
Context Switch
[
]
System Programming in Linux
20
Process Scheduling
Advanced Java Programming
SYSTEM
Timesharing (multitasking) is logical extension in which CPU switches jobs so frequently that users can interact with each job while it is running, creating interactive computing Response time should be small enough 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
PROGRAMMING IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
21
CPU Scheduling
Advanced Java Programming
Basic Concept
SYSTEM
Maximum CPU utilization obtained with multiprogramming
CPU–I/O Burst Cycle – Process execution consists of a cycle of CPU execution and I/O wait
PROGRAMMING CPU burst distribution
IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
22
Scheduling
SYSTEM PROGRAMMING
IN LINUX
Bursts of CPU usage alternate with periods of I/O wait a CPU-bound process an I/O bound process
| U. K. Roy |
[
]
System Programming in Linux
23
Histogram of CPU-burst Times
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
24
CPU Scheduler
SYSTEM
Selects from among the processes in memory that are ready to execute, and allocates the CPU to one of them
CPU scheduling decisions may take place when a process: 1. 2. 3. 4.
Switches from running to waiting state Switches from running to ready state Switches from waiting to ready Terminates
PROGRAMMING
Scheduling under 1 and 4 is nonpreemptive
All other scheduling is preemptive
| U. K. Roy |
IN LINUX [
]
System Programming in Linux Advanced Java Programming
25
Dispatcher
SYSTEM
Dispatcher module gives control of the CPU to the process selected by the short-term scheduler; this involves: switching context switching to user mode
PROGRAMMING jumping to the proper location in the user program to restart that program
| U. K. Roy |
Dispatch latency – time it takes for the dispatcher to stop one process and start another running
IN LINUX [
]
System Programming in Linux
26
Scheduling Criteria CPU utilization Advanced Java Programming
keep the CPU as busy as possible
SYSTEM
Throughput
# of processes that complete their execution per time unit
Turnaround time
PROGRAMMING amount of time to execute a particular process
Waiting time amount of time a process has been waiting in the ready queue
IN LINUX
Response time
amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment) | U. K. Roy |
[
]
System Programming in Linux
27
Scheduling Algorithm Goals
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
28
Advanced Java Programming First-Come, First-Served (FCFS) Scheduling
SYSTEM
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:
PROGRAMMING P1
| U. K. Roy |
P2
Waiting 0 time for P1 = 0; P2 = 24;24P3 = 2727 Average waiting time: (0 + 24 + 27)/3 = 17
P3
30
IN LINUX [
]
System Programming in Linux
29
FCFS Scheduling (Cont.)
Advanced Java Programming
SYSTEM
Suppose that the processes arrive in the order P2 , P3 , P1 The Gantt chart for the schedule is:
PROGRAMMING P2
| U. K. Roy |
P3
P1
6 =0 P =3 Waiting0time for3P1 = 6; P 2 ; 3 Average waiting time: (6 + 0 + 3)/3 = 3 Much better than previous case Convoy effect short process behind long process
30
IN LINUX [
]
System Programming in Linux
30
Shortest-Job-First (SJR) Scheduling
Advanced Java Programming
Associate with each process the length of its next CPU burst. Use these lengths to schedule the process with the shortest time
SYSTEM
Two schemes:
PROGRAMMING
nonpreemptive – once CPU given to the process it cannot be preempted until completes its CPU burst preemptive – if a new process arrives with CPU burst length less than remaining time of current executing process, preempt. This scheme is know as the Shortest-Remaining-Time-First (SRTF)
| U. K. Roy |
IN LINUX
SJF is optimal – gives minimum average waiting time for a given set of processes [
]
System Programming in Linux
31
Example of Non-Preemptive SJF
Advanced Java Programming
SYSTEM
Process Arrival Time P1 0.0 P2 2.0 P3 4.0 P4 5.0 SJF (non-preemptive)
Burst Time 7 4 1 4
PROGRAMMING
P1
| U. K. Roy |
P3
P2
P4
IN LINUX
0 3 7 8 12 Average waiting time = (0 + 6 + 3 + 7)/4 = 4
16
[
]
System Programming in Linux
32
Example of Preemptive SJF
Advanced Java Programming
SYSTEM
Process P1 P2 P3 P4 SJF (preemptive)
Arrival Time 0.0 2.0 4.0 5.0
Burst Time 7 4 1 4
PROGRAMMING
P1
| U. K. Roy |
P2
P3
P2
P4
P1
IN LINUX
11 0 2 4 5 7 Average waiting time = (9 + 1 + 0 +2)/4 = 3
16
[
]
System Programming in Linux Determining Length of Next CPU Advanced Java Programming Burst
33
Can only estimate the length Can be done by using the length of previous CPU bursts, using exponential averaging
SYSTEM
1. t n = actual lenght of n th CPU burst
PROGRAMMING 2. τ n +1 = predicted value for the next CPU burst
3. α , 0 ≤ α ≤ 1 4. Define : τ n +1 = α t n + (1 − α )τ n .
IN LINUX | U. K. Roy |
[
]
in Linux Prediction of System the Programming Length of the Next CPU Advanced Java Programming Burst
34
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
35
Examples of Exponential Averaging α =0 Advanced Java Programming
τn+1 = τn
SYSTEM
Recent history does not count
α =1 τn+1 = α tn
PROGRAMMING Only the actual last CPU burst counts
If we expand the formula, we get: τn+1 = α tn+(1 - α)α tn -1 + … +(1 - α )j α tn -j + … +(1 - α )n +1 τ0
IN LINUX
Since both α and (1 - α) are less than or equal to 1, each successive term has less weight than its predecessor | U. K. Roy |
[
]
System Programming in Linux
36
Priority Scheduling
Advanced Java Programming
A priority number (integer) is associated with each process
The CPU is allocated to the process with the highest priority (smallest integer ≡ highest priority)
SYSTEM
Preemptive Nonpreemptive
PROGRAMMING
SJF is a priority scheduling where priority is the predicted next CPU burst time
Problem ≡ Starvation – low priority processes may never execute
Solution ≡ Aging – as time progresses increase the priority of the process
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux
37
Round Robin (RR)
Advanced Java Programming
SYSTEM
Each process gets a small unit of CPU time (time quantum), 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.
Performance
PROGRAMMING IN LINUX
q large ⇒ FIFO
q small ⇒ q must be large with respect to context switch, otherwise overhead is too high
| U. K. Roy |
[
]
System Programming in Linux Example of RR with Time Quantum = Advanced Java Programming 20
38
SYSTEM
Process P1 P2 P3 P4 The Gantt chart is:
Burst Time 53 17 68 24
PROGRAMMING
P1
0
| U. K. Roy |
P2
20
37
P3
P4
57
P1
77
P3
P4
P1
P3
P3
97 117 121 134 154 162
IN LINUX
Typically, higher average turnaround than SJF, but better response
[
]
System Programming in Linux
39
Advanced Java Programming Time Quantum and Context Switch Time
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
40
Advanced Java Programming Turnaround Time Varies With The Time Quantum
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
41
Multilevel Queue Ready queue is partitioned into separate queues: Advanced Java Programming
SYSTEM
foreground (interactive) background
Each queue has its own scheduling algorithm
PROGRAMMING foreground – RR background – FCFS
Scheduling must be done between the queues
IN LINUX
Fixed priority scheduling
• serve all from foreground then from background—Possibility of starvation.
Time slice
• each queue gets a certain amount of CPU time which it can schedule amongst its processes; e.g., 80% to foreground in RR and 20% to background in FCFS | U. K. Roy |
[
]
System Programming in Linux
42
Multilevel Queue Scheduling
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
43
Multilevel Feedback Queue
Advanced Java Programming
SYSTEM
A process can move between the various queues aging can be implemented this way
Multilevel-feedback-queue scheduler defined by the following parameters:
PROGRAMMING
number of queues scheduling algorithms for each queue method used to determine when to upgrade a process method used to determine when to demote a process method used to determine which queue a process will enter when that process needs service
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux Example of Multilevel Feedback Advanced Java Programming Queue
44
Three queues:
SYSTEM
Q0 – RR with time quantum 8 milliseconds Q1 – RR time quantum 16 milliseconds Q2 – FCFS
PROGRAMMING
Scheduling
| U. K. Roy |
A new job enters queue Q0 which is served RR. When it gains CPU, job receives 8 milliseconds. If it does not finish in 8 milliseconds, job is moved to queue Q1.
IN LINUX
At Q1 job is again served RR and receives 16 additional milliseconds. If it still does not complete, it is preempted and moved to queue Q2. [
]
System Programming in Linux
45
Multiple-Processor Scheduling
Advanced Java Programming
CPU scheduling more complex when multiple CPUs are available
Homogeneous processors within a multiprocessor
SYSTEM
Any available processor can be used to run any process
Heterogeneous processors program complied must run on that processor
PROGRAMMING
Load sharing
Use separate queue for each processor
• One could be idle while another was very busy
Use Common ready queue
IN LINUX
• Each processor picks a process—may result inconsistency • Use one processor as scheduler—creates master-slave relationship
Asymmetric multiprocessing
| U. K. Roy |
only one processor accesses the system data structures Others executes user processes
[
]
System Programming in Linux
46
Real-Time Scheduling
Advanced Java Programming
Hard real-time systems required to complete a critical task within a guaranteed amount of time
SYSTEM
Soft real-time systems
requires that critical processes receive priority over less fortunate ones
PROGRAMMING
Schedulable real-time system
Given
m events (processes) process i occurs within period Pi and requires Ci seconds
IN LINUX C ∑ ≤1
Then the load can only be handled if m
i =1
| U. K. Roy |
i
Pi
[
]
System Programming in Linux
47
Algorithm Evaluation
Advanced Java Programming
Criteria used in selecting an algorithm Maximum CPU utilization under the constraint the maximum response time is 1 second
SYSTEM
Maximum throughput such that average turnaround time linearly proportional to execution time
PROGRAMMING
Deterministic Modeling
Evaluates using a predetermined work load
• can not cope with the dynamic behavior of the system
IN LINUX
Queueing Models
Uses mathematical analysis
• Complicated—hence used unrealistic assumtions • Uses some assumptions—that may not occur • An approximation of real system and accuracy is questionable | U. K. Roy |
[
]
PROCESS
SYNCHRONIZATION
System Programming in Linux
49
Process Synchronization
Advanced Java Programming
Background
The Critical-Section Problem
Simple Solutions
Solutions using Synchronization Hardware
Semaphores
SYSTEM
PROGRAMMING Solutions of Classic Problems of Synchronization
IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
50
Background
Cooperating Processes Processes that can affect or be affected by other processes Implementation uses shared logical address space or shared data using files
SYSTEM
Concurrent access to shared data may result in data inconsistency
PROGRAMMING Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes
IN LINUX
Suppose that we wanted to provide a solution to the consumer-producer problem
| U. K. Roy |
[
]
System Programming in Linux
51
Producer-Consumer Problem
Advanced Java Programming
Representative of operating system process
SYSTEM
while (true) { … /* produce an item to nextp */ while (count == BUFFER_SIZE) ; // buffer is full, do nothing buffer [in] = nextp; in = (in + 1) % BUFFER_SIZE; count++; … }
while (true) { … while (count == 0) ; // buffer is empty, do nothing nextc = buffer[out]; out = (out + 1) % BUFFER_SIZE; count--; /* consume the item from nextc … }
PROGRAMMING IN LINUX
Producer process
| U. K. Roy |
Consumer process
[
]
System Programming in Linux Advanced Java Programming
52
Race Condition
count++ could be implemented as register1 = count register1 = register1 + 1 count = register1
SYSTEM
count-- could be implemented as register2 = count register2 = register2 - 1 count = register2
PROGRAMMING Consider this execution interleaving with “count = 5” initially: S0: producer execute register1 = count {register1 = 5} S1: producer execute register1 = register1 + 1 {register1 = 6} S2: consumer execute register2 = count {register2 = 5} S3: consumer execute register2 = register2 - 1 {register2 = 4} S4: producer execute count = register1 {count = 6 } S5: consumer execute count = register2 {count = 4}
IN LINUX
Race condition Outcome depends upon the order of execution
| U. K. Roy |
[
]
System Programming in Linux
53
Solution to Critical-Section Problem
Advanced Java Programming
Critical Section segment of code where shared variables are used
SYSTEM
Solution must satisfy the following criteria
Mutual Exclusion
If process Pi is executing in its critical section, then no other processes can be executing in their critical sections
PROGRAMMING
Progress
If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely
IN LINUX
Bounded Waiting
A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted
Assume that each process executes at a nonzero speed No assumption concerning relative speed of the N processes
| U. K. Roy |
[
]
System Programming in Linux
54
Two process solution
Advanced Java Programming
Solution 1 Assume that the LOAD and STORE instructions are atomic; that is, cannot be interrupted. The two processes share a variable: int turn;
SYSTEM
The variable turn indicates whose turn it is to enter the critical section. while (true) { … while (turn != i) ;
PROGRAMMING
IN LINUX turn = j;
REMAINDER SECTION
}
Structure of process i | U. K. Roy |
[
]
System Programming in Linux
55
Two process solution
Advanced Java Programming
Solution 2 The two processes share a variable:
SYSTEM
Boolean flag[2]
The flag array is used to indicate if a process is ready to enter the critical section. flag[i] = true implies that process Pi is ready!
while (true) { … flag[i]=true; while (flag[j]) ;
PROGRAMMING
IN LINUX flag[i]=false;
REMAINDER SECTION
} Structure of process i | U. K. Roy |
[
]
System Programming in Linux
56
Two process solution
Advanced Java Programming
Solution 3
SYSTEM
while (true) { … flag[i]=true; turn=j while (flag[j] && turn==j) ;
PROGRAMMING
flag[i]=false;
IN LINUX
REMAINDER SECTION }
Structure of process i | U. K. Roy |
[
]
System Programming in Linux
57
Synchronization Hardware
Advanced Java Programming
Many systems provide hardware support for critical section code
SYSTEM
Uniprocessors – could disable interrupts Currently running code would execute without preemption Generally too inefficient on multiprocessor systems
PROGRAMMING • Operating systems using this not broadly scalable
Modern machines provide special atomic hardware instructions • Atomic = non-interruptible
IN LINUX
Either test memory word and set value Or swap contents of two memory words
| U. K. Roy |
[
]
System Programming in Linux
58
TestAndSet Instruction
Advanced Java Programming
Definition:
SYSTEM
bool TestAndSet (bool &target) { bool temp = target; target = true; return temp: }
PROGRAMMING
Solution using TestAndSet
Shared boolean variable lock., initialized to false.
while (true) { while ( TestAndSet (lock )) ; /* do nothing lock = FALSE; // remainder section }
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
59
Swap Instruction
Advanced Java Programming
Definition:
SYSTEM
void Swap (bool &a, bool &b) { bool temp = a; a = b; b = temp: }
Solution Shared Boolean variable lock initialized to false; Each process has a local Boolean variable key. Solution:
PROGRAMMING while (true) { key = true; while ( key == true) Swap (lock, key ); // critical section lock = false; // remainder section }
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
60
Semaphore
Synchronization tool that does not require busy waiting
Semaphore S – integer variable
Two standard operations modify S: wait() and signal() Originally called P() and V()
Less complicated
Can only be accessed via two indivisible (atomic) operations
SYSTEM
PROGRAMMING wait (S) { while S <= 0 ; // no-op S--; }
IN LINUX
signal (S) { S++; } | U. K. Roy |
[
]
System Programming in Linux
61
Semaphore as General Synchronization Tool
Advanced Java Programming
Counting semaphore – integer value can range over an unrestricted domain
Binary semaphore – integer value can range only between 0 and 1; can be simpler to implement
SYSTEM
Also known as mutex, locks
Can implement a counting semaphore S as a binary semaphore
Provides mutual exclusion
PROGRAMMING Semaphore S; // initialized to 1 wait (S); Critical Section signal (S);
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
62
Solution of other Synchronization Problem
Advanced Java Programming
Two processes P1 and P2 are running concurrently: P1 with a statement S1 and P2 with a statement S2
Requirement:
SYSTEM
S2 be executed only after S1
Solution:
PROGRAMMING Use a a semaphore variable sync initialized to 0
… S1
… wait(sync)
IN LINUX Signal(sync)
S2
…
…
Process P1
| U. K. Roy |
Process P2
[
]
System Programming in Linux
63
Semaphore Implementation
Advanced Java Programming
Must guarantee that no two processes can execute wait () and signal () on the same semaphore at the same time
Thus, implementation becomes the critical section problem where the wait and signal code are placed in the crtical section.
SYSTEM
Could now have busy waiting in critical section implementation • But implementation code is short • Little busy waiting if critical section rarely occupied
PROGRAMMING
Note that applications may spend lots of time in critical sections and therefore this is not a good solution.
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
64
Semaphore Implementation with no Busy waiting
Advanced Java Programming
With each semaphore there is an associated waiting queue. Each entry in a waiting queue has two data items:
SYSTEM
value (of type integer)
a list of processes L waiting on this semaphore
PROGRAMMING Two operations:
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.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
65
Advanced Java Programming Semaphore Implementation with no Busy waiting (Cont.)
Implementation of wait:
SYSTEM
wait (S){ value--; if (value < 0) { add this process to waiting queue block(); } }
PROGRAMMING
Implementation of signal:
IN LINUX
Signal (S){ value++; if (value <= 0) { remove a process P from the waiting queue wakeup(P); } | U. K. Roy}|
[
]
System Programming in Linux
66
Deadlock and Starvation
Advanced Java Programming
Deadlock – two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes
Let S and Q be two semaphores initialized to 1
SYSTEM
P0
P1
PROGRAMMING wait (S); wait (Q); . . . signal (S); signal (Q);
wait (Q); wait (S); . . . signal (Q); signal (S);
IN LINUX
Starvation – indefinite blocking. A process may never be removed from the semaphore queue in which it is suspended.
| U. K. Roy |
[
]
System Programming in Linux
67
Advanced Java Programming Classical Problems of Synchronization
SYSTEM
Bounded-Buffer Problem Readers and Writers Problem Dining-Philosophers Problem
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
68
Bounded-Buffer Problem
Advanced Java Programming
SYSTEM
N buffers, each can hold one item Semaphore mutex initialized to the value 1 Semaphore full initialized to the value 0 Semaphore empty initialized to the value N.
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
69
Bounded Buffer Problem (Cont.)
Advanced Java Programming
The structure of the producer process
The structure of the consumer process
SYSTEM while (true) {
while (true) { //
wait (full); wait (mutex);
produce an item
PROGRAMMING // remove an item from buffer
wait (empty); wait (mutex);
signal (mutex); signal (empty);
// add the item to the buffer
}
| U. K. Roy |
// consume the removed item
IN LINUX
signal (mutex); signal (full);
}
[
]
System Programming in Linux
70
Readers-Writers Problem
Advanced Java Programming
A data set is shared among a number of concurrent processes
SYSTEM
Readers – only read the data set; they do not perform any updates Writers – can both read and write.
Problem – allow multiple readers to read at the same time. Only one writer can access the shared data at the same time.
PROGRAMMING
Shared Data
Data set Semaphore mutex initialized to 1. Semaphore wrt initialized to 1. Integer readcount initialized to 0.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
71
Readers-Writers Problem (Cont.)
Advanced Java Programming
SYSTEM
The structure of a writer process
while (true) { wait (wrt) ;
The structure of a reader process
while (true) { wait (mutex) ; readcount ++ ; if (readercount == 1) wait (wrt) ; signal (mutex)
PROGRAMMING //
writing is performed
// reading is performed
signal (wrt) ;
}
wait (mutex) ; readcount - - ; if (redacount == 0) signal (wrt) ; signal (mutex) ;
IN LINUX }
| U. K. Roy |
[
]
System Programming in Linux
72
Dining-Philosophers Problem
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX
• Shared data
Bowl of rice (data set)
Semaphore chopstick [5] initialized to 1 | U. K. Roy |
[
]
System Programming in Linux
73
Dining-Philosophers Problem (Cont.)
Advanced Java Programming
The structure of Philosopher i:
SYSTEM
While (true) { wait ( chopstick[i] ); wait ( chopStick[ (i + 1) % 5] );
PROGRAMMING // eat
signal (chopstick[ (i + 1) % 5] ); signal ( chopstick[i] );
IN LINUX // think
}
| U. K. Roy |
[
]
System Programming in Linux
74
Dining-Philosophers Problem (Cont.)
Advanced Java Programming
Deadlock free solution Allow at most four philosophers to be sitting simultaneously at the table Allow a philosopher to pick up chopsticks only both are available
SYSTEM
While (true) { wait(mutex) wait ( chopstick[i] ); wait ( chopStick[ (i + 1) % 5] ); signal(mutex) // eat wait (mutex) signal (chopstick[ (i + 1) % 5] ); signal ( chopstick[i] ); signal(mutex) // think }
PROGRAMMING IN LINUX
Asymmetric solution
• Odd philosopher will pick first left then right while even philosopher picks up first left and then right chopstick | U. K. Roy |
[
]
System Programming in Linux
75
Problems with Semaphores
Advanced Java Programming
•
Correct use of semaphore operations: •
SYSTEM
signal (mutex) …. wait (mutex)
• Mutual exclusion requirement is violated •
wait (mutex) … wait (mutex)
PROGRAMMING • Violation of progress condition • Possibility of deadlock
•
Omitting of wait (mutex) or signal (mutex) (or both) • Violation of mutual exclusion or deadlock
IN LINUX
| U. K. Roy |
[
]
DEADLOCKS
System Programming in Linux Advanced Java Programming
77
Deadlocks
SYSTEM
The Deadlock Problem System Model Deadlock Characterization Methods for Handling Deadlocks Deadlock Prevention Deadlock Avoidance Deadlock Detection Recovery from Deadlock
PROGRAMMING
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
78
The Deadlock Problem
Advanced Java Programming
In a multiprogramming Environment several processes compete for finite number of resources
A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set.
SYSTEM
PROGRAMMING
Example 1
System has 2 disk drives. P1 and P2 each hold one disk drive and each needs another one.
Example 2
IN LINUX
semaphores A and B, initialized to 1 P0 wait (A); wait (B);
P1 wait(B) wait(A)
Example 3 Each philosopher picks left chopstick in dining philosopher problem | U. K. Roy |
[
]
System Programming in Linux
79
Bridge Crossing Example
Advanced Java Programming
SYSTEM
Traffic only in one direction.
Each section of a bridge can be viewed as a resource.
If two cars approach each other at the crossing, neither can
PROGRAMMING
start until the other has gone(Dead locks)
If a deadlock occurs, it can be resolved if one car backs up
IN LINUX
(preempt resources and rollback).
Several cars may have to be backed up if a deadlock occurs.
Starvation is possible.
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
80
System Model
Resource types R1, R2, . . ., Rm
SYSTEM
CPU cycles, memory space, I/O devices
Each resource type Ri has Wi instances.
Example—two CPU, Three printers, 2 disk drives
PROGRAMMING
Process may requests as many resources as it requires to perform its designated task Must be less the total number of resources available
Each process utilizes a resource as follows: Request—If the request can not be granted immediately, the requesting process must wait Use Release
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
81
Deadlock Characterization
Advanced Java Programming
Deadlock can arise if four conditions hold simultaneously.
SYSTEM
Mutual exclusion: at least one resource must in non-sharable mode i.e. only one process at a time can use that resource.
Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes.
PROGRAMMING No preemption: a resource can be released only voluntarily by the process holding it, after that process has completed its task. Circular wait: there exists a set {P0, P1, …, Pn} of waiting processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2, …, Pn–1 is waiting for a resource that is held by Pn, and Pn is waiting for a resource that is held by P0.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
82
Resource-Allocation Graph
Advanced Java Programming
Used to visualize resource allocation pattern Helps to describe deadlock more precisely
A set of vertices V and a set of edges (directed) E
V is partitioned into two types:
SYSTEM
PROGRAMMING P = {P1, P2, …, Pn}, the set consisting of all the processes in the system. R = {R1, R2, …, Rm}, the set consisting of all resource types in the system.
IN LINUX
E is partitioned into two types:
request edge – directed edge Pi → Rj
assignment edge – directed edge Rj → Pi | U. K. Roy |
[
]
System Programming in Linux
83
Resource-Allocation Graph (Cont.)
Advanced Java Programming
SYSTEM
Process
Resource Type with 4 instances
PROGRAMMING
| U. K. Roy |
Pi requests an instance of Rj
Pi
Rj
Pi
IN LINUX
Pi is holding an instance of Rj
Rj
[
]
System Programming in Linux
84
Example of a Resource Allocation Graph
Advanced Java Programming
The sets P, R and E
SYSTEM
P = {P1, P2, P3}
R = {R1, R2, R3, R4}
E = {P1 R1, P2 R3, R1 P2 ,
R2 P2, R2 P1, R3 P3}
PROGRAMMING
Resource Instances
One instance of resource type R1
Two instances of resource type R2
IN LINUX
One instance of resource type R3
Three instances of resource type R3
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
85
Basic Facts
SYSTEM
If graph contains no cycles ⇒ no deadlock.
If graph contains a cycle ⇒
if only one instance per resource type, then deadlock.
PROGRAMMING if several instances per resource type, possibility of deadlock.
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
86
Resource Allocation Graph With A Deadlock
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
87
Graph With A Cycle But No Deadlock
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
88
Methods for Handling Deadlocks
Advanced Java Programming
Three methods for dealing with the deadlock problem
SYSTEM
Ensure that the system will never enter a deadlock state. • Deadlock prevention—ensure that one of the necessary conditions can not hold • Deadlock avoidance—systems additional information about resource usage pattern during the execution
PROGRAMMING Allow the system to enter a deadlock state and then recover.
Ignore the problem and pretend that deadlocks never occur in the system; used by most operating systems, including UNIX.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
89
Deadlock Prevention
Advanced Java Programming
• ensure that one of the necessary conditions can not hold
SYSTEM
• Restrain the ways request can be made.
Mutual Exclusion – not required for sharable resources; must hold for nonsharable resources.
Hold and Wait – must guarantee that whenever a process requests a resource, it does not hold any other resources.
Two possibilities
PROGRAMMING Require process to request and be allocated all its resources before it begins execution allow process to request resources only when the process has none.
IN LINUX
• Low resource utilization; possibility of starvation • Data inconsistency
| U. K. Roy |
[
]
System Programming in Linux
90
Deadlock Prevention (Cont.)
Advanced Java Programming
No Preemption – Two possibilities
SYSTEM
If a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released.
PROGRAMMING If a process requests some resources that are not available as they are allocated to other waiting processes, then preempt desired resources from waiting processes
• Preempted resources are added to the list of resources for which the process is waiting. • Process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
91
Deadlock Prevention (Cont.)
Advanced Java Programming
Circular Wait – impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration.
SYSTEM
F(tape drive)=1 F(disk drive)=5 F(printer)=12
PROGRAMMING Facts:I
If a process currently holds resource type Ri , the process can request another resource type Rj if F(Rj) > F(Ri)
OR If a process requests a resource type Rj , if it has released any resource type Ri such the F(Ri) ≥ F(Rj)
IN LINUX
Proof(by contradiction):
Set of deadlocked process {P0, P1, P2, …, Pn}
F(R0) < F(R1) < F(R2) <…< F(Rn) < F(R0) which is impossible | U. K. Roy |
So there can be no circular wait—no deadlock
[
]
System Programming in Linux
92
Deadlock Avoidance
Advanced Java Programming
•
Requires that the system has some additional information available.
•
With this additional information, system can decide whether a newly arrived request can be satisfied (served) or not
SYSTEM
Simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need.
PROGRAMMING
The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
93
Safe State
state is defined by the number of available and allocated resources, and the maximum demands of the processes.
System is in safe state if there exists a sequence of ALL the processes in the systems such that for each Pi, the resources that Pi can still request can be satisfied by currently available resources + resources held by all the Pj, with j < i.
That is:
SYSTEM
PROGRAMMING If Pi needs some resources that are not immediately available, then Pi can wait until all Pj have finished.
When Pj is finished, Pi can obtain needed resources, execute, return allocated resources, and terminate.
IN LINUX
When Pi terminates, Pi +1 can obtain its needed resources, and so on.
When a process requests an available resource, system must decide if immediate allocation leaves the system in a safe state.
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
Basic Facts
If a system is in safe state ⇒ no deadlocks.
If a system is in unsafe state ⇒ possibility of deadlock.
Avoidance ⇒ ensure that a system will never enter an unsafe state.
94
SYSTEM
Example: 12 disk drives Snapshot at time T0: Maximum needs Current Needs P0 10 5 P1 4 2 P2 9 2 The sequence is safe At time T1 P2 requests one more disk drive Satisfying the request leaves the system in an unsafe state can not be granted | U. K. RoyRequest | [ ]
PROGRAMMING IN LINUX
System Programming in Linux
95
Safe, Unsafe , Deadlock State
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
96
Avoidance algorithms
Advanced Java Programming
SYSTEM
Single instance of a resource type. Use a resource-allocation graph
Multiple instances of a resource type. Use the banker’s algorithm
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
97
Resource-Allocation Graph Scheme
Advanced Java Programming
Claim edge Pi → Rj indicated that process Pj may request resource Rj; represented by a dashed line.
Claim edge converts to request edge when a process requests a resource.
SYSTEM
PROGRAMMING Request edge converted to an assignment edge when the resource is allocated to the process.
When a resource is released by a process, assignment edge reconverts to a claim edge.
Resources must be claimed a priori in the system.
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux
98
Resource-Allocation Graph
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
99
Resource-Allocation Graph Algorithm
Advanced Java Programming
SYSTEM
Suppose that process Pi requests a resource Rj
The request can be granted only if converting the request edge to an assignment edge does not result in the formation of a cycle (including the claim edge )in the resource allocation graph
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
100
Unsafe State In Resource-Allocation Graph
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
101
Banker’s Algorithm
Advanced Java Programming
SYSTEM
Multiple instances.
Each process must a priori claim maximum use.
PROGRAMMING
When a process requests a resource it may have to wait.
When a process gets all its resources it must return them in a finite amount of time.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
102
Data Structures for the Banker’s Algorithm
Advanced Java Programming
Let n = number of processes, and m = number of resources types.
SYSTEM
Available: Vector of length m. If Available [j] = k, there are k instances of resource type Rj available.
Max: n x m matrix. If Max [i,j] = k, then process Pi may request at most k instances of resource type Rj.
PROGRAMMING Allocation: n x m matrix. If Allocation[i,j] = k then Pi is currently allocated k instances of Rj.
Need: n x m matrix. If Need[i,j] = k, then Pi may need k more instances of Rj to complete its task.
IN LINUX
Need [i,j] = Max[i,j] – Allocation [i,j].
Define X≤Y if X[i] ≤ Y[i] ∀ i
| U. K. Roy |
[
]
System Programming in Linux
103
Safety Algorithm
Advanced Java Programming
1. Let Work and Finish be vectors of length m and n, respectively. Initialize:
SYSTEM
Work = Available Finish [i] = false for i = 0, 1, …, n- 1.
2. Find and i such that both: (a) Finish [i] = false (b) Needi ≤ Work
PROGRAMMING If no such i exists, go to step 4.
Work = Work + Allocationi Finish[i] = true go to step 2.
IN LINUX
4. If Finish [i] == true for all i, then the system is in a safe state. Algorithm requires an order of O(m x n2) operations to detect whether the system is in safe state. | U. K. Roy |
[
]
System Programming in Linux
104
Resource-Request Algorithm for Process Pi
Advanced Java Programming
Requesti = request vector for process Pi. If Requesti [j] = k then process Pi wants k instances of resource type Rj.
SYSTEM
If Requesti ≤ Needi go to step 2. Otherwise, raise error condition, since process has exceeded its maximum claim.
PROGRAMMING
If Requesti ≤ Available, go to step 3. Otherwise Pi must wait, since resources are not available.
3. Pretend to allocate requested resources to Pi by modifying the state as follows: Available = Available – Request; Allocationi = Allocationi + Requesti; Needi = Needi – Requesti;
IN LINUX
If safe ⇒ the resources are allocated to Pi. ● If unsafe ⇒ Pi must wait, and the old resource-allocation state is restored ●
| U. K. Roy |
[
]
System Programming in Linux
105
Example of Banker’s Algorithm
Advanced Java Programming
5 processes P0 through P4; 3 resource types: Available A (10 instances), B (5instances), and C (7 instances).
SYSTEM
PROGRAMMING
Snapshot at time T0: Allocation Max Available ABC ABC ABC P0 0 1 0 753 332 P1 2 0 0 322 P2 3 0 2 902 P3 2 1 1 222 P4 0 0 2 4 3 3
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
106
Example (Cont.)
Advanced Java Programming
The content of the matrix Need is defined to be Max – Allocation.
SYSTEM Need ABC 743 122 600 011 431
PROGRAMMING P0 P1 P2 P3 P4
| U. K. Roy |
IN LINUX
The system is in a safe state since the sequence < P1, P3, P4, P2, P0> satisfies safety criteria. [
]
System Programming in Linux
107
Example: P1 Request (1,0,2)
Advanced Java Programming
Check that Request ≤ Available (that is, (1,0,2) ≤ (3,3,2) ⇒ true. Allocation Need Available ABC ABC ABC P0 0 1 0 743 230 P1 3 0 2 020 P2 3 0 1 600 P3 2 1 1 011 P4 0 0 2 431 Executing safety algorithm shows that sequence < P1, P3, P4, P0, P2> satisfies safety requirement. Can request for (3,3,0) by P4 be granted? Can request for (0,2,0) by P0 be granted?
SYSTEM
PROGRAMMING | U. K. Roy |
IN LINUX
[
]
System Programming in Linux
108
Deadlock Detection
Advanced Java Programming
Allow system to enter deadlock state
System must provide
SYSTEM
Detection algorithm • Checks the state of the system to determine whether a deadlock has occured
PROGRAMMING Recovery scheme
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
109
Single Instance of Each Resource Type
Advanced Java Programming
SYSTEM
Maintain wait-for graph Nodes are processes.
Pi → Pj if Pi is waiting for Pj.
PROGRAMMING
Periodically invoke an algorithm that searches for a cycle in the graph. If there is a cycle, there exists a deadlock.
An algorithm to detect a cycle in a graph requires an order of n2 operations, where n is the number of vertices in the graph.
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux
110
Resource-Allocation Graph and Wait-for Graph
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX
ResourceAllocation Graph
| U. K. Roy |
Corresponding waitfor graph
[
]
System Programming in Linux
111
Several Instances of a Resource Type
Advanced Java Programming
SYSTEM
Available: A vector of length m indicates the number of available resources of each type.
Allocation: An n x m matrix defines the number of resources of each type currently allocated to each process.
PROGRAMMING
Request: An n x m matrix indicates the current request of each process. If Request [ij] = k, then process Pi is requesting k more instances of resource type. Rj.
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
112
Detection Algorithm
Advanced Java Programming
1. Let Work and Finish be vectors of length m and n, respectively Initialize: (a) Work = Available For i = 1,2, …, n, if Allocationi ≠ 0, then Finish[i] = false;otherwise, Finish[i] = true.
SYSTEM
2. Find an index i such that both: (a) Finish[i] == false (b) Requesti ≤ Work
PROGRAMMING If no such i exists, go to step 4.
3. Work = Work + Allocationi Finish[i] = true go to step 2.
IN LINUX
4. If Finish[i] == false, for some i, 1 ≤ i ≤ n, then the system is in deadlock state. Moreover, if Finish[i] == false, then Pi is deadlocked. Algorithm requires an order of O(m x n2) operations to detect whether the system is in deadlocked state. | U. K. Roy |
[
]
System Programming in Linux
113
Example of Detection Algorithm
Advanced Java Programming
Five processes P0 through P4; three resource types A (7 instances), B (2 instances), and C (6 instances).
SYSTEM
Snapshot at time T0: Allocation Request ABC ABC P0 010 000 P1 200 202 P2 303 000 P3 211 100 P4 002 002
Available ABC 000
PROGRAMMING
IN LINUX
Sequence will result in Finish[i] = true for all i.
| U. K. Roy |
[
]
System Programming in Linux
114
Example (Cont.)
Advanced Java Programming
P2 requests an additional instance of type C. Request ABC P0 0 0 0 P1 2 0 1 P2 0 0 1 P3 1 0 0 P4 0 0 2 State of system?
SYSTEM
PROGRAMMING
IN LINUX
Can reclaim resources held by process P0, but insufficient resources to fulfill other processes; requests. Deadlock exists, consisting of processes P1, P2, P3, and P4. | U. K. Roy |
[
]
System Programming in Linux
115
Detection-Algorithm Usage
Advanced Java Programming
When, and how often, to invoke depends on:
SYSTEM
How often a deadlock is likely to occur?
How many processes will need to be rolled back? • one for each disjoint cycle
Run deadlock detection detection algorithm every time a request can not be granted
PROGRAMMING Considerably overhead
Run once per hour Run when CPU/resource utilization drops below 40% If detection algorithm is invoked arbitrarily, there may be many cycles in the resource graph and so we would not be able to tell which of the many deadlocked processes “caused” the deadlock.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
116
Recovery from Deadlock: Process Termination
Advanced Java Programming
Abort all deadlocked processes.
Abort one process at a time until the deadlock cycle is eliminated.
In which order should we choose to abort?
SYSTEM
PROGRAMMING Priority of the process. How long process has computed, and how much longer to completion. Resources the process has used. Resources process needs to complete. How many processes will need to be terminated. Is process interactive or batch?
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
117
Recovery from Deadlock: Resource Preemption
Advanced Java Programming
SYSTEM
Selecting a victim – minimize cost.
Rollback – return to some safe state, restart process for that state.
PROGRAMMING Starvation – same process may always be picked as victim, include number of rollback in cost factor.
IN LINUX | U. K. Roy |
[
]
Memory Management
System Programming in Linux
119
Memory Management
Advanced Java Programming
SYSTEM
Background Swapping Contiguous Memory Allocation Paging Structure of the Page Table Segmentation Example: The Intel Pentium
PROGRAMMING
IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
120
Objectives
SYSTEM
To provide a detailed description of various ways of organizing memory hardware To discuss various memory-management techniques, including paging and segmentation To provide a detailed description of the Intel Pentium, which supports both pure segmentation and segmentation with paging
PROGRAMMING
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
121
Background
Advanced Java Programming
SYSTEM
Program must be brought (from disk) into memory and placed within a process for it to be run Main memory and registers are only storage CPU can access directly Register access in one CPU clock (or less) Main memory can take many cycles Cache sits between main memory and CPU registers Protection of memory required to ensure correct operation
PROGRAMMING
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux
122
Base and Limit Registers
Advanced Java Programming
SYSTEM
A pair of base and limit registers define the logical address space
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
123
Binding of Instructions and Data to Memory
Advanced Java Programming
SYSTEM
Address binding of instructions and data to memory addresses can happen at three different stages Compile time: If memory location known a priori, absolute code can be generated; must recompile code if starting location changes Load time: Must generate relocatable code if memory location is not known at compile time Execution time: Binding delayed until run time if the process can be moved during its execution from one memory segment to another. Need hardware support for address maps (e.g., base and limit registers)
PROGRAMMING IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
124
Multistep Processing of a User Program
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
125
Logical vs. Physical Address Space
Advanced Java Programming
SYSTEM
The concept of a logical address space that is bound to a separate physical address space is central to proper memory management Logical address – generated by the CPU; also referred to as virtual address Physical address – address seen by the memory unit
PROGRAMMING
Logical and physical addresses are the same in compile-time and load-time addressbinding schemes; logical (virtual) and physical addresses differ in execution-time address-binding scheme
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
126
Memory-Management Unit (MMU)
Advanced Java Programming
SYSTEM
Hardware device that maps virtual to physical address
In MMU scheme, the value in the relocation register is added to every address generated by a user process at the time it is sent to memory
PROGRAMMING
The user program deals with logical addresses; it never sees the real physical addresses
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
127
Dynamic relocation using a relocation register
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
128
Dynamic Loading
Advanced Java Programming
SYSTEM
Routine is not loaded until it is called Better memory-space utilization; unused routine is never loaded Useful when large amounts of code are needed to handle infrequently occurring cases No special support from the operating system is required implemented through program design
PROGRAMMING
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
129
Dynamic Linking
Advanced Java Programming
SYSTEM
Linking postponed until execution time Small piece of code, stub, used to locate the appropriate memory-resident library routine Stub replaces itself with the address of the routine, and executes the routine Operating system needed to check if routine is in processes’ memory address Dynamic linking is particularly useful for libraries System also known as shared libraries
PROGRAMMING
| U. K. Roy |
IN LINUX [
]
System Programming in Linux Advanced Java Programming
130
Swapping
SYSTEM
A process can be swapped temporarily out of memory to a backing store, and then brought back into memory for continued execution
Backing store – fast disk large enough to accommodate copies of all memory images for all users; must provide direct access to these memory images
PROGRAMMING
Roll out, roll in – swapping variant used for prioritybased scheduling algorithms; lower-priority process is swapped out so higher-priority process can be loaded and executed
Major part of swap time is transfer time; total transfer time is directly proportional to the amount of memory swapped
Modified versions of swapping are found on many systems (i.e., UNIX, Linux, and Windows) System maintains a ready queue of ready-to-run processes which have memory images on disk
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux
131
Schematic View of Swapping
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
132
Contiguous Allocation
Advanced Java Programming
SYSTEM
Main memory usually into two partitions:
Resident operating system, usually held in low memory with interrupt vector User processes then held in high memory
Relocation registers used to protect user processes from each other, and from changing operating-system code and data
PROGRAMMING Base register contains value of smallest physical address Limit register contains range of logical addresses – each logical address must be less than the limit register MMU maps logical address dynamically
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
133
HW address protection with base and limit registers
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
134
Contiguous Allocation (Cont.)
Advanced Java Programming
SYSTEM
Multiple-partition allocation
Hole – block of available memory; holes of various size are scattered throughout memory When a process arrives, it is allocated memory from a hole large enough to accommodate it Operating system maintains information about: a) allocated partitions b) free partitions (hole)
PROGRAMMING OS
OS
OS
OS
process 5
process 5
process 5
process 5
process 9
process 9
process 8 process 2
| U. K. Roy |
IN LINUX
process 10
process 2
process 2
process 2
[
]
System Programming in Linux
135
Advanced Java Programming Dynamic Storage-Allocation Problem
SYSTEM
How to satisfy a request of size n from a list of free holes
First-fit: Allocate the first hole that is big enough Best-fit: Allocate the smallest hole that is big enough; must search entire list, unless ordered by size
PROGRAMMING Produces the smallest leftover hole
Worst-fit: Allocate the largest hole; must also search entire list Produces the largest leftover hole
Firstfit and bestfit better than worstfit in terms of speed and storage utilization
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
136
Fragmentation
Advanced Java Programming
SYSTEM
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 Reduce external fragmentation by compaction
PROGRAMMING
Shuffle memory contents to place all free memory together in one large block Compaction is possible only if relocation is dynamic, and is done at execution time I/O problem
IN LINUX
• Latch job in memory while it is involved in I/O • Do I/O only into OS buffers
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
137
Paging
SYSTEM
Logical address space of a process can be noncontiguous; process is allocated physical memory whenever the latter is available Divide physical memory into fixed-sized blocks called frames (size is power of 2, between 512 bytes and 8,192 bytes) Divide logical memory into blocks of same size called pages Keep track of all free frames To run a program of size n pages, need to find n free frames and load program Set up a page table to translate logical to physical addresses Internal fragmentation
PROGRAMMING
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux
138
Address Translation Scheme
Advanced Java Programming
SYSTEM
Address generated by CPU is divided into:
Page number (p) – used as an index into a page table which contains base address of each page in physical memory
PROGRAMMING Page offset (d) – combined with base address to definepage number the physical memory address that is page offset sent to the memory unit p d m n
n
IN LINUX
For given logical address space 2m and page size 2n | U. K. Roy |
[
]
System Programming in Linux
139
Paging Hardware
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
140
Advanced Java Programming Paging Model of Logical and Physical Memory
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
141
Paging Example
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX 32byte memory and 4byte pages | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
142
Free Frames
SYSTEM PROGRAMMING IN LINUX Before allocation | U. K. Roy |
After allocation [
]
System Programming in Linux
143
Implementation of Page Table
Advanced Java Programming
SYSTEM
Page table is kept in main memory Page-table base register (PTBR) points to the page table Page-table length register (PRLR) indicates size of the page table In this scheme every data/instruction access requires two memory accesses. One for the page table and one for the data/instruction. The two memory access problem can be solved by the use of a special fast-lookup hardware cache called associative memory or translation look-aside buffers (TLBs) Some TLBs store address-space identifiers (ASIDs) in each TLB entry – uniquely identifies each process to provide address-space protection for that process
PROGRAMMING
| U. K. Roy |
IN LINUX [
]
System Programming in Linux
144
Associative Memory
Advanced Java Programming
SYSTEM
Associative memory – parallel search Page #
Frame #
PROGRAMMING Address translation (p, d)
If p is in associative register, get frame # out Otherwise get frame # from page table in memory
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
145
Paging Hardware With TLB
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
146
Effective Access Time
Advanced Java Programming
SYSTEM
Associative Lookup = ε time unit Assume memory cycle time is 1 microsecond Hit ratio – percentage of times that a page number is found in the associative registers; ratio related to number of associative registers Hit ratio = α Effective Access Time (EAT) EAT = (1 + ε) α + (2 + ε)(1 – α) =2+ε–α
PROGRAMMING
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
147
Memory Protection
Advanced Java Programming
SYSTEM
Memory protection implemented by associating protection bit with each frame
Valid-invalid bit attached to each entry in the page table:
PROGRAMMING “valid” indicates that the associated page is in the process’ logical address space, and is thus a legal page “invalid” indicates that the page is not in the process’ logical address space
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux Valid (v) or Invalid (i) Bit In A Page Advanced Java Programming Table
148
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
149
Shared Pages
SYSTEM
Shared code
One copy of read-only (reentrant) code shared among processes (i.e., text editors, compilers, window systems). Shared code must appear in same location in the logical address space of all processes
PROGRAMMING
Private code and data
Each process keeps a separate copy of the code and data
IN LINUX
The pages for the private code and data can appear anywhere in the logical address space
| U. K. Roy |
[
]
System Programming in Linux
150
Shared Pages Example
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
151
Structure of the Page Table
Advanced Java Programming
SYSTEM
Hierarchical Paging
Hashed Page Tables
PROGRAMMING
Inverted Page Tables
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
152
Hierarchical Page Tables
Advanced Java Programming
SYSTEM
Break up the logical address space into multiple page tables
A simple technique is a two-level page table
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
153
Two-Level Page-Table Scheme
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
154
Two-Level Paging Example
Advanced Java Programming
SYSTEM
A logical address (on 32-bit machine with 1K page size) is divided into: a page number consisting of 22 bits a page offset consisting of 10 bits
PROGRAMMING
Since the page table is paged, the page number is further divided into: a 12-bit page number page number a 10-bit page offset p2 pi
d Thus, a logical address is as follows:
IN LINUX 12
| U. K. Roy |
page offset
10
10
[
]
System Programming in Linux
155
Address-Translation Scheme
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
156
Three-level Paging Scheme
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
157
Hashed Page Tables
Advanced Java Programming
SYSTEM
Common in address spaces > 32 bits
The virtual page number is hashed into a page table. This page table contains a chain of elements hashing to the same location.
PROGRAMMING
Virtual page numbers are compared in this chain searching for a match. If a match is found, the corresponding physical frame is extracted.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
158
Hashed Page Table
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
159
Inverted Page Table
Advanced Java Programming
SYSTEM
One entry for each real page of memory Entry consists of the virtual address of the page stored in that real memory location, with information about the process that owns that page Decreases memory needed to store each page table, but increases time needed to search the table when a page reference occurs Use hash table to limit the search to one — or at most a few — page-table entries
PROGRAMMING
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux
160
Inverted Page Table Architecture
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
161
Segmentation
SYSTEM
Memory-management scheme that supports user view of memory A program is a collection of segments. A segment is a logical unit such as: main program, procedure, function, method, object, local variables, global variables, common block, stack, symbol table, arrays
PROGRAMMING IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
162
User’s View of a Program
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
163
Logical View of Segmentation
Advanced Java Programming
1
1
SYSTEM 4
2
PROGRAMMING 3
4
2 3
IN LINUX
user space
| U. K. Roy |
physical memory space
[
]
System Programming in Linux
164
Segmentation Architecture
Advanced Java Programming
SYSTEM
Logical address consists of a two tuple: <segment-number, offset>, Segment table – maps two-dimensional physical addresses; each table entry has:
base – contains the starting physical address where the segments reside in memory limit – specifies the length of the segment
PROGRAMMING
Segment-table base register (STBR) points to the segment table’s location in memory Segment-table length register (STLR) indicates number of segments used by a program; segment number s is legal if s < STLR
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
165
Segmentation Architecture (Cont.)
Advanced Java Programming
Protection
SYSTEM
With each entry in segment table associate: • validation bit = 0 ⇒ illegal segment • read/write/execute privileges
Protection bits associated with segments; code sharing occurs at segment level Since segments vary in length, memory allocation is a dynamic storage-allocation problem A segmentation example is shown in the following diagram
PROGRAMMING
| U. K. Roy |
IN LINUX [
]
System Programming in Linux
166
Segmentation Hardware
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
167
Example of Segmentation
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
168
Example: The Intel Pentium
Advanced Java Programming
SYSTEM
Supports both segmentation and segmentation with paging CPU generates logical address Given to segmentation unit
PROGRAMMING • Which produces linear addresses
Linear address given to paging unit
• Which generates physical address in main memory • Paging units form equivalent of MMU
IN LINUX | U. K. Roy |
[
]
System Programming in Linux Logical to Physical Address Translation in Advanced Java Programming Pentium
169
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
170
Intel Pentium Segmentation
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
171
Pentium Paging Architecture
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
172
Linear Address in Linux
Advanced Java Programming
SYSTEM
Broken into four parts:
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
173
Three-level Paging in Linux
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
LINUX COMMANDS
System Programming in Linux Advanced Java Programming
175
Objectives
SYSTEM
In this session, you will learn to: Use the basic Unix commands like pwd date
PROGRAMMING who ls
man
Use “man” pages
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
176
Simple commands
Advanced Java Programming
pwd
SYSTEM
Displays the current working directory.
date
PROGRAMMING Displays the current date and time
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
177
Simple commands
Advanced Java Programming
who
SYSTEM
Displays the names of all the users who have currently logged in
PROGRAMMING
who am i
Displays the name of the current user.
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
178
Listing contents of directory
Advanced Java Programming
• • •
ls Syntax options:
• •
PROGRAMMING column
•
SYSTEM
:ls [options] [file….] -l list in long format -a list all file including those beginning with a dot -i list inode no of file in first
file
•
directories • •
| U. K. Roy |
-s
reports disk blocks occupied by
-R
recursively list all sub
IN LINUX -F -C
mark type of each file display files in columns
[
]
System Programming in Linux
179
Meta characters
Advanced Java Programming
Meta Characters * ? […]
Purpose
SYSTEM Example
Match with one or more characters or none Match with any single character Match with any single character within the brackets ; Command separator | Pipe two commands () Group commands Useful when the output of thecommand group has to be redirected `command` Execute the command enclosed within back quotes. Useful when the output of a command into a variable in a shell script
$ ls –l *.c file* $ ls –l file? $ ls –l file[abc]
$ cat file1; cat file2 $ cat abc | wc $ (echo “==== x.c ====”; cat x.c) > out
PROGRAMMING
‘string’ “string”
| U. K. Roy |
count=`expr $count + 1`
assuming count has value3, this increments the value of count echo ‘expr $count + 1’ displays expr $count + 1 echo “expr $count + 1” displays expr 3 + 1 assuming the variable count has value 3
IN LINUX
Quote all characters with no substitution (ex. no special meaning for $) Quote all characters with substitution. The characters $, \ (back slash) and back quote have special meaning.
[
]
System Programming in Linux
180
Listing contents of directory
Advanced Java Programming
$ ls –l
SYSTEM
total 6 -rwxr-xr-x drwxr-xr-x -rw-r--r--rw-------rw-r--r--
1 2 1 1 1
user1 user2 user1 user1 user3
projA projD projA projA projC
12373 4096 12831 61440 255
Dec Dec Dec Dec Dec
15 22 12 15 20
14:45 14:00 13:59 11:16 14:29
a.out awkpro c core cs
PROGRAMMING File access permissions
File type
User id
Link count
Group id
File size in bytes
Date & time of modification
File name
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
181
Getting help on commands
Advanced Java Programming
•
The Unix manual, usually called man pages, is available on-line to explain the usage of the Unix system and commands.
•
Syntax: man [options] command_name
•
SYSTEM
PROGRAMMING Common Options -k keyword list command synopsis line for all keyword matches -M path path to man pages -a show all matching man pages (SVR4)
• •
IN LINUX
info command_name - help for the internal commands help -–command_name– gives command synatx
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
•
•
182
Summary
SYSTEM
In this session, you have learned to … use the basic Unix commands like • pwd • date • who • ls • man use “man” pages
PROGRAMMING IN LINUX
| U. K. Roy |
[
]
FILES AND
DIRECTORIES
System Programming in Linux Advanced Java Programming
184
Objectives
SYSTEM
In this session, you will learn to:
set file permissions using the chmod command use directory-related commands namely mkdir, rmdir, cd commands
PROGRAMMING use file-related commands namely cp, mv, rm commands
access advanced file permissions using commands umask, suid, sgid, linking files, stickybit create and edit files using the vi editor
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
185
File access permissions
Advanced Java Programming
Refers to the permissions associated with a file with respect to the following
Permission Levels
SYSTEM
User (owner) (u)
PROGRAMMING Group (wheel, staff, daemon, etc.) (g)
World (guest, anonymous and all other users) (o)
Permission Settings Read (r)
IN LINUX
Write (w)
Execute (x)
| U. K. Roy |
[
]
System Programming in Linux
186
File access permissions
Advanced Java Programming
No read permission does not allow the user to:
SYSTEM
List the contents of directory Remove the directory
No Write permission does not allow the user to : copy files to the directory
PROGRAMMING remove files from the directory rename files in the directory make a subdirectory
remove a subdirectory from the directory
IN LINUX
move files to, and from the directory
| U. K. Roy |
[
]
System Programming in Linux
187
File access permissions
Advanced Java Programming
SYSTEM
No execute permission does not allow the user to: display the contents of a directory file from within the directory
PROGRAMMING change to the directory
display a file in the directory
IN LINUX
copy a file to, or from the directory
| U. K. Roy |
[
]
System Programming in Linux
188
Changing permissions - chmod
Advanced Java Programming
chmod u+x file_name Syntax: chmod or chmod filename
SYSTEM
PROGRAMMING Octal 4 2 3
Number - for read - for write - for execution
IN LINUX
$ chmod 744 xyz this will set rwx for user, r– for group, r—for others
| U. K. Roy |
[
]
System Programming in Linux
189
Directory creation
Advanced Java Programming
Command Syntax mkdir [OPTION] DIRECTORY $mkdir <path>/ $mkdir –m $mkdir –p //
SYSTEM
PROGRAMMING
Example:
mkdir project1
IN LINUX
This creates a directory project1 under current directory
Note: Write and execute permissions are needed for the user to create a directory
| U. K. Roy |
[
]
System Programming in Linux
190
Directory removal
Advanced Java Programming
rmdir command removes directory Syntax
SYSTEM
rmdir
Example Removes project1 directory in the current directory
rmdir project1
PROGRAMMING
| U. K. Roy |
Remove multiple directories rmdir pos1 pos2 Remove the directory recursively rmdir –p dir1/dir2/dir2 Rule: rmdir can be executed to remove a directory if it is empty and not the current directory
IN LINUX
[
]
System Programming in Linux
191
Command - cd
Advanced Java Programming
SYSTEM
cd command is used to change the directory
PROGRAMMING cd cd .. cd /
- take to the home directory - takes to the parent directory - takes to the root directory
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
192
File related commands
Advanced Java Programming
File
SYSTEM
Operation
Copying
a file
Command cp
mv
PROGRAMMING
Moving
a file
Removing
Displaying
a file
cat
IN LINUX
a file and concatenating files
| U. K. Roy |
rm
[
]
System Programming in Linux
193
Command - cp
Advanced Java Programming
SYSTEM
Used to copy files across directories Syntax cp <source file>
PROGRAMMING
Example cp file1 file2
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
194
Command - cp
Advanced Java Programming
-p
SYSTEM
Copies the file and preserves the following attributes • • • •
owner id group id permissions last modification time
PROGRAMMING -r
recursive copy; copy subdirectories under the directory if any
-i
IN LINUX
interactive; prompts for confirmation before overwriting the target file, if it already exists
| U. K. Roy |
[
]
System Programming in Linux
195
Command - mv
Advanced Java Programming
SYSTEM
Used to move a file, or rename a file
Preserves the following details • • • •
owner id group id permissions Last modification time
PROGRAMMING
-f
suppresses all prompting (forces overwriting of target)
-i
prompts before overwriting destination file
| U. K. Roy |
IN LINUX [
]
System Programming in Linux
196
Command – rm
Advanced Java Programming
Used to remove a file •
SYSTEM
Syntax : rm file(s)
-f
suppresses all prompting
-i
prompts before overwriting destination file
-r will recursively remove the file from a directory (can be used to delete a directory along with the content )
Caution: Use “i” option along with “r” to get notified on deletion
PROGRAMMING
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux
197
Command – chown & chgrp
Advanced Java Programming
$ ls –l -rwxr-xr-x -rwxr-xr-x
$chown user2 a.out
$ls –l -rwxr-xr-x -rwxr-xr-x
1user1 training 3 user1 faculty
12373 Dec 15 14:45 a.out 4096 Dec 24 11:56 awkpro
SYSTEM
1user2 3 user1
training faculty
12373 Dec 15 14:45 a.out 4096 Dec 24 11:56 awkpro
PROGRAMMING $ chgrp training awkpro $ls –l -rwxr-xr-x -rwxr-xr-x
| U. K. Roy |
1user2 3 user1
training training
12373 Dec 15 14:45 a.out 4096 Dec 24 11:56 awkpro
IN LINUX
[
]
System Programming in Linux
198
Command - umask
Advanced Java Programming
umask value is used to set the default permission of a file and directory while creating
umask command is used to see the default mask for the file permission
Default umask value will be set in the system environment file like /etc/profile
umask 022 will set a mask of 022 for the current session
SYSTEM
PROGRAMMING The file permission after setting this umask value will be 644 And the directory permission will be 755
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
199
Command - ln
Advanced Java Programming
Linking files
Hard Link (in the same filesystem)
SYSTEM
$ ln /usr/bin/clear /usr/bin/cls
PROGRAMMING Hard link uses the same inode number
Soft Link (in different filesystems also used to link directories)
IN LINUX
$ ln –s /usr/bin/clear /home/user1/cls
| U. K. Roy |
[
]
System Programming in Linux
200
Special permission bits
Advanced Java Programming
Set user ID (SUID)
SYSTEM
This means that if the SUID bit is set for any application then your user ID would be set as that of the owner of application/file rather than the current user, while running that application
PROGRAMMING “set user ID” bit can be set in one of the two ways: • chmod u+s
• chmod 4755
IN LINUX
• The leftmost octal number 4 indicates “set user ID” bit to be set, other octal digits indicate regular file permissions. This is meaningful for executable files only.
| U. K. Roy |
[
]
System Programming in Linux
201
Special permission bits
Advanced Java Programming
Set group id (SGID)
SYSTEM
Just like SUID, setting the SGID bit for a file sets your group ID to the file's group while the file is executing “set group ID” bit can be set in one of the two ways:
PROGRAMMING • chmod g+s
• chmod 2755
• The leftmost octal number 2 indicates “set group ID” bit to be set, other octal digits indicate regular file permissions. This is meaningful for executable files only.
IN LINUX
Click to edit Master text styles | U. K. Roy |
Second level • Third level
[
]
System Programming in Linux
202
Special permission bits
Advanced Java Programming
Sticky bit (SVTX)
SYSTEM
Typically set to a directory that is shareable
Any user can create a file in such sharable directory Only owner of the file or super user (root) can remove a file from the directory
PROGRAMMING “sticky” bit can be set in one of the two ways: • chmod +t
• chmod 1555
IN LINUX
• The leftmost octal number 1 indicates “sticky” bit to be set, other octal digits indicate regular file permissions.
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
203
vi editor
vi is a visual editor used to create and edit text files.
SYSTEM
A screen-oriented text editor
Included with most UNIX system distributions Command driven
PROGRAMMING
Categories of commands include Cursor movement
Editing commands
Search and replace commands
IN LINUX
The vi editor is invoked by the following command: vi
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
Ba ckspa ce
the
q uick
the 2 the b
q uick
SYSTEM
brown w
w
Spa ce
fox
k
l
the
q uick
w
brown
fox
brown
fox
$
the
q uick
brown
fox
^
w q uick
Navigation
j
h
204
brown b
fox b
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
205
Editing commands
Advanced Java Programming
Text insertion / replacement
SYSTEM
i
- inserts text to the left of the cursor
a
- inserts text to the right of the cursor
I
- inserts text at the beginning of the line
PROGRAMMING A
- appends text at end of the line
o
- opens line below
O
- opens line above
R
- replaces text from cursor to right
s
- replaces a single character with any number of
IN LINUX characters
S
| U. K. Roy |
- replaces entire line
[
]
System Programming in Linux
206
Editing commands
Advanced Java Programming
Deletion
SYSTEM
x
- to delete character at cursor position
3x
- to delete 3 characters at cursor position
dw
- to delete word
2dw
- to delete 2 word
dd
- to delete a line
2dd
- to delete 2 lines
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
207
Editing commands
Advanced Java Programming
Yanking Y- copy 3Y p P
SYSTEM
line into buffer - copy 3 lines into buffer - copy buffer below cursor - copy buffer above cursor
PROGRAMMING
Save and quit :w :w! :x :q :q!
| U. K. Roy |
-
to save to name a file (:w! filename -> save as) save and quit cancel changes cancel and quit
IN LINUX
[
]
System Programming in Linux
208
Search & replace commands
Advanced Java Programming
The following commands are applicable for vi editor in Linux
/pat cursor
SYSTEM
searches for the pattern pat and places where pattern occurs.
PROGRAMMING
/
repeat last search
:%s/old/new/g file.
to change every occurrence in the whole
IN LINUX
:#,#s/old/new/g numbers of
| U. K. Roy |
where #,# are replaced with the the two lines.
[
]
System Programming in Linux Advanced Java Programming
209
Summary
SYSTEM
In this session, you have learned how to … use file permissions using the chmod command use directory-related commands namely mkdir, rmdir, cd commands use file-related commands namely cp, mv, rm commands access advanced file permissions using commands umask, suid, sgid, linking the files, stickybit create and edit files using the vi editor
PROGRAMMING IN LINUX
| U. K. Roy |
[
]
Chapter 4 UNIX
Utilities
System Programming in Linux Advanced Java Programming
211
Objectives
In this session, you will learn to:
SYSTEM
use the Unix Utilities like
• cat, echo, touch, more, file, wc, cmp, comm, find
employ redirection operators use filters like
PROGRAMMING • sort, grep, cut, head, tail, tr, and paste
use communication commands • telnet, ftp
use backup commands
IN LINUX
• zip/gzip and tar
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
212
cat
•
cat command takes the input from the keyboard, and sends the output to the monitor
•
We can redirect the input and output using the redirection operators
SYSTEM
PROGRAMMING $ cat>file1 Type the content here press $ cat file1 Displays the content of the file $cat>>file1 (will append to the content of the file)
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
touch
SYSTEM
touch is used to change the time stamp of the file
Syntax: touch [options] file Options:
213
PROGRAMMING a to change the access time m to change the modification time c no create if not exists
touch will change the time of change of the file if the file exists
If the file does not exist, it will create a file of zero byte size.
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux Advanced Java Programming
214
echo & read
echo command is used to print output to the screen echo “This is an example” This is an example
SYSTEM
PROGRAMMING x=10 echo $x 10
IN LINUX
read command allows to read input from user and assign it to the variable specified. read x
| U. K. Roy |
[
]
System Programming in Linux
215
General purpose utilities
Advanced Java Programming
more
SYSTEM
Allows user to view one page-full of information at a time.
file
Used to display the type of the file
PROGRAMMING tty
Prints the terminal’s name
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
216
General purpose utilities
Advanced Java Programming
wc
SYSTEM
A filter used to count the number of lines, words, and characters in a disk file or from the standard input. -l
- displays the number of lines
-w
- displays the number of words
-c
- displays the number of characters
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
217
General purpose utilities
Advanced Java Programming
cmp
SYSTEM
Returns the offset and the line number of the first position where the two files differ.
comm
PROGRAMMING col1 - unique lines of first file
col2 - unique lines of second file col3 - common lines
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
218
General purpose utilities
Advanced Java Programming
diff
SYSTEM
Indicate the differences between the files a Lines added
d Lines deleted c Lines changed
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
219
find
Lets user to search set of files and directories based on various criteria Syntax: find [path...] [expression] [path]
SYSTEM
[expression] PROGRAMMING where to search
what type of file to search (specified with –type option) What action to be applied (–exec, –print, etc.) Name of the files (specified as part of –name option, enclosed in “ “)
IN LINUX
Example
find . –name “*.c” -print | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
220
find
Finding files on the basis of file size
SYSTEM
– size [+ –]n[bc]
• n represents size in bytes (c) or blocks (b) of 512 bytes • find . –size 1000c lists all files that are exactly 1000 bytes in size • find . –size +1000c lists all files that are more than 1000 bytes in size • find . –size –1000c lists all files that are less than 1000 bytes in size
PROGRAMMING IN LINUX
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
221
find
Finding files on the basis of access time (atime) or modified time (mtime)
SYSTEM
– atime [+-]n
– mtime [+-]n
PROGRAMMING •
n represents number of days ( actually 24 * n hours)
• find . –atime 2 days ago • find . –atime +2 2 days ago • find / –mtime –2 2 days ago
lists files accessed exactly 2
lists files accessed more than
IN LINUX
| U. K. Roy |
lists files modified less than
[
]
System Programming in Linux Advanced Java Programming
222
find
Applying a command on files matching the criteria with – exec and –ok options
SYSTEM
– exec command {} \;
• command is command to be applied on the matching files (does not prompt user) • find . -name “*.dat” –exec ls –l {} \; • Long listing of all files with .dat extension in the current and its subdirectories
PROGRAMMING -ok command {} \;
IN LINUX
• Functionality is similar to –exec, but prompts user before applying the command on the file matching the criteria.
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
•
•
pr
223
pr
SYSTEM
•
Used to display a file in a format to be printed.
•
Breaks up a file into pages with a header, text and footer area
PROGRAMMING Options
| U. K. Roy |
-l
to alter the length of the file
-h
to set the header
-t
to suppress the header and the footer
-n
to set the line number
IN LINUX [
]
System Programming in Linux
224
Standard files
Advanced Java Programming
Standard Input file
SYSTEM
Keyboard, file descriptor is 0
Standard Output file Monitor, file descriptor is 1
PROGRAMMING Standard Error file
Monitor, file descriptor is 2
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
225
I/O redirection
Advanced Java Programming
< file redirect standard input from file > file redirect standard output to file 2> file redirect standard error to file 2>&1 merge standard error with standard output $ cat > abc
SYSTEM
PROGRAMMING $ ls –l > outfile
$ cat xyz abc > outfile 2> errfile
$ cat xyz abc > outfile 2>&1
| U. K. Roy |
IN LINUX [
]
System Programming in Linux Advanced Java Programming
226
Filters
Filters are programs that takes its input from the standard input file, process it, and sends it to the standard output file.
Commonly used filter commands
SYSTEM
PROGRAMMING sort
grep cut
head tail paste
| U. K. Roy |
IN LINUX [
]
System Programming in Linux Advanced Java Programming
sort
SYSTEM
Sorts the contents of the given file based on the first char of each line. -n --numeric sort -r --Reverse sort -t -Specify delimiter for fields
PROGRAMMING
+num -specify sorting field numbers +num -num - to specify the range
can specify the characters in the field
227
| U. K. Roy |
IN LINUX [
]
System Programming in Linux Advanced Java Programming
228
grep
SYSTEM
grep -Global Regular Expression Printer is used for searching regular expressions Syntax grep <pattern>
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
229
grep options
Advanced Java Programming
-c
SYSTEM
occurrences -n
displays count of the number of
displays line numbers along with the lines
PROGRAMMING -v
displays all lines except lines matching pattern -i
| U. K. Roy |
Ignores case for matching
IN LINUX [
]
System Programming in Linux Advanced Java Programming
230
Patterns
* - matches 0 or more characters
[^pqr] - Matches a single character which is not p ,q or r
^pqr -Matches pqr at the beginning of the line
SYSTEM
PROGRAMMING pqr$ -Matches pqr at the end of the line
“.” - Matches any one character
\ - ignores the special meaning. grep “New\[abc\]” filename
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux
231
Filter command - head
Advanced Java Programming
SYSTEM
Displays the top n lines of the file
Can specify top n lines to be displayed
$ head -3 file1
PROGRAMMING IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
232
Filter command - tail
Advanced Java Programming
Displays the end of the file Can specify last n lines to be displayed
$ tail -3 file1
SYSTEM
PROGRAMMING Can also specify the line number from which the data has to be displayed $ tail +5 file1
| U. K. Roy |
IN LINUX [
]
System Programming in Linux
233
Filter command - tr
Advanced Java Programming
SYSTEM
tr - translate filter used to translate a given set of characters
usage :
PROGRAMMING tr [a-z] [A-Z]
option -s can be used to squeeze the repeated characters.
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
234
Filter command - tr
Advanced Java Programming
SYSTEM
Useful options for tr
-s char
Squeeze multiple contiguous occurrences of the character into single char
PROGRAMMING
-d char
Remove the character
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
235
Command piping
Advanced Java Programming
SYSTEM
•
Allows the output (only the standard output) of a command to be sent as input to another command.
•
Multiple pipes may appear in one command line.
PROGRAMMING Example:
$ cat * | wc
$ cat fil1 | head | wc -l
| U. K. Roy |
IN LINUX [
]
System Programming in Linux
236
Filter command - tee
Advanced Java Programming
•
tee command allows the normal output to the standard output, as well as to a file
•
Useful to capture intermediate output of a long command pipeline for further processing, or debugging purpose.
•
SYSTEM
PROGRAMMING Example • •
| U. K. Roy |
who | tee userlist cat - | tee file1 | wc -l
IN LINUX [
]
System Programming in Linux
237
Filter command - cut
Advanced Java Programming
Used to extract specified columns from the output of certain commands -c used to extract characters -d Delimiter for fields -f Field no. Examples cut -c2-5 file1 cut -d “|” -f2,3 file1
SYSTEM
PROGRAMMING IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
238
Filter command - paste
Advanced Java Programming
Paste is used to fix two cut portions of the file vertically
-s
SYSTEM
Pastes the contents of file2 below file1
PROGRAMMING -d Specify delimiter
$ paste -d”|” file1 file2
IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
239
telnet
SYSTEM
telnet hostname or telnet
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
ftp hostname
240
ftp
SYSTEM
put/send: Transfer to Other hosts put [local_file [remote_file]]
PROGRAMMING get/recv: Transfer From Other hosts
get [remote_file [local_file]]
IN LINUX
mput: Multiple Transfer to Other hosts
| U. K. Roy |
[
]
System Programming in Linux
241
Compression utilities
Advanced Java Programming
SYSTEM
gzip, Usage is very similar to compress and pack utilities in Unix: gzip [-vc] filename
PROGRAMMING
where -v displays the compression ratio. -c sends the compressed output to standard output and leaves the original file intact.
IN LINUX
gunzip gunzip can uncompress files originally compressed with compress.
| U. K. Roy |
[
]
System Programming in Linux
242
Tape archive - tar
Advanced Java Programming
SYSTEM
•
Tar is an archiving utility to store and retrieve files from an archive, known as tarfile.
•
Though archives are created on a tape, it is common to have them as disk files as well.
PROGRAMMING –
tar c|t|x [vf destination] source...
Examples: Create a new tar file containing all .dat files (assuming a.dat, b.dat and c.dat exist) $ tar –cf mytar *.dat
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux Advanced Java Programming
•
243
Summary
In this session, you have learned to: •
•
SYSTEM
use the Unix Utilities like • cat, echo, touch, more, file, wc, cmp, comm, find employ redirection operators use filters like • sort, grep, cut, head, tail, tr, and paste communication commands • telnet, ftp backup commands • zip/gzip and tar
PROGRAMMING •
•
•
| U. K. Roy |
IN LINUX
[
]
Chapter 5 Process
System Programming in Linux Advanced Java Programming
•
245
Objectives
In this session, you will learn to:
SYSTEM
•
Define a process
•
Use process-related commands like • ps, kill, sleep
•
Start a Background process
•
Use background and foreground-related commands like • bg, fg, jobs , nice , nohup
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
246
Process
SYSTEM
•
Process - a program in execution
•
When program is executed, a new process is created.
•
The process is alive till the execution of the program is complete.
•
Each process is identified by a number called pid.
PROGRAMMING
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux Advanced Java Programming
247
Login shell
As soon as the user logs in, a process is created which executes the login shell.
Login shell is set for each login in /etc/passwd file.
SYSTEM
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
248
ps
•
The ps command is used to display the characteristics of a process
•
It fetches the pid, tty, time, and the command which has started the process.
SYSTEM
PROGRAMMING -f
lists the pid of the parent process also.
-u
lists the processes of a given user
-a
lists the processes of all the users
-e
lists all the processes including the system processes
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
249
Background process
Advanced Java Programming
SYSTEM
Enables the user to do more than one task at a time.
If the command terminates with an ampersand (&), UNIX executes the command in the background
Shell returns by displaying the process ID (PID) and job id of the process
PROGRAMMING IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
250
Background process
Advanced Java Programming
nohup
SYSTEM
Lets processes to continue to run even after logout The output of the command is sent to nohup.out if not redirected
PROGRAMMING $ nohup command args
$ nohup sort emp.lst & [1] 21356
IN LINUX
nohup: appending output to `nohup.out'
| U. K. Roy |
[
]
System Programming in Linux
251
Background process
Advanced Java Programming
SYSTEM
wait command
can be used when a process has to wait for the output of a background process The wait command, can be used to let the shell wait for all background processes terminate.
PROGRAMMING $ wait
It is possible to wait for completion of one specific process as well.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
252
Controlling background process
Advanced Java Programming
SYSTEM
•
jobs
•
List the background process fg % <job id> •
PROGRAMMING Runs a process in the foreground bg %<job id> •
•
•
Runs a process in the background
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
253
Process priority
Advanced Java Programming
•
nice •
SYSTEM
Used to reduce the priority of jobs
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
254
kill
SYSTEM
•
kill: Kills or terminates a process
•
kill command send a signal to the process The default signal is 15 ( SIGTERM)
PROGRAMMING •
kill -9 (SIGKILL) • Terminates the process abruptly
IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
•
255
Summary
In this session, you learned to:
SYSTEM
•
Define a process
•
Use process-related commands like • ps, kill, sleep
•
Start a background process
•
Use background and foreground-related commands like • bg, fg, jobs
PROGRAMMING IN LINUX | U. K. Roy |
[
]
Chapter 6 UNIX
Shell Programming
System Programming in Linux Advanced Java Programming
•
257
Objectives
In this session, you will learn to:
SYSTEM
•
Use Shell variables
•
Write scripts to process positional parameters
•
Use “test” command
•
Use “if” construct
•
Use “for” loop
•
Use “while” loop
•
Use “case” construct
•
Define and use functions
•
Debug shell scripts
PROGRAMMING
| U. K. Roy |
IN LINUX [
]
System Programming in Linux
258
Flavors of UNIX shell
Advanced Java Programming
SYSTEM
•
Bourne shell
•
C shell
•
Korn shell
•
Bourne again shell bash (shell distributed with linux)
•
sh
csh
PROGRAMMING ksh
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
259
Command processing
Advanced Java Programming
SYSTEM
•
Displays the shell prompt and reads the command typed by the user.
•
Interprets the command and classifies it as an internal (built-in), or an external command.
•
If it is NOT a built-in command, searches for the command in the PATH-specified directories, and executes that command if it is found.
PROGRAMMING IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
260
Shell features
Advanced Java Programming
SYSTEM
Parent shell process fork
(bash)
$ vi test.c
command typed by user
PROGRAMMING Child shell process (bash)
Exec of “vi test.c”
User Mode Kernel Mode
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
261
Additional shell features
Advanced Java Programming
SYSTEM
Each shell, apart from the basic features, provides additional features such as:
•
PROGRAMMING Maintaining command history (C, korn and bash) Renaming (aliasing) a command (C, korn, bash) Command editing (C, korn and bash)
IN LINUX
Programming language (all shells)
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
• • • •
262
History
SYSTEM
some UNIX shells support command history facility to keeps track of commands that were executed facility to rerun previously executed commands bash shell supports the following
PROGRAMMING !!
recall the last command and execute it.
!num
execute nth command where n is the the num specified after !
| U. K. Roy |
IN LINUX [
]
System Programming in Linux Advanced Java Programming
263
alias
SYSTEM
• alias can be used to give new name to an existing command • A better name that represents a single command or a sequence of commands to be executed, often with appropriate options • alias is an internal command
PROGRAMMING alias newname=command $ alias l=‘ls –l’
IN LINUX
The unalias command cancels previously defined alias.
| U. K. Roy |
[
]
System Programming in Linux
264
File name substitution
Advanced Java Programming
•
When the user enters a command string, the shell parses the string into following components: •
SYSTEM
Command (the first part of the string, till the first space char) Command arguments (the subsequent parts of the string)
PROGRAMMING •
•
For example, given the command-string “ls –l *.c”, this string contains the “ls” command and two arguments “-l” and “*.c”.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
265
File name substitution
Advanced Java Programming
•
SYSTEM
In arguments of a command, the shell recognizes certain characters – such as *, ?, [ ], and - as special characters and expands these characters into a filename list before executing the command.
PROGRAMMING
•
To see how this works, enter following commands while in /bin directory
$ ls a*
IN LINUX
$ ls ??
| U. K. Roy |
[
]
System Programming in Linux
266
Shell programming
Advanced Java Programming
•
Allows
SYSTEM
•
Defining and referencing variables
•
Logic control structures such as if, for, while, case
•
Input and output
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
267
Shell variables
Advanced Java Programming
•
A variable is a name associated with a data value, and it offers a symbolic way to represent and manipulate data variables in the shell. They are classified as follows
SYSTEM
•
user-defined variables
•
environment variables
•
predefined variables
PROGRAMMING
•
value assigned to the variable can then be referred to by preceding the variable name with a $ sign.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
268
Shell variables
Advanced Java Programming
SYSTEM
•
The shell provides the facility to define normal, and environment variables.
•
A normal variable can be only used in the shell where it is defined.
•
PROGRAMMING An environment variable can be used in the shell where it is defined, plus any child shells invoked from that shell.
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
269
Using normal variables
Advanced Java Programming
•
To define a normal variable, use the following syntax:
SYSTEM
variable_name=value •
Examples:
PROGRAMMING $ x=10 $ textline_1=‘This line was entered by $USER’ $ textline_2=“This line was entered by $USER” $ allusers=`who` $ usercount=`who | wc –l`
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
270
Using normal variables
Advanced Java Programming
•
SYSTEM
Once variables are defined, one can use the echo command to display the value of each variable:
$ $ $ $ $
echo echo echo echo echo
$x $textline_1 $textline_2 $allusers $usercount
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
271
Using environment variables
Advanced Java Programming
SYSTEM
• • •
To define an environment variable, use following syntax: variable_name=value export variable_name
PROGRAMMING Examples: • $ x=10; export x • $ allusers=`who` ; export allusers
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
272
Built-in environment variables
Advanced Java Programming
SYSTEM
• PATH
• MAIL
• BASH_ENV
• USER
• HOME
• LOGNAME
PROGRAMMING • PWD
• PS1
• SHELL
• PS2
• TERM
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
273
Sample shell script
Advanced Java Programming
SYSTEM
#! /bin/bash # # The above line has a special meaning. It must be the # first line of the script. It says that the commands in # this shell script should be executed by the bash # shell (/bin/bash). # --------------------------------------------------------------echo “Hello $USER….” echo “Welcome to programming shell scripts..” # ---------------------------------------------------------------
PROGRAMMING
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux
274
Executing shell scripts
Advanced Java Programming
There are two ways of executing a shell script:
SYSTEM
By passing the shell script name as an argument to the shell. For example:
PROGRAMMING
sh script1.sh
If the shell script is assigned execute permission, it can be executed using it’s name. For example: ./script1.sh
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux
275
Passing parameters to scripts
Advanced Java Programming
SYSTEM
•
parameter can be passed to a shell script
•
parameters are specified after the name of the shell script when invoking the script.
•
PROGRAMMING
•
Within the shell script, parameters are referenced using the predefined variables $1 through $9.
In case of more than 9 parameters, other parameters can be accessed by shifting.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
276
Built-in variables
Advanced Java Programming
•
SYSTEM
Following are built-in variables supported •
$0, $1…$9 $* $@
- positional arguments - all arguments - all arguments
PROGRAMMING • •
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
277
Passing parameters to scripts
Advanced Java Programming
SYSTEM
•
Consider following shell script:
----------------------script2.sh-------------------------echo “Total parameters entered: $#” echo “First parameter is : $1” echo “The parameters are: $*” shift echo “First parameter is : $1” ------------------------------------------------------------
PROGRAMMING •
| U. K. Roy |
IN LINUX
Execute the above script using the “script2.sh these are the parameters” command.
[
]
System Programming in Linux
278
Passing parameters to scripts
Advanced Java Programming
SYSTEM
•
The shell parameters are passed as strings.
•
to pass a string containing multiple words as a single parameter, it must be enclosed within quotes.
•
PROGRAMMING For example,
parameter”
$ script2.sh “this string is a single
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
279
Doing arithmetic operations
Advanced Java Programming
Arithmetic operations within a shell script can be performed using expr command.
Example, x=10 y=5
•
SYSTEM
PROGRAMMING
•
number_1 = `expr $x + $y` number_2 = `expr $x - $y` number_3 = `expr $x / $y`
IN LINUX
number_4 = `expr $x \* $y`
number_5 = `expr $x % $y`
| U. K. Roy |
[
]
System Programming in Linux
280
Using the test command
Advanced Java Programming
The general syntax of test command is:
SYSTEM
test <expression> •
PROGRAMMING The expression can be formed using a combination of shell variables and the operators supported by the test command. These operators provide facility to compare numbers, string and logical values, file types and file access modes.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
281
Using the test command
Advanced Java Programming
SYSTEM
To compare two integers using test following operators are available: -eq (equal to) -ne (not equal to) -lt (less than) -le (less than or equal to) -gt (greater than) -ge (greater than or equal to)
PROGRAMMING IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
282
Using the test command
Advanced Java Programming
SYSTEM
Please note that you can only compare two integers using test.
General syntax
PROGRAMMING test [expression]
test integer1 operator integer2 OR [ integer1 operator integer2 ]
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
283
Using the test command
Advanced Java Programming
SYSTEM
To compare two strings using the test command, following operators are available: string1 = string2 (equal to, please note it is a single =) string1 != string2 (not equal to) string1 (string is not NULL) -n string1 (string is not NULL and exists) -z string1 (string is NULL and exists)
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
284
Using the test command
Advanced Java Programming
SYSTEM
The syntax for this string comparison is: test string1 operator string2 OR [ string1 operator string2 ] OR test operator string OR [ operator string ]
PROGRAMMING IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
285
Using the test command
Advanced Java Programming
SYSTEM
To check a file type/access permissions using the test command, following operators are available:
-s file (file is not empty and exists)
PROGRAMMING -f file (Ordinary file and exists)
-d file (file is a directory and exists) -r file (file is readable and exists)
-w file (file is write-able and exists)
IN LINUX
-x file (file is executable and exists)
| U. K. Roy |
[
]
System Programming in Linux
286
Using the test command
Advanced Java Programming
To check a file type/access permissions using the test command, following operators are available:
SYSTEM
-b file (file is a block device and exists) -c file (file is a character device and exists)
PROGRAMMING -p file (file is a named pipe and exists) -g file (file has sticky bit set)
-u file (file has setuid bit set)
IN LINUX
-t file_des (file descriptor is standard output)
| U. K. Roy |
[
]
System Programming in Linux
287
Combining conditions
Advanced Java Programming
•
SYSTEM
It is possible to combine conditions by using following operators:
-a (logical AND operator)
PROGRAMMING -o (logical OR operator) ! (logical NOT operator)
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
288
Combining conditions
Advanced Java Programming
The syntax for this is:
SYSTEM
test expression_1 –a expression _2, OR [ expression _1 –a expression _2 ]
PROGRAMMING test expression_1 –o expression _2, OR [ expression_1 –o expression_2 ] test
! expression _1 OR [ ! expression _1 ]
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
289
Condition checking in scripts
Advanced Java Programming
SYSTEM
Bash shell provides the if command to test if a condition is true. The general format of this command is: if condition then command fi
PROGRAMMING
| U. K. Roy |
IN LINUX
The condition is typically formed using the test command.
[
]
System Programming in Linux Advanced Java Programming
290
Example
SYSTEM
# to check if the current directory is the same as your home directory curdir=`pwd` if test “$curdir” != “$HOME” then echo your home dir is not the same as your pesent working directory else echo $HOME is your current directory fi
PROGRAMMING
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux
291
Checking multiple conditions
Advanced Java Programming
SYSTEM
The complex form of if statement is as follows: if condition_1 then
PROGRAMMING command
elif condition_2 then
command else
IN LINUX
command fi
| U. K. Roy |
[
]
System Programming in Linux
292
Using for loop
Advanced Java Programming
SYSTEM
The Bash shell provides a for loop.
is:
The syntax of this loop
Example:
for i in 1 2 3 4 5 do echo -n $i \* $i = " " echo `expr $i \* $i ` done
PROGRAMMING
for variable in list do command … command done
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
293
Example
SYSTEM
----------------------script.sh--------------------------
#! /bin/sh
usernames=`who | cut –d “ “ –f1`
echo “Total users logged in = $#usernames”
PROGRAMMING #
for user in ${usernames} do
echo $user done
IN LINUX
------------------------------------------------------------
| U. K. Roy |
[
]
System Programming in Linux
294
Using while loop
Advanced Java Programming
SYSTEM
The Bash shell provides a while loop. The syntax of this loop is: while condition do command … command done
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
295
Example
SYSTEM
Shell script checks for a blank/non blank string eg: read nam while [ -z “$nam” ] do read nam done echo the string is $nam
PROGRAMMING
the above piece of code keeps accepting string variable nam until it is non zero in length.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
Example
SYSTEM
Shell script to compute factorial of a given number
#!/bin/bash n=$1 if [ $n -eq 0 ]; then fact=0 else fact=1 while [ $n –ne 0 ] do fact=`expr $fact \* $n` n=`expr $n – 1` done fi echo $fact
296
PROGRAMMING
| U. K. Roy |
IN LINUX [
]
System Programming in Linux
297
case statement
Advanced Java Programming
SYSTEM
- THE CASE STATEMENT case value in pattern1) command command;; pattern2) command command;; patternn) command;; esac
PROGRAMMING
| U. K. Roy |
IN LINUX [
]
System Programming in Linux Advanced Java Programming
298
Example
#!/bin/bash echo enter a choice read choice case $choice in 1) echo enter 2 nos read num1 read num2 res=`expr $num1 + $num2` echo result is $res;; 2) who;; *) echo invalid choice;;
SYSTEM
PROGRAMMING esac
| U. K. Roy |
IN LINUX [
]
System Programming in Linux Advanced Java Programming
Example
#!/bin/bash read number case $number 1) echo 1st break;; 2) echo 2nd break;; 3) echo 3rd break;; *) echo ${number}th break;; esac
SYSTEM
299
PROGRAMMING
| U. K. Roy |
IN LINUX [
]
System Programming in Linux Advanced Java Programming
300
Functions
SYSTEM
Shell functions are a way to group commands for later execution using a single name for the group. They are executed just like a "regular" command.
PROGRAMMING
Shell functions are executed in the current shell context; no new process is created to interpret them. Functions are declared using this syntax: [ function ] name () { command-list; }
IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
301
Functions
SYSTEM
Shell functions can accept arguments Arguments are passed in the same way as given to commands Functions refer to arguments using $1, $2 etc., similar to the way shell scripts refer to command line arguments
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
302
Functions
SYSTEM
Function to convert standard input into upper case
toupper() { tr A-Z a-z }
This function can be used as
$ cat abc | toupper
PROGRAMMING
| U. K. Roy |
IN LINUX [
]
System Programming in Linux
303
Debugging shell scripts
Advanced Java Programming
SYSTEM
Two options help in debugging shell scripts “-v” (verbose) option:
causes shell to print the lines of the script as they are read.
PROGRAMMING
$ bash –v script-file
“-x” (verbose) option:
IN LINUX
prints commands and their arguments as they are executed.
| U. K. Roy |
$ bash –x script-file
[
]
System Programming in Linux
304
Programming in C vs shell
Advanced Java Programming
Comparison between
SYSTEM
•
A solution in C
•
A shell solution written like a C program
•
A proper “shell/unix” solution
PROGRAMMING e.g: The problem is to count the no of lines in a file ( the file is called the_file)
IN LINUX | U. K. Roy |
[
]
Programming in C vs shell
C program to count lines in a file #include
<stdio.h> void main(void) { int lcount=0; FILE *infile; char line[500];
infile=fopen("the_file","r"); while(!feof(infile)) { fgets(line,500,infile); lcount ++; } printf("no of lines is %d\n",lcount); }
Solution in Bash count=0 while
read line
do
count=`expr $count +
1` done < the_file echo
Number of lines is $count using existing Solution
commands $ wc –l the_file
System Programming in Linux Advanced Java Programming
•
306
Summary
In this session, you have learned to:
SYSTEM
•
Use Shell variables
•
Write scripts to process positional parameters
•
Use “test” command
•
Use “if” construct
•
Use “for” loop
•
Use “while” loop
•
Use “case” construct
•
Define and use functions
•
Debug shell scripts
PROGRAMMING
| U. K. Roy |
IN LINUX [
]
System Programming in Linux
307
Bibliography
Advanced Java Programming
UNIX for the Impatient, Paul W. Abrahams & Bruce R. Larson (Addison-Wesley Publishing Company, 1992, ISBN 0-20155703-7).
SYSTEM
PROGRAMMING UNIX in a Nutshell for BSD 4.3: A Desktop Quick Reference For Berkeley (O'Reilly & Associates, Inc., 1990, ISBN 0-937175-20-X). (A handy reference for BSD.)
IN LINUX
UNIX in a Nutshell: A Desktop Quick
| U. K. Roy |
[
]
System Programming in Linux
308
Advanced Java Programming
SYSTEM Thank You
PROGRAMMING IN LINUX | U. K. Roy |
[
]
PROGRAMMING
IN LINUX UTTAM K. ROY
Dept. of Information Technology, Jadavpur University, Kolkata
System Programming in Linux
2
Topics to be discussed
Advanced Java Programming
Introduction to Operating Systems and Linux Internals
SYSTEM
General Introduction to Operating Systems Process management Scheduling Memory Management File Management
PROGRAMMING Linux Systems Programming Files and Directories Input/Output System Files Process Control Signals Interprocess Communication Network programming
Linux System Administration Linux Shells and Commands Systems management Managing File Systems Network Management
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
Books
Advanced Java Programming
“Operating System Concepts”,
•
Silberschatz Galvin, Wesley publication
•
Andrew S. Tanenbaum,
•
William Stallings,
•
•
3
SYSTEM
Addison
“Operating Systems”
“Operating Systems”,
Prentice-Hall India
PROGRAMMING Richard Stones & Neil Matthew, “Beginning Programming”, A Wrox publication Sumitabha Das, publication
Linux
“Unix Shell Programming”,
IN LINUX
•
Olaf Kirch, Terry Dawson, “Linux Guide”, A O’relly publication
•
Daniel P. Bovet, Marco Cesati, “Understanding Kernel”, O’Reilly publication
| U. K. Roy |
A Tata McGraw-Hill
Network Administrator's the Linux [
]
INTRODUCTION TO OPERATING SYSTEM
System Programming in Linux
5
Computer System Organization
Advanced Java Programming
Computer-system operation
SYSTEM
One or more CPUs, device controllers connect through common bus providing access to shared memory Concurrent execution of CPUs and devices competing for memory cycles
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
6
Components of a Computer System
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
7
Components (Contd.)
Advanced Java Programming
SYSTEM PROGRAMMING
A computer system consists of
IN LINUX hardware
system programs
application programs
| U. K. Roy |
[
]
System Programming in Linux
8
Components (Contd.)
Advanced Java Programming
SYSTEM
Computer system components
Hardware – provides basic computing resources • CPU, memory, I/O devices
Operating system • Controls and coordinates use of hardware among various applications and users
PROGRAMMING Application programs – define the ways in which the system resources are used to solve the computing problems of the users • Word processors, compilers, web browsers, database systems, video games
Users
IN LINUX
• People, machines, other computers
| U. K. Roy |
[
]
System Programming in Linux
9
What is an Operating System?
Advanced Java Programming
SYSTEM
A program that acts as an intermediary between a user of a computer and the computer hardware.
PROGRAMMING
Operating system goals:
Execute user programs and make solving user problems easier. Make the computer system convenient to use.
IN LINUX
Puspose:
Use the computer hardware in an efficient manner.
| U. K. Roy |
[
]
System Programming in Linux
10
Operating System Functions?
Advanced Java Programming
Process Management The The The The
creation and deletion of both user and system process suspension and resumption of process provision of mechanisms for process synchronization provision of mechanism for deadlock handling
SYSTEM
Main Memory Management
PROGRAMMING
Keep track of which parts of memory are being used and by whom Decide which processes are to be loaded into the memory when memory space becomes available Allocates and deallocates memory as and when needed
| U. K. Roy |
IN LINUX
File Management
Creation and deletion of files Creation and deletion of directories The support of primitives for manipulating files and directories [
]
System Programming in Linux
11
Operating System Functions?
Advanced Java Programming
I/O System Management A memory management component including buffering, caching and spooling A general device driver interface Drivers for specific hardware interface
SYSTEM
Secondary Storage Management
PROGRAMMING Free space management Storage allocation Disk Scheduling
Networking
IN LINUX
Communication task
Command Interpreter System Command line interpreter
| U. K. Roy |
[
]
PROCESS
MANAGEMENT
System Programming in Linux
13
Process Management
Advanced Java Programming
SYSTEM
Process Management
Creating and deleting both user and system processes Suspending and resuming processes Providing mechanisms for process synchronization Providing mechanisms for process communication Providing mechanisms for deadlock handling
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
14
Process—Basic Concept
Advanced Java Programming
SYSTEM
A process is a program in execution. It is a unit of work within the system. Program is a passive entity, process is an active entity.
Process needs resources to accomplish its task
PROGRAMMING CPU, memory, I/O, files Initialization data
Process termination requires reclaim of any reusable resources
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
15
Process—Basic Concept
Advanced Java Programming
Single-threaded process has one program counter specifying location of next instruction to execute
SYSTEM
Process executes instructions sequentially, one at a time, until completion
Multi-threaded process has one program counter per thread
Typically system has many processes, some user, some operating system running concurrently on one or more CPUs
PROGRAMMING IN LINUX
Concurrency by multiplexing the CPUs among the processes / threads
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
16
Process States
SYSTEM PROGRAMMING
Possible process states
IN LINUX
running—Instructions are being executed Blocked—Process is waiting for some event to occur Ready—The process in waiting to be assigned to a processor
| U. K. Roy |
Transitions between states shown
[
]
System Programming in Linux
17
Process Control Block(PCB)
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX Fields of a Process Control Block entry | U. K. Roy |
[
]
System Programming in Linux
18
Scheduling—Basic Concept
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX Three level scheduling | U. K. Roy |
[
]
System Programming in Linux
19
Process Scheduling
Advanced Java Programming
Multiprogramming needed for efficiency
SYSTEM
Single user cannot keep CPU and I/O devices busy at all times Multiprogramming organizes jobs (code and data) so CPU always has one to execute
PROGRAMMING A subset of total jobs in system is kept in memory One job selected and run via job scheduling
When it has to wait (for I/O for example), OS switches to another job
| U. K. Roy |
IN LINUX
Context Switch
[
]
System Programming in Linux
20
Process Scheduling
Advanced Java Programming
SYSTEM
Timesharing (multitasking) is logical extension in which CPU switches jobs so frequently that users can interact with each job while it is running, creating interactive computing Response time should be small enough 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
PROGRAMMING IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
21
CPU Scheduling
Advanced Java Programming
Basic Concept
SYSTEM
Maximum CPU utilization obtained with multiprogramming
CPU–I/O Burst Cycle – Process execution consists of a cycle of CPU execution and I/O wait
PROGRAMMING CPU burst distribution
IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
22
Scheduling
SYSTEM PROGRAMMING
IN LINUX
Bursts of CPU usage alternate with periods of I/O wait a CPU-bound process an I/O bound process
| U. K. Roy |
[
]
System Programming in Linux
23
Histogram of CPU-burst Times
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
24
CPU Scheduler
SYSTEM
Selects from among the processes in memory that are ready to execute, and allocates the CPU to one of them
CPU scheduling decisions may take place when a process: 1. 2. 3. 4.
Switches from running to waiting state Switches from running to ready state Switches from waiting to ready Terminates
PROGRAMMING
Scheduling under 1 and 4 is nonpreemptive
All other scheduling is preemptive
| U. K. Roy |
IN LINUX [
]
System Programming in Linux Advanced Java Programming
25
Dispatcher
SYSTEM
Dispatcher module gives control of the CPU to the process selected by the short-term scheduler; this involves: switching context switching to user mode
PROGRAMMING jumping to the proper location in the user program to restart that program
| U. K. Roy |
Dispatch latency – time it takes for the dispatcher to stop one process and start another running
IN LINUX [
]
System Programming in Linux
26
Scheduling Criteria CPU utilization Advanced Java Programming
keep the CPU as busy as possible
SYSTEM
Throughput
# of processes that complete their execution per time unit
Turnaround time
PROGRAMMING amount of time to execute a particular process
Waiting time amount of time a process has been waiting in the ready queue
IN LINUX
Response time
amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment) | U. K. Roy |
[
]
System Programming in Linux
27
Scheduling Algorithm Goals
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
28
Advanced Java Programming First-Come, First-Served (FCFS) Scheduling
SYSTEM
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:
PROGRAMMING P1
| U. K. Roy |
P2
Waiting 0 time for P1 = 0; P2 = 24;24P3 = 2727 Average waiting time: (0 + 24 + 27)/3 = 17
P3
30
IN LINUX [
]
System Programming in Linux
29
FCFS Scheduling (Cont.)
Advanced Java Programming
SYSTEM
Suppose that the processes arrive in the order P2 , P3 , P1 The Gantt chart for the schedule is:
PROGRAMMING P2
| U. K. Roy |
P3
P1
6 =0 P =3 Waiting0time for3P1 = 6; P 2 ; 3 Average waiting time: (6 + 0 + 3)/3 = 3 Much better than previous case Convoy effect short process behind long process
30
IN LINUX [
]
System Programming in Linux
30
Shortest-Job-First (SJR) Scheduling
Advanced Java Programming
Associate with each process the length of its next CPU burst. Use these lengths to schedule the process with the shortest time
SYSTEM
Two schemes:
PROGRAMMING
nonpreemptive – once CPU given to the process it cannot be preempted until completes its CPU burst preemptive – if a new process arrives with CPU burst length less than remaining time of current executing process, preempt. This scheme is know as the Shortest-Remaining-Time-First (SRTF)
| U. K. Roy |
IN LINUX
SJF is optimal – gives minimum average waiting time for a given set of processes [
]
System Programming in Linux
31
Example of Non-Preemptive SJF
Advanced Java Programming
SYSTEM
Process Arrival Time P1 0.0 P2 2.0 P3 4.0 P4 5.0 SJF (non-preemptive)
Burst Time 7 4 1 4
PROGRAMMING
P1
| U. K. Roy |
P3
P2
P4
IN LINUX
0 3 7 8 12 Average waiting time = (0 + 6 + 3 + 7)/4 = 4
16
[
]
System Programming in Linux
32
Example of Preemptive SJF
Advanced Java Programming
SYSTEM
Process P1 P2 P3 P4 SJF (preemptive)
Arrival Time 0.0 2.0 4.0 5.0
Burst Time 7 4 1 4
PROGRAMMING
P1
| U. K. Roy |
P2
P3
P2
P4
P1
IN LINUX
11 0 2 4 5 7 Average waiting time = (9 + 1 + 0 +2)/4 = 3
16
[
]
System Programming in Linux Determining Length of Next CPU Advanced Java Programming Burst
33
Can only estimate the length Can be done by using the length of previous CPU bursts, using exponential averaging
SYSTEM
1. t n = actual lenght of n th CPU burst
PROGRAMMING 2. τ n +1 = predicted value for the next CPU burst
3. α , 0 ≤ α ≤ 1 4. Define : τ n +1 = α t n + (1 − α )τ n .
IN LINUX | U. K. Roy |
[
]
in Linux Prediction of System the Programming Length of the Next CPU Advanced Java Programming Burst
34
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
35
Examples of Exponential Averaging α =0 Advanced Java Programming
τn+1 = τn
SYSTEM
Recent history does not count
α =1 τn+1 = α tn
PROGRAMMING Only the actual last CPU burst counts
If we expand the formula, we get: τn+1 = α tn+(1 - α)α tn -1 + … +(1 - α )j α tn -j + … +(1 - α )n +1 τ0
IN LINUX
Since both α and (1 - α) are less than or equal to 1, each successive term has less weight than its predecessor | U. K. Roy |
[
]
System Programming in Linux
36
Priority Scheduling
Advanced Java Programming
A priority number (integer) is associated with each process
The CPU is allocated to the process with the highest priority (smallest integer ≡ highest priority)
SYSTEM
Preemptive Nonpreemptive
PROGRAMMING
SJF is a priority scheduling where priority is the predicted next CPU burst time
Problem ≡ Starvation – low priority processes may never execute
Solution ≡ Aging – as time progresses increase the priority of the process
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux
37
Round Robin (RR)
Advanced Java Programming
SYSTEM
Each process gets a small unit of CPU time (time quantum), 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.
Performance
PROGRAMMING IN LINUX
q large ⇒ FIFO
q small ⇒ q must be large with respect to context switch, otherwise overhead is too high
| U. K. Roy |
[
]
System Programming in Linux Example of RR with Time Quantum = Advanced Java Programming 20
38
SYSTEM
Process P1 P2 P3 P4 The Gantt chart is:
Burst Time 53 17 68 24
PROGRAMMING
P1
0
| U. K. Roy |
P2
20
37
P3
P4
57
P1
77
P3
P4
P1
P3
P3
97 117 121 134 154 162
IN LINUX
Typically, higher average turnaround than SJF, but better response
[
]
System Programming in Linux
39
Advanced Java Programming Time Quantum and Context Switch Time
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
40
Advanced Java Programming Turnaround Time Varies With The Time Quantum
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
41
Multilevel Queue Ready queue is partitioned into separate queues: Advanced Java Programming
SYSTEM
foreground (interactive) background
Each queue has its own scheduling algorithm
PROGRAMMING foreground – RR background – FCFS
Scheduling must be done between the queues
IN LINUX
Fixed priority scheduling
• serve all from foreground then from background—Possibility of starvation.
Time slice
• each queue gets a certain amount of CPU time which it can schedule amongst its processes; e.g., 80% to foreground in RR and 20% to background in FCFS | U. K. Roy |
[
]
System Programming in Linux
42
Multilevel Queue Scheduling
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
43
Multilevel Feedback Queue
Advanced Java Programming
SYSTEM
A process can move between the various queues aging can be implemented this way
Multilevel-feedback-queue scheduler defined by the following parameters:
PROGRAMMING
number of queues scheduling algorithms for each queue method used to determine when to upgrade a process method used to determine when to demote a process method used to determine which queue a process will enter when that process needs service
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux Example of Multilevel Feedback Advanced Java Programming Queue
44
Three queues:
SYSTEM
Q0 – RR with time quantum 8 milliseconds Q1 – RR time quantum 16 milliseconds Q2 – FCFS
PROGRAMMING
Scheduling
| U. K. Roy |
A new job enters queue Q0 which is served RR. When it gains CPU, job receives 8 milliseconds. If it does not finish in 8 milliseconds, job is moved to queue Q1.
IN LINUX
At Q1 job is again served RR and receives 16 additional milliseconds. If it still does not complete, it is preempted and moved to queue Q2. [
]
System Programming in Linux
45
Multiple-Processor Scheduling
Advanced Java Programming
CPU scheduling more complex when multiple CPUs are available
Homogeneous processors within a multiprocessor
SYSTEM
Any available processor can be used to run any process
Heterogeneous processors program complied must run on that processor
PROGRAMMING
Load sharing
Use separate queue for each processor
• One could be idle while another was very busy
Use Common ready queue
IN LINUX
• Each processor picks a process—may result inconsistency • Use one processor as scheduler—creates master-slave relationship
Asymmetric multiprocessing
| U. K. Roy |
only one processor accesses the system data structures Others executes user processes
[
]
System Programming in Linux
46
Real-Time Scheduling
Advanced Java Programming
Hard real-time systems required to complete a critical task within a guaranteed amount of time
SYSTEM
Soft real-time systems
requires that critical processes receive priority over less fortunate ones
PROGRAMMING
Schedulable real-time system
Given
m events (processes) process i occurs within period Pi and requires Ci seconds
IN LINUX C ∑ ≤1
Then the load can only be handled if m
i =1
| U. K. Roy |
i
Pi
[
]
System Programming in Linux
47
Algorithm Evaluation
Advanced Java Programming
Criteria used in selecting an algorithm Maximum CPU utilization under the constraint the maximum response time is 1 second
SYSTEM
Maximum throughput such that average turnaround time linearly proportional to execution time
PROGRAMMING
Deterministic Modeling
Evaluates using a predetermined work load
• can not cope with the dynamic behavior of the system
IN LINUX
Queueing Models
Uses mathematical analysis
• Complicated—hence used unrealistic assumtions • Uses some assumptions—that may not occur • An approximation of real system and accuracy is questionable | U. K. Roy |
[
]
PROCESS
SYNCHRONIZATION
System Programming in Linux
49
Process Synchronization
Advanced Java Programming
Background
The Critical-Section Problem
Simple Solutions
Solutions using Synchronization Hardware
Semaphores
SYSTEM
PROGRAMMING Solutions of Classic Problems of Synchronization
IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
50
Background
Cooperating Processes Processes that can affect or be affected by other processes Implementation uses shared logical address space or shared data using files
SYSTEM
Concurrent access to shared data may result in data inconsistency
PROGRAMMING Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes
IN LINUX
Suppose that we wanted to provide a solution to the consumer-producer problem
| U. K. Roy |
[
]
System Programming in Linux
51
Producer-Consumer Problem
Advanced Java Programming
Representative of operating system process
SYSTEM
while (true) { … /* produce an item to nextp */ while (count == BUFFER_SIZE) ; // buffer is full, do nothing buffer [in] = nextp; in = (in + 1) % BUFFER_SIZE; count++; … }
while (true) { … while (count == 0) ; // buffer is empty, do nothing nextc = buffer[out]; out = (out + 1) % BUFFER_SIZE; count--; /* consume the item from nextc … }
PROGRAMMING IN LINUX
Producer process
| U. K. Roy |
Consumer process
[
]
System Programming in Linux Advanced Java Programming
52
Race Condition
count++ could be implemented as register1 = count register1 = register1 + 1 count = register1
SYSTEM
count-- could be implemented as register2 = count register2 = register2 - 1 count = register2
PROGRAMMING Consider this execution interleaving with “count = 5” initially: S0: producer execute register1 = count {register1 = 5} S1: producer execute register1 = register1 + 1 {register1 = 6} S2: consumer execute register2 = count {register2 = 5} S3: consumer execute register2 = register2 - 1 {register2 = 4} S4: producer execute count = register1 {count = 6 } S5: consumer execute count = register2 {count = 4}
IN LINUX
Race condition Outcome depends upon the order of execution
| U. K. Roy |
[
]
System Programming in Linux
53
Solution to Critical-Section Problem
Advanced Java Programming
Critical Section segment of code where shared variables are used
SYSTEM
Solution must satisfy the following criteria
Mutual Exclusion
If process Pi is executing in its critical section, then no other processes can be executing in their critical sections
PROGRAMMING
Progress
If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely
IN LINUX
Bounded Waiting
A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted
Assume that each process executes at a nonzero speed No assumption concerning relative speed of the N processes
| U. K. Roy |
[
]
System Programming in Linux
54
Two process solution
Advanced Java Programming
Solution 1 Assume that the LOAD and STORE instructions are atomic; that is, cannot be interrupted. The two processes share a variable: int turn;
SYSTEM
The variable turn indicates whose turn it is to enter the critical section. while (true) { … while (turn != i) ;
PROGRAMMING
IN LINUX turn = j;
REMAINDER SECTION
}
Structure of process i | U. K. Roy |
[
]
System Programming in Linux
55
Two process solution
Advanced Java Programming
Solution 2 The two processes share a variable:
SYSTEM
Boolean flag[2]
The flag array is used to indicate if a process is ready to enter the critical section. flag[i] = true implies that process Pi is ready!
while (true) { … flag[i]=true; while (flag[j]) ;
PROGRAMMING
IN LINUX flag[i]=false;
REMAINDER SECTION
} Structure of process i | U. K. Roy |
[
]
System Programming in Linux
56
Two process solution
Advanced Java Programming
Solution 3
SYSTEM
while (true) { … flag[i]=true; turn=j while (flag[j] && turn==j) ;
PROGRAMMING
flag[i]=false;
IN LINUX
REMAINDER SECTION }
Structure of process i | U. K. Roy |
[
]
System Programming in Linux
57
Synchronization Hardware
Advanced Java Programming
Many systems provide hardware support for critical section code
SYSTEM
Uniprocessors – could disable interrupts Currently running code would execute without preemption Generally too inefficient on multiprocessor systems
PROGRAMMING • Operating systems using this not broadly scalable
Modern machines provide special atomic hardware instructions • Atomic = non-interruptible
IN LINUX
Either test memory word and set value Or swap contents of two memory words
| U. K. Roy |
[
]
System Programming in Linux
58
TestAndSet Instruction
Advanced Java Programming
Definition:
SYSTEM
bool TestAndSet (bool &target) { bool temp = target; target = true; return temp: }
PROGRAMMING
Solution using TestAndSet
Shared boolean variable lock., initialized to false.
while (true) { while ( TestAndSet (lock )) ; /* do nothing
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
59
Swap Instruction
Advanced Java Programming
Definition:
SYSTEM
void Swap (bool &a, bool &b) { bool temp = a; a = b; b = temp: }
Solution Shared Boolean variable lock initialized to false; Each process has a local Boolean variable key. Solution:
PROGRAMMING while (true) { key = true; while ( key == true) Swap (lock, key ); // critical section lock = false; // remainder section }
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
60
Semaphore
Synchronization tool that does not require busy waiting
Semaphore S – integer variable
Two standard operations modify S: wait() and signal() Originally called P() and V()
Less complicated
Can only be accessed via two indivisible (atomic) operations
SYSTEM
PROGRAMMING wait (S) { while S <= 0 ; // no-op S--; }
IN LINUX
signal (S) { S++; } | U. K. Roy |
[
]
System Programming in Linux
61
Semaphore as General Synchronization Tool
Advanced Java Programming
Counting semaphore – integer value can range over an unrestricted domain
Binary semaphore – integer value can range only between 0 and 1; can be simpler to implement
SYSTEM
Also known as mutex, locks
Can implement a counting semaphore S as a binary semaphore
Provides mutual exclusion
PROGRAMMING Semaphore S; // initialized to 1 wait (S); Critical Section signal (S);
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
62
Solution of other Synchronization Problem
Advanced Java Programming
Two processes P1 and P2 are running concurrently: P1 with a statement S1 and P2 with a statement S2
Requirement:
SYSTEM
S2 be executed only after S1
Solution:
PROGRAMMING Use a a semaphore variable sync initialized to 0
… S1
… wait(sync)
IN LINUX Signal(sync)
S2
…
…
Process P1
| U. K. Roy |
Process P2
[
]
System Programming in Linux
63
Semaphore Implementation
Advanced Java Programming
Must guarantee that no two processes can execute wait () and signal () on the same semaphore at the same time
Thus, implementation becomes the critical section problem where the wait and signal code are placed in the crtical section.
SYSTEM
Could now have busy waiting in critical section implementation • But implementation code is short • Little busy waiting if critical section rarely occupied
PROGRAMMING
Note that applications may spend lots of time in critical sections and therefore this is not a good solution.
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
64
Semaphore Implementation with no Busy waiting
Advanced Java Programming
With each semaphore there is an associated waiting queue. Each entry in a waiting queue has two data items:
SYSTEM
value (of type integer)
a list of processes L waiting on this semaphore
PROGRAMMING Two operations:
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.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
65
Advanced Java Programming Semaphore Implementation with no Busy waiting (Cont.)
Implementation of wait:
SYSTEM
wait (S){ value--; if (value < 0) { add this process to waiting queue block(); } }
PROGRAMMING
Implementation of signal:
IN LINUX
Signal (S){ value++; if (value <= 0) { remove a process P from the waiting queue wakeup(P); } | U. K. Roy}|
[
]
System Programming in Linux
66
Deadlock and Starvation
Advanced Java Programming
Deadlock – two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes
Let S and Q be two semaphores initialized to 1
SYSTEM
P0
P1
PROGRAMMING wait (S); wait (Q); . . . signal (S); signal (Q);
wait (Q); wait (S); . . . signal (Q); signal (S);
IN LINUX
Starvation – indefinite blocking. A process may never be removed from the semaphore queue in which it is suspended.
| U. K. Roy |
[
]
System Programming in Linux
67
Advanced Java Programming Classical Problems of Synchronization
SYSTEM
Bounded-Buffer Problem Readers and Writers Problem Dining-Philosophers Problem
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
68
Bounded-Buffer Problem
Advanced Java Programming
SYSTEM
N buffers, each can hold one item Semaphore mutex initialized to the value 1 Semaphore full initialized to the value 0 Semaphore empty initialized to the value N.
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
69
Bounded Buffer Problem (Cont.)
Advanced Java Programming
The structure of the producer process
The structure of the consumer process
SYSTEM while (true) {
while (true) { //
wait (full); wait (mutex);
produce an item
PROGRAMMING // remove an item from buffer
wait (empty); wait (mutex);
signal (mutex); signal (empty);
// add the item to the buffer
}
| U. K. Roy |
// consume the removed item
IN LINUX
signal (mutex); signal (full);
}
[
]
System Programming in Linux
70
Readers-Writers Problem
Advanced Java Programming
A data set is shared among a number of concurrent processes
SYSTEM
Readers – only read the data set; they do not perform any updates Writers – can both read and write.
Problem – allow multiple readers to read at the same time. Only one writer can access the shared data at the same time.
PROGRAMMING
Shared Data
Data set Semaphore mutex initialized to 1. Semaphore wrt initialized to 1. Integer readcount initialized to 0.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
71
Readers-Writers Problem (Cont.)
Advanced Java Programming
SYSTEM
The structure of a writer process
while (true) { wait (wrt) ;
The structure of a reader process
while (true) { wait (mutex) ; readcount ++ ; if (readercount == 1) wait (wrt) ; signal (mutex)
PROGRAMMING //
writing is performed
// reading is performed
signal (wrt) ;
}
wait (mutex) ; readcount - - ; if (redacount == 0) signal (wrt) ; signal (mutex) ;
IN LINUX }
| U. K. Roy |
[
]
System Programming in Linux
72
Dining-Philosophers Problem
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX
• Shared data
Bowl of rice (data set)
Semaphore chopstick [5] initialized to 1 | U. K. Roy |
[
]
System Programming in Linux
73
Dining-Philosophers Problem (Cont.)
Advanced Java Programming
The structure of Philosopher i:
SYSTEM
While (true) { wait ( chopstick[i] ); wait ( chopStick[ (i + 1) % 5] );
PROGRAMMING // eat
signal (chopstick[ (i + 1) % 5] ); signal ( chopstick[i] );
IN LINUX // think
}
| U. K. Roy |
[
]
System Programming in Linux
74
Dining-Philosophers Problem (Cont.)
Advanced Java Programming
Deadlock free solution Allow at most four philosophers to be sitting simultaneously at the table Allow a philosopher to pick up chopsticks only both are available
SYSTEM
While (true) { wait(mutex) wait ( chopstick[i] ); wait ( chopStick[ (i + 1) % 5] ); signal(mutex) // eat wait (mutex) signal (chopstick[ (i + 1) % 5] ); signal ( chopstick[i] ); signal(mutex) // think }
PROGRAMMING IN LINUX
Asymmetric solution
• Odd philosopher will pick first left then right while even philosopher picks up first left and then right chopstick | U. K. Roy |
[
]
System Programming in Linux
75
Problems with Semaphores
Advanced Java Programming
•
Correct use of semaphore operations: •
SYSTEM
signal (mutex) …. wait (mutex)
• Mutual exclusion requirement is violated •
wait (mutex) … wait (mutex)
PROGRAMMING • Violation of progress condition • Possibility of deadlock
•
Omitting of wait (mutex) or signal (mutex) (or both) • Violation of mutual exclusion or deadlock
IN LINUX
| U. K. Roy |
[
]
DEADLOCKS
System Programming in Linux Advanced Java Programming
77
Deadlocks
SYSTEM
The Deadlock Problem System Model Deadlock Characterization Methods for Handling Deadlocks Deadlock Prevention Deadlock Avoidance Deadlock Detection Recovery from Deadlock
PROGRAMMING
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
78
The Deadlock Problem
Advanced Java Programming
In a multiprogramming Environment several processes compete for finite number of resources
A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set.
SYSTEM
PROGRAMMING
Example 1
System has 2 disk drives. P1 and P2 each hold one disk drive and each needs another one.
Example 2
IN LINUX
semaphores A and B, initialized to 1 P0 wait (A); wait (B);
P1 wait(B) wait(A)
Example 3 Each philosopher picks left chopstick in dining philosopher problem | U. K. Roy |
[
]
System Programming in Linux
79
Bridge Crossing Example
Advanced Java Programming
SYSTEM
Traffic only in one direction.
Each section of a bridge can be viewed as a resource.
If two cars approach each other at the crossing, neither can
PROGRAMMING
start until the other has gone(Dead locks)
If a deadlock occurs, it can be resolved if one car backs up
IN LINUX
(preempt resources and rollback).
Several cars may have to be backed up if a deadlock occurs.
Starvation is possible.
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
80
System Model
Resource types R1, R2, . . ., Rm
SYSTEM
CPU cycles, memory space, I/O devices
Each resource type Ri has Wi instances.
Example—two CPU, Three printers, 2 disk drives
PROGRAMMING
Process may requests as many resources as it requires to perform its designated task Must be less the total number of resources available
Each process utilizes a resource as follows: Request—If the request can not be granted immediately, the requesting process must wait Use Release
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
81
Deadlock Characterization
Advanced Java Programming
Deadlock can arise if four conditions hold simultaneously.
SYSTEM
Mutual exclusion: at least one resource must in non-sharable mode i.e. only one process at a time can use that resource.
Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes.
PROGRAMMING No preemption: a resource can be released only voluntarily by the process holding it, after that process has completed its task. Circular wait: there exists a set {P0, P1, …, Pn} of waiting processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2, …, Pn–1 is waiting for a resource that is held by Pn, and Pn is waiting for a resource that is held by P0.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
82
Resource-Allocation Graph
Advanced Java Programming
Used to visualize resource allocation pattern Helps to describe deadlock more precisely
A set of vertices V and a set of edges (directed) E
V is partitioned into two types:
SYSTEM
PROGRAMMING P = {P1, P2, …, Pn}, the set consisting of all the processes in the system. R = {R1, R2, …, Rm}, the set consisting of all resource types in the system.
IN LINUX
E is partitioned into two types:
request edge – directed edge Pi → Rj
assignment edge – directed edge Rj → Pi | U. K. Roy |
[
]
System Programming in Linux
83
Resource-Allocation Graph (Cont.)
Advanced Java Programming
SYSTEM
Process
Resource Type with 4 instances
PROGRAMMING
| U. K. Roy |
Pi requests an instance of Rj
Pi
Rj
Pi
IN LINUX
Pi is holding an instance of Rj
Rj
[
]
System Programming in Linux
84
Example of a Resource Allocation Graph
Advanced Java Programming
The sets P, R and E
SYSTEM
P = {P1, P2, P3}
R = {R1, R2, R3, R4}
E = {P1 R1, P2 R3, R1 P2 ,
R2 P2, R2 P1, R3 P3}
PROGRAMMING
Resource Instances
One instance of resource type R1
Two instances of resource type R2
IN LINUX
One instance of resource type R3
Three instances of resource type R3
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
85
Basic Facts
SYSTEM
If graph contains no cycles ⇒ no deadlock.
If graph contains a cycle ⇒
if only one instance per resource type, then deadlock.
PROGRAMMING if several instances per resource type, possibility of deadlock.
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
86
Resource Allocation Graph With A Deadlock
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
87
Graph With A Cycle But No Deadlock
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
88
Methods for Handling Deadlocks
Advanced Java Programming
Three methods for dealing with the deadlock problem
SYSTEM
Ensure that the system will never enter a deadlock state. • Deadlock prevention—ensure that one of the necessary conditions can not hold • Deadlock avoidance—systems additional information about resource usage pattern during the execution
PROGRAMMING Allow the system to enter a deadlock state and then recover.
Ignore the problem and pretend that deadlocks never occur in the system; used by most operating systems, including UNIX.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
89
Deadlock Prevention
Advanced Java Programming
• ensure that one of the necessary conditions can not hold
SYSTEM
• Restrain the ways request can be made.
Mutual Exclusion – not required for sharable resources; must hold for nonsharable resources.
Hold and Wait – must guarantee that whenever a process requests a resource, it does not hold any other resources.
Two possibilities
PROGRAMMING Require process to request and be allocated all its resources before it begins execution allow process to request resources only when the process has none.
IN LINUX
• Low resource utilization; possibility of starvation • Data inconsistency
| U. K. Roy |
[
]
System Programming in Linux
90
Deadlock Prevention (Cont.)
Advanced Java Programming
No Preemption – Two possibilities
SYSTEM
If a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released.
PROGRAMMING If a process requests some resources that are not available as they are allocated to other waiting processes, then preempt desired resources from waiting processes
• Preempted resources are added to the list of resources for which the process is waiting. • Process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
91
Deadlock Prevention (Cont.)
Advanced Java Programming
Circular Wait – impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration.
SYSTEM
F(tape drive)=1 F(disk drive)=5 F(printer)=12
PROGRAMMING Facts:I
If a process currently holds resource type Ri , the process can request another resource type Rj if F(Rj) > F(Ri)
OR If a process requests a resource type Rj , if it has released any resource type Ri such the F(Ri) ≥ F(Rj)
IN LINUX
Proof(by contradiction):
Set of deadlocked process {P0, P1, P2, …, Pn}
F(R0) < F(R1) < F(R2) <…< F(Rn) < F(R0) which is impossible | U. K. Roy |
So there can be no circular wait—no deadlock
[
]
System Programming in Linux
92
Deadlock Avoidance
Advanced Java Programming
•
Requires that the system has some additional information available.
•
With this additional information, system can decide whether a newly arrived request can be satisfied (served) or not
SYSTEM
Simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need.
PROGRAMMING
The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
93
Safe State
state is defined by the number of available and allocated resources, and the maximum demands of the processes.
System is in safe state if there exists a sequence
That is:
SYSTEM
PROGRAMMING If Pi needs some resources that are not immediately available, then Pi can wait until all Pj have finished.
When Pj is finished, Pi can obtain needed resources, execute, return allocated resources, and terminate.
IN LINUX
When Pi terminates, Pi +1 can obtain its needed resources, and so on.
When a process requests an available resource, system must decide if immediate allocation leaves the system in a safe state.
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
Basic Facts
If a system is in safe state ⇒ no deadlocks.
If a system is in unsafe state ⇒ possibility of deadlock.
Avoidance ⇒ ensure that a system will never enter an unsafe state.
94
SYSTEM
Example: 12 disk drives Snapshot at time T0: Maximum needs Current Needs P0 10 5 P1 4 2 P2 9 2 The sequence
PROGRAMMING IN LINUX
System Programming in Linux
95
Safe, Unsafe , Deadlock State
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
96
Avoidance algorithms
Advanced Java Programming
SYSTEM
Single instance of a resource type. Use a resource-allocation graph
Multiple instances of a resource type. Use the banker’s algorithm
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
97
Resource-Allocation Graph Scheme
Advanced Java Programming
Claim edge Pi → Rj indicated that process Pj may request resource Rj; represented by a dashed line.
Claim edge converts to request edge when a process requests a resource.
SYSTEM
PROGRAMMING Request edge converted to an assignment edge when the resource is allocated to the process.
When a resource is released by a process, assignment edge reconverts to a claim edge.
Resources must be claimed a priori in the system.
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux
98
Resource-Allocation Graph
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
99
Resource-Allocation Graph Algorithm
Advanced Java Programming
SYSTEM
Suppose that process Pi requests a resource Rj
The request can be granted only if converting the request edge to an assignment edge does not result in the formation of a cycle (including the claim edge )in the resource allocation graph
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
100
Unsafe State In Resource-Allocation Graph
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
101
Banker’s Algorithm
Advanced Java Programming
SYSTEM
Multiple instances.
Each process must a priori claim maximum use.
PROGRAMMING
When a process requests a resource it may have to wait.
When a process gets all its resources it must return them in a finite amount of time.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
102
Data Structures for the Banker’s Algorithm
Advanced Java Programming
Let n = number of processes, and m = number of resources types.
SYSTEM
Available: Vector of length m. If Available [j] = k, there are k instances of resource type Rj available.
Max: n x m matrix. If Max [i,j] = k, then process Pi may request at most k instances of resource type Rj.
PROGRAMMING Allocation: n x m matrix. If Allocation[i,j] = k then Pi is currently allocated k instances of Rj.
Need: n x m matrix. If Need[i,j] = k, then Pi may need k more instances of Rj to complete its task.
IN LINUX
Need [i,j] = Max[i,j] – Allocation [i,j].
Define X≤Y if X[i] ≤ Y[i] ∀ i
| U. K. Roy |
[
]
System Programming in Linux
103
Safety Algorithm
Advanced Java Programming
1. Let Work and Finish be vectors of length m and n, respectively. Initialize:
SYSTEM
Work = Available Finish [i] = false for i = 0, 1, …, n- 1.
2. Find and i such that both: (a) Finish [i] = false (b) Needi ≤ Work
PROGRAMMING If no such i exists, go to step 4.
Work = Work + Allocationi Finish[i] = true go to step 2.
IN LINUX
4. If Finish [i] == true for all i, then the system is in a safe state. Algorithm requires an order of O(m x n2) operations to detect whether the system is in safe state. | U. K. Roy |
[
]
System Programming in Linux
104
Resource-Request Algorithm for Process Pi
Advanced Java Programming
Requesti = request vector for process Pi. If Requesti [j] = k then process Pi wants k instances of resource type Rj.
SYSTEM
If Requesti ≤ Needi go to step 2. Otherwise, raise error condition, since process has exceeded its maximum claim.
PROGRAMMING
If Requesti ≤ Available, go to step 3. Otherwise Pi must wait, since resources are not available.
3. Pretend to allocate requested resources to Pi by modifying the state as follows: Available = Available – Request; Allocationi = Allocationi + Requesti; Needi = Needi – Requesti;
IN LINUX
If safe ⇒ the resources are allocated to Pi. ● If unsafe ⇒ Pi must wait, and the old resource-allocation state is restored ●
| U. K. Roy |
[
]
System Programming in Linux
105
Example of Banker’s Algorithm
Advanced Java Programming
5 processes P0 through P4; 3 resource types: Available A (10 instances), B (5instances), and C (7 instances).
SYSTEM
PROGRAMMING
Snapshot at time T0: Allocation Max Available ABC ABC ABC P0 0 1 0 753 332 P1 2 0 0 322 P2 3 0 2 902 P3 2 1 1 222 P4 0 0 2 4 3 3
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
106
Example (Cont.)
Advanced Java Programming
The content of the matrix Need is defined to be Max – Allocation.
SYSTEM Need ABC 743 122 600 011 431
PROGRAMMING P0 P1 P2 P3 P4
| U. K. Roy |
IN LINUX
The system is in a safe state since the sequence < P1, P3, P4, P2, P0> satisfies safety criteria. [
]
System Programming in Linux
107
Example: P1 Request (1,0,2)
Advanced Java Programming
Check that Request ≤ Available (that is, (1,0,2) ≤ (3,3,2) ⇒ true. Allocation Need Available ABC ABC ABC P0 0 1 0 743 230 P1 3 0 2 020 P2 3 0 1 600 P3 2 1 1 011 P4 0 0 2 431 Executing safety algorithm shows that sequence < P1, P3, P4, P0, P2> satisfies safety requirement. Can request for (3,3,0) by P4 be granted? Can request for (0,2,0) by P0 be granted?
SYSTEM
PROGRAMMING | U. K. Roy |
IN LINUX
[
]
System Programming in Linux
108
Deadlock Detection
Advanced Java Programming
Allow system to enter deadlock state
System must provide
SYSTEM
Detection algorithm • Checks the state of the system to determine whether a deadlock has occured
PROGRAMMING Recovery scheme
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
109
Single Instance of Each Resource Type
Advanced Java Programming
SYSTEM
Maintain wait-for graph Nodes are processes.
Pi → Pj if Pi is waiting for Pj.
PROGRAMMING
Periodically invoke an algorithm that searches for a cycle in the graph. If there is a cycle, there exists a deadlock.
An algorithm to detect a cycle in a graph requires an order of n2 operations, where n is the number of vertices in the graph.
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux
110
Resource-Allocation Graph and Wait-for Graph
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX
ResourceAllocation Graph
| U. K. Roy |
Corresponding waitfor graph
[
]
System Programming in Linux
111
Several Instances of a Resource Type
Advanced Java Programming
SYSTEM
Available: A vector of length m indicates the number of available resources of each type.
Allocation: An n x m matrix defines the number of resources of each type currently allocated to each process.
PROGRAMMING
Request: An n x m matrix indicates the current request of each process. If Request [ij] = k, then process Pi is requesting k more instances of resource type. Rj.
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
112
Detection Algorithm
Advanced Java Programming
1. Let Work and Finish be vectors of length m and n, respectively Initialize: (a) Work = Available For i = 1,2, …, n, if Allocationi ≠ 0, then Finish[i] = false;otherwise, Finish[i] = true.
SYSTEM
2. Find an index i such that both: (a) Finish[i] == false (b) Requesti ≤ Work
PROGRAMMING If no such i exists, go to step 4.
3. Work = Work + Allocationi Finish[i] = true go to step 2.
IN LINUX
4. If Finish[i] == false, for some i, 1 ≤ i ≤ n, then the system is in deadlock state. Moreover, if Finish[i] == false, then Pi is deadlocked. Algorithm requires an order of O(m x n2) operations to detect whether the system is in deadlocked state. | U. K. Roy |
[
]
System Programming in Linux
113
Example of Detection Algorithm
Advanced Java Programming
Five processes P0 through P4; three resource types A (7 instances), B (2 instances), and C (6 instances).
SYSTEM
Snapshot at time T0: Allocation Request ABC ABC P0 010 000 P1 200 202 P2 303 000 P3 211 100 P4 002 002
Available ABC 000
PROGRAMMING
IN LINUX
Sequence
| U. K. Roy |
[
]
System Programming in Linux
114
Example (Cont.)
Advanced Java Programming
P2 requests an additional instance of type C. Request ABC P0 0 0 0 P1 2 0 1 P2 0 0 1 P3 1 0 0 P4 0 0 2 State of system?
SYSTEM
PROGRAMMING
IN LINUX
Can reclaim resources held by process P0, but insufficient resources to fulfill other processes; requests. Deadlock exists, consisting of processes P1, P2, P3, and P4. | U. K. Roy |
[
]
System Programming in Linux
115
Detection-Algorithm Usage
Advanced Java Programming
When, and how often, to invoke depends on:
SYSTEM
How often a deadlock is likely to occur?
How many processes will need to be rolled back? • one for each disjoint cycle
Run deadlock detection detection algorithm every time a request can not be granted
PROGRAMMING Considerably overhead
Run once per hour Run when CPU/resource utilization drops below 40% If detection algorithm is invoked arbitrarily, there may be many cycles in the resource graph and so we would not be able to tell which of the many deadlocked processes “caused” the deadlock.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
116
Recovery from Deadlock: Process Termination
Advanced Java Programming
Abort all deadlocked processes.
Abort one process at a time until the deadlock cycle is eliminated.
In which order should we choose to abort?
SYSTEM
PROGRAMMING Priority of the process. How long process has computed, and how much longer to completion. Resources the process has used. Resources process needs to complete. How many processes will need to be terminated. Is process interactive or batch?
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
117
Recovery from Deadlock: Resource Preemption
Advanced Java Programming
SYSTEM
Selecting a victim – minimize cost.
Rollback – return to some safe state, restart process for that state.
PROGRAMMING Starvation – same process may always be picked as victim, include number of rollback in cost factor.
IN LINUX | U. K. Roy |
[
]
Memory Management
System Programming in Linux
119
Memory Management
Advanced Java Programming
SYSTEM
Background Swapping Contiguous Memory Allocation Paging Structure of the Page Table Segmentation Example: The Intel Pentium
PROGRAMMING
IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
120
Objectives
SYSTEM
To provide a detailed description of various ways of organizing memory hardware To discuss various memory-management techniques, including paging and segmentation To provide a detailed description of the Intel Pentium, which supports both pure segmentation and segmentation with paging
PROGRAMMING
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
121
Background
Advanced Java Programming
SYSTEM
Program must be brought (from disk) into memory and placed within a process for it to be run Main memory and registers are only storage CPU can access directly Register access in one CPU clock (or less) Main memory can take many cycles Cache sits between main memory and CPU registers Protection of memory required to ensure correct operation
PROGRAMMING
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux
122
Base and Limit Registers
Advanced Java Programming
SYSTEM
A pair of base and limit registers define the logical address space
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
123
Binding of Instructions and Data to Memory
Advanced Java Programming
SYSTEM
Address binding of instructions and data to memory addresses can happen at three different stages Compile time: If memory location known a priori, absolute code can be generated; must recompile code if starting location changes Load time: Must generate relocatable code if memory location is not known at compile time Execution time: Binding delayed until run time if the process can be moved during its execution from one memory segment to another. Need hardware support for address maps (e.g., base and limit registers)
PROGRAMMING IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
124
Multistep Processing of a User Program
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
125
Logical vs. Physical Address Space
Advanced Java Programming
SYSTEM
The concept of a logical address space that is bound to a separate physical address space is central to proper memory management Logical address – generated by the CPU; also referred to as virtual address Physical address – address seen by the memory unit
PROGRAMMING
Logical and physical addresses are the same in compile-time and load-time addressbinding schemes; logical (virtual) and physical addresses differ in execution-time address-binding scheme
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
126
Memory-Management Unit (MMU)
Advanced Java Programming
SYSTEM
Hardware device that maps virtual to physical address
In MMU scheme, the value in the relocation register is added to every address generated by a user process at the time it is sent to memory
PROGRAMMING
The user program deals with logical addresses; it never sees the real physical addresses
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
127
Dynamic relocation using a relocation register
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
128
Dynamic Loading
Advanced Java Programming
SYSTEM
Routine is not loaded until it is called Better memory-space utilization; unused routine is never loaded Useful when large amounts of code are needed to handle infrequently occurring cases No special support from the operating system is required implemented through program design
PROGRAMMING
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
129
Dynamic Linking
Advanced Java Programming
SYSTEM
Linking postponed until execution time Small piece of code, stub, used to locate the appropriate memory-resident library routine Stub replaces itself with the address of the routine, and executes the routine Operating system needed to check if routine is in processes’ memory address Dynamic linking is particularly useful for libraries System also known as shared libraries
PROGRAMMING
| U. K. Roy |
IN LINUX [
]
System Programming in Linux Advanced Java Programming
130
Swapping
SYSTEM
A process can be swapped temporarily out of memory to a backing store, and then brought back into memory for continued execution
Backing store – fast disk large enough to accommodate copies of all memory images for all users; must provide direct access to these memory images
PROGRAMMING
Roll out, roll in – swapping variant used for prioritybased scheduling algorithms; lower-priority process is swapped out so higher-priority process can be loaded and executed
Major part of swap time is transfer time; total transfer time is directly proportional to the amount of memory swapped
Modified versions of swapping are found on many systems (i.e., UNIX, Linux, and Windows) System maintains a ready queue of ready-to-run processes which have memory images on disk
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux
131
Schematic View of Swapping
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
132
Contiguous Allocation
Advanced Java Programming
SYSTEM
Main memory usually into two partitions:
Resident operating system, usually held in low memory with interrupt vector User processes then held in high memory
Relocation registers used to protect user processes from each other, and from changing operating-system code and data
PROGRAMMING Base register contains value of smallest physical address Limit register contains range of logical addresses – each logical address must be less than the limit register MMU maps logical address dynamically
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
133
HW address protection with base and limit registers
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
134
Contiguous Allocation (Cont.)
Advanced Java Programming
SYSTEM
Multiple-partition allocation
Hole – block of available memory; holes of various size are scattered throughout memory When a process arrives, it is allocated memory from a hole large enough to accommodate it Operating system maintains information about: a) allocated partitions b) free partitions (hole)
PROGRAMMING OS
OS
OS
OS
process 5
process 5
process 5
process 5
process 9
process 9
process 8 process 2
| U. K. Roy |
IN LINUX
process 10
process 2
process 2
process 2
[
]
System Programming in Linux
135
Advanced Java Programming Dynamic Storage-Allocation Problem
SYSTEM
How to satisfy a request of size n from a list of free holes
First-fit: Allocate the first hole that is big enough Best-fit: Allocate the smallest hole that is big enough; must search entire list, unless ordered by size
PROGRAMMING Produces the smallest leftover hole
Worst-fit: Allocate the largest hole; must also search entire list Produces the largest leftover hole
Firstfit and bestfit better than worstfit in terms of speed and storage utilization
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
136
Fragmentation
Advanced Java Programming
SYSTEM
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 Reduce external fragmentation by compaction
PROGRAMMING
Shuffle memory contents to place all free memory together in one large block Compaction is possible only if relocation is dynamic, and is done at execution time I/O problem
IN LINUX
• Latch job in memory while it is involved in I/O • Do I/O only into OS buffers
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
137
Paging
SYSTEM
Logical address space of a process can be noncontiguous; process is allocated physical memory whenever the latter is available Divide physical memory into fixed-sized blocks called frames (size is power of 2, between 512 bytes and 8,192 bytes) Divide logical memory into blocks of same size called pages Keep track of all free frames To run a program of size n pages, need to find n free frames and load program Set up a page table to translate logical to physical addresses Internal fragmentation
PROGRAMMING
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux
138
Address Translation Scheme
Advanced Java Programming
SYSTEM
Address generated by CPU is divided into:
Page number (p) – used as an index into a page table which contains base address of each page in physical memory
PROGRAMMING Page offset (d) – combined with base address to definepage number the physical memory address that is page offset sent to the memory unit p d m n
n
IN LINUX
For given logical address space 2m and page size 2n | U. K. Roy |
[
]
System Programming in Linux
139
Paging Hardware
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
140
Advanced Java Programming Paging Model of Logical and Physical Memory
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
141
Paging Example
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX 32byte memory and 4byte pages | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
142
Free Frames
SYSTEM PROGRAMMING IN LINUX Before allocation | U. K. Roy |
After allocation [
]
System Programming in Linux
143
Implementation of Page Table
Advanced Java Programming
SYSTEM
Page table is kept in main memory Page-table base register (PTBR) points to the page table Page-table length register (PRLR) indicates size of the page table In this scheme every data/instruction access requires two memory accesses. One for the page table and one for the data/instruction. The two memory access problem can be solved by the use of a special fast-lookup hardware cache called associative memory or translation look-aside buffers (TLBs) Some TLBs store address-space identifiers (ASIDs) in each TLB entry – uniquely identifies each process to provide address-space protection for that process
PROGRAMMING
| U. K. Roy |
IN LINUX [
]
System Programming in Linux
144
Associative Memory
Advanced Java Programming
SYSTEM
Associative memory – parallel search Page #
Frame #
PROGRAMMING Address translation (p, d)
If p is in associative register, get frame # out Otherwise get frame # from page table in memory
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
145
Paging Hardware With TLB
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
146
Effective Access Time
Advanced Java Programming
SYSTEM
Associative Lookup = ε time unit Assume memory cycle time is 1 microsecond Hit ratio – percentage of times that a page number is found in the associative registers; ratio related to number of associative registers Hit ratio = α Effective Access Time (EAT) EAT = (1 + ε) α + (2 + ε)(1 – α) =2+ε–α
PROGRAMMING
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
147
Memory Protection
Advanced Java Programming
SYSTEM
Memory protection implemented by associating protection bit with each frame
Valid-invalid bit attached to each entry in the page table:
PROGRAMMING “valid” indicates that the associated page is in the process’ logical address space, and is thus a legal page “invalid” indicates that the page is not in the process’ logical address space
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux Valid (v) or Invalid (i) Bit In A Page Advanced Java Programming Table
148
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
149
Shared Pages
SYSTEM
Shared code
One copy of read-only (reentrant) code shared among processes (i.e., text editors, compilers, window systems). Shared code must appear in same location in the logical address space of all processes
PROGRAMMING
Private code and data
Each process keeps a separate copy of the code and data
IN LINUX
The pages for the private code and data can appear anywhere in the logical address space
| U. K. Roy |
[
]
System Programming in Linux
150
Shared Pages Example
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
151
Structure of the Page Table
Advanced Java Programming
SYSTEM
Hierarchical Paging
Hashed Page Tables
PROGRAMMING
Inverted Page Tables
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
152
Hierarchical Page Tables
Advanced Java Programming
SYSTEM
Break up the logical address space into multiple page tables
A simple technique is a two-level page table
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
153
Two-Level Page-Table Scheme
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
154
Two-Level Paging Example
Advanced Java Programming
SYSTEM
A logical address (on 32-bit machine with 1K page size) is divided into: a page number consisting of 22 bits a page offset consisting of 10 bits
PROGRAMMING
Since the page table is paged, the page number is further divided into: a 12-bit page number page number a 10-bit page offset p2 pi
d Thus, a logical address is as follows:
IN LINUX 12
| U. K. Roy |
page offset
10
10
[
]
System Programming in Linux
155
Address-Translation Scheme
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
156
Three-level Paging Scheme
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
157
Hashed Page Tables
Advanced Java Programming
SYSTEM
Common in address spaces > 32 bits
The virtual page number is hashed into a page table. This page table contains a chain of elements hashing to the same location.
PROGRAMMING
Virtual page numbers are compared in this chain searching for a match. If a match is found, the corresponding physical frame is extracted.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
158
Hashed Page Table
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
159
Inverted Page Table
Advanced Java Programming
SYSTEM
One entry for each real page of memory Entry consists of the virtual address of the page stored in that real memory location, with information about the process that owns that page Decreases memory needed to store each page table, but increases time needed to search the table when a page reference occurs Use hash table to limit the search to one — or at most a few — page-table entries
PROGRAMMING
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux
160
Inverted Page Table Architecture
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
161
Segmentation
SYSTEM
Memory-management scheme that supports user view of memory A program is a collection of segments. A segment is a logical unit such as: main program, procedure, function, method, object, local variables, global variables, common block, stack, symbol table, arrays
PROGRAMMING IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
162
User’s View of a Program
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
163
Logical View of Segmentation
Advanced Java Programming
1
1
SYSTEM 4
2
PROGRAMMING 3
4
2 3
IN LINUX
user space
| U. K. Roy |
physical memory space
[
]
System Programming in Linux
164
Segmentation Architecture
Advanced Java Programming
SYSTEM
Logical address consists of a two tuple: <segment-number, offset>, Segment table – maps two-dimensional physical addresses; each table entry has:
base – contains the starting physical address where the segments reside in memory limit – specifies the length of the segment
PROGRAMMING
Segment-table base register (STBR) points to the segment table’s location in memory Segment-table length register (STLR) indicates number of segments used by a program; segment number s is legal if s < STLR
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
165
Segmentation Architecture (Cont.)
Advanced Java Programming
Protection
SYSTEM
With each entry in segment table associate: • validation bit = 0 ⇒ illegal segment • read/write/execute privileges
Protection bits associated with segments; code sharing occurs at segment level Since segments vary in length, memory allocation is a dynamic storage-allocation problem A segmentation example is shown in the following diagram
PROGRAMMING
| U. K. Roy |
IN LINUX [
]
System Programming in Linux
166
Segmentation Hardware
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
167
Example of Segmentation
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
168
Example: The Intel Pentium
Advanced Java Programming
SYSTEM
Supports both segmentation and segmentation with paging CPU generates logical address Given to segmentation unit
PROGRAMMING • Which produces linear addresses
Linear address given to paging unit
• Which generates physical address in main memory • Paging units form equivalent of MMU
IN LINUX | U. K. Roy |
[
]
System Programming in Linux Logical to Physical Address Translation in Advanced Java Programming Pentium
169
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
170
Intel Pentium Segmentation
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
171
Pentium Paging Architecture
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
172
Linear Address in Linux
Advanced Java Programming
SYSTEM
Broken into four parts:
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
173
Three-level Paging in Linux
Advanced Java Programming
SYSTEM PROGRAMMING IN LINUX | U. K. Roy |
[
]
LINUX COMMANDS
System Programming in Linux Advanced Java Programming
175
Objectives
SYSTEM
In this session, you will learn to: Use the basic Unix commands like pwd date
PROGRAMMING who ls
man
Use “man” pages
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
176
Simple commands
Advanced Java Programming
pwd
SYSTEM
Displays the current working directory.
date
PROGRAMMING Displays the current date and time
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
177
Simple commands
Advanced Java Programming
who
SYSTEM
Displays the names of all the users who have currently logged in
PROGRAMMING
who am i
Displays the name of the current user.
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
178
Listing contents of directory
Advanced Java Programming
• • •
ls Syntax options:
• •
PROGRAMMING column
•
SYSTEM
:ls [options] [file….] -l list in long format -a list all file including those beginning with a dot -i list inode no of file in first
file
•
directories • •
| U. K. Roy |
-s
reports disk blocks occupied by
-R
recursively list all sub
IN LINUX -F -C
mark type of each file display files in columns
[
]
System Programming in Linux
179
Meta characters
Advanced Java Programming
Meta Characters * ? […]
Purpose
SYSTEM Example
Match with one or more characters or none Match with any single character Match with any single character within the brackets ; Command separator | Pipe two commands () Group commands Useful when the output of thecommand group has to be redirected `command` Execute the command enclosed within back quotes. Useful when the output of a command into a variable in a shell script
$ ls –l *.c file* $ ls –l file? $ ls –l file[abc]
$ cat file1; cat file2 $ cat abc | wc $ (echo “==== x.c ====”; cat x.c) > out
PROGRAMMING
‘string’ “string”
| U. K. Roy |
count=`expr $count + 1`
assuming count has value3, this increments the value of count echo ‘expr $count + 1’ displays expr $count + 1 echo “expr $count + 1” displays expr 3 + 1 assuming the variable count has value 3
IN LINUX
Quote all characters with no substitution (ex. no special meaning for $) Quote all characters with substitution. The characters $, \ (back slash) and back quote have special meaning.
[
]
System Programming in Linux
180
Listing contents of directory
Advanced Java Programming
$ ls –l
SYSTEM
total 6 -rwxr-xr-x drwxr-xr-x -rw-r--r--rw-------rw-r--r--
1 2 1 1 1
user1 user2 user1 user1 user3
projA projD projA projA projC
12373 4096 12831 61440 255
Dec Dec Dec Dec Dec
15 22 12 15 20
14:45 14:00 13:59 11:16 14:29
a.out awkpro c core cs
PROGRAMMING File access permissions
File type
User id
Link count
Group id
File size in bytes
Date & time of modification
File name
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
181
Getting help on commands
Advanced Java Programming
•
The Unix manual, usually called man pages, is available on-line to explain the usage of the Unix system and commands.
•
Syntax: man [options] command_name
•
SYSTEM
PROGRAMMING Common Options -k keyword list command synopsis line for all keyword matches -M path path to man pages -a show all matching man pages (SVR4)
• •
IN LINUX
info command_name - help for the internal commands help -–command_name– gives command synatx
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
•
•
182
Summary
SYSTEM
In this session, you have learned to … use the basic Unix commands like • pwd • date • who • ls • man use “man” pages
PROGRAMMING IN LINUX
| U. K. Roy |
[
]
FILES AND
DIRECTORIES
System Programming in Linux Advanced Java Programming
184
Objectives
SYSTEM
In this session, you will learn to:
set file permissions using the chmod command use directory-related commands namely mkdir, rmdir, cd commands
PROGRAMMING use file-related commands namely cp, mv, rm commands
access advanced file permissions using commands umask, suid, sgid, linking files, stickybit create and edit files using the vi editor
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
185
File access permissions
Advanced Java Programming
Refers to the permissions associated with a file with respect to the following
Permission Levels
SYSTEM
User (owner) (u)
PROGRAMMING Group (wheel, staff, daemon, etc.) (g)
World (guest, anonymous and all other users) (o)
Permission Settings Read (r)
IN LINUX
Write (w)
Execute (x)
| U. K. Roy |
[
]
System Programming in Linux
186
File access permissions
Advanced Java Programming
No read permission does not allow the user to:
SYSTEM
List the contents of directory Remove the directory
No Write permission does not allow the user to : copy files to the directory
PROGRAMMING remove files from the directory rename files in the directory make a subdirectory
remove a subdirectory from the directory
IN LINUX
move files to, and from the directory
| U. K. Roy |
[
]
System Programming in Linux
187
File access permissions
Advanced Java Programming
SYSTEM
No execute permission does not allow the user to: display the contents of a directory file from within the directory
PROGRAMMING change to the directory
display a file in the directory
IN LINUX
copy a file to, or from the directory
| U. K. Roy |
[
]
System Programming in Linux
188
Changing permissions - chmod
Advanced Java Programming
chmod u+x file_name Syntax: chmod
SYSTEM
PROGRAMMING Octal 4 2 3
Number - for read - for write - for execution
IN LINUX
$ chmod 744 xyz this will set rwx for user, r– for group, r—for others
| U. K. Roy |
[
]
System Programming in Linux
189
Directory creation
Advanced Java Programming
Command Syntax mkdir [OPTION] DIRECTORY $mkdir <path>/
SYSTEM
PROGRAMMING
Example:
mkdir project1
IN LINUX
This creates a directory project1 under current directory
Note: Write and execute permissions are needed for the user to create a directory
| U. K. Roy |
[
]
System Programming in Linux
190
Directory removal
Advanced Java Programming
rmdir command removes directory Syntax
SYSTEM
rmdir
Example Removes project1 directory in the current directory
rmdir project1
PROGRAMMING
| U. K. Roy |
Remove multiple directories rmdir pos1 pos2 Remove the directory recursively rmdir –p dir1/dir2/dir2 Rule: rmdir can be executed to remove a directory if it is empty and not the current directory
IN LINUX
[
]
System Programming in Linux
191
Command - cd
Advanced Java Programming
SYSTEM
cd command is used to change the directory
PROGRAMMING cd cd .. cd /
- take to the home directory - takes to the parent directory - takes to the root directory
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
192
File related commands
Advanced Java Programming
File
SYSTEM
Operation
Copying
a file
Command cp
mv
PROGRAMMING
Moving
a file
Removing
Displaying
a file
cat
IN LINUX
a file and concatenating files
| U. K. Roy |
rm
[
]
System Programming in Linux
193
Command - cp
Advanced Java Programming
SYSTEM
Used to copy files across directories Syntax cp <source file>
PROGRAMMING
Example cp file1 file2
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
194
Command - cp
Advanced Java Programming
-p
SYSTEM
Copies the file and preserves the following attributes • • • •
owner id group id permissions last modification time
PROGRAMMING -r
recursive copy; copy subdirectories under the directory if any
-i
IN LINUX
interactive; prompts for confirmation before overwriting the target file, if it already exists
| U. K. Roy |
[
]
System Programming in Linux
195
Command - mv
Advanced Java Programming
SYSTEM
Used to move a file, or rename a file
Preserves the following details • • • •
owner id group id permissions Last modification time
PROGRAMMING
-f
suppresses all prompting (forces overwriting of target)
-i
prompts before overwriting destination file
| U. K. Roy |
IN LINUX [
]
System Programming in Linux
196
Command – rm
Advanced Java Programming
Used to remove a file •
SYSTEM
Syntax : rm file(s)
-f
suppresses all prompting
-i
prompts before overwriting destination file
-r will recursively remove the file from a directory (can be used to delete a directory along with the content )
Caution: Use “i” option along with “r” to get notified on deletion
PROGRAMMING
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux
197
Command – chown & chgrp
Advanced Java Programming
$ ls –l -rwxr-xr-x -rwxr-xr-x
$chown user2 a.out
$ls –l -rwxr-xr-x -rwxr-xr-x
1user1 training 3 user1 faculty
12373 Dec 15 14:45 a.out 4096 Dec 24 11:56 awkpro
SYSTEM
1user2 3 user1
training faculty
12373 Dec 15 14:45 a.out 4096 Dec 24 11:56 awkpro
PROGRAMMING $ chgrp training awkpro $ls –l -rwxr-xr-x -rwxr-xr-x
| U. K. Roy |
1user2 3 user1
training training
12373 Dec 15 14:45 a.out 4096 Dec 24 11:56 awkpro
IN LINUX
[
]
System Programming in Linux
198
Command - umask
Advanced Java Programming
umask value is used to set the default permission of a file and directory while creating
umask command is used to see the default mask for the file permission
Default umask value will be set in the system environment file like /etc/profile
umask 022 will set a mask of 022 for the current session
SYSTEM
PROGRAMMING The file permission after setting this umask value will be 644 And the directory permission will be 755
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
199
Command - ln
Advanced Java Programming
Linking files
Hard Link (in the same filesystem)
SYSTEM
$ ln /usr/bin/clear /usr/bin/cls
PROGRAMMING Hard link uses the same inode number
Soft Link (in different filesystems also used to link directories)
IN LINUX
$ ln –s /usr/bin/clear /home/user1/cls
| U. K. Roy |
[
]
System Programming in Linux
200
Special permission bits
Advanced Java Programming
Set user ID (SUID)
SYSTEM
This means that if the SUID bit is set for any application then your user ID would be set as that of the owner of application/file rather than the current user, while running that application
PROGRAMMING “set user ID” bit can be set in one of the two ways: • chmod u+s
• chmod 4755
IN LINUX
• The leftmost octal number 4 indicates “set user ID” bit to be set, other octal digits indicate regular file permissions. This is meaningful for executable files only.
| U. K. Roy |
[
]
System Programming in Linux
201
Special permission bits
Advanced Java Programming
Set group id (SGID)
SYSTEM
Just like SUID, setting the SGID bit for a file sets your group ID to the file's group while the file is executing “set group ID” bit can be set in one of the two ways:
PROGRAMMING • chmod g+s
• chmod 2755
• The leftmost octal number 2 indicates “set group ID” bit to be set, other octal digits indicate regular file permissions. This is meaningful for executable files only.
IN LINUX
Click to edit Master text styles | U. K. Roy |
Second level • Third level
[
]
System Programming in Linux
202
Special permission bits
Advanced Java Programming
Sticky bit (SVTX)
SYSTEM
Typically set to a directory that is shareable
Any user can create a file in such sharable directory Only owner of the file or super user (root) can remove a file from the directory
PROGRAMMING “sticky” bit can be set in one of the two ways: • chmod +t
• chmod 1555
IN LINUX
• The leftmost octal number 1 indicates “sticky” bit to be set, other octal digits indicate regular file permissions.
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
203
vi editor
vi is a visual editor used to create and edit text files.
SYSTEM
A screen-oriented text editor
Included with most UNIX system distributions Command driven
PROGRAMMING
Categories of commands include Cursor movement
Editing commands
Search and replace commands
IN LINUX
The vi editor is invoked by the following command: vi
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
Ba ckspa ce
the
q uick
the 2 the b
q uick
SYSTEM
brown w
w
Spa ce
fox
k
l
the
q uick
w
brown
fox
brown
fox
$
the
q uick
brown
fox
^
w q uick
Navigation
j
h
204
brown b
fox b
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
205
Editing commands
Advanced Java Programming
Text insertion / replacement
SYSTEM
i
- inserts text to the left of the cursor
a
- inserts text to the right of the cursor
I
- inserts text at the beginning of the line
PROGRAMMING A
- appends text at end of the line
o
- opens line below
O
- opens line above
R
- replaces text from cursor to right
s
- replaces a single character with any number of
IN LINUX characters
S
| U. K. Roy |
- replaces entire line
[
]
System Programming in Linux
206
Editing commands
Advanced Java Programming
Deletion
SYSTEM
x
- to delete character at cursor position
3x
- to delete 3 characters at cursor position
dw
- to delete word
2dw
- to delete 2 word
dd
- to delete a line
2dd
- to delete 2 lines
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
207
Editing commands
Advanced Java Programming
Yanking Y- copy 3Y p P
SYSTEM
line into buffer - copy 3 lines into buffer - copy buffer below cursor - copy buffer above cursor
PROGRAMMING
Save and quit :w :w! :x :q :q!
| U. K. Roy |
-
to save to name a file (:w! filename -> save as) save and quit cancel changes cancel and quit
IN LINUX
[
]
System Programming in Linux
208
Search & replace commands
Advanced Java Programming
The following commands are applicable for vi editor in Linux
/pat cursor
SYSTEM
searches for the pattern pat and places where pattern occurs.
PROGRAMMING
/
repeat last search
:%s/old/new/g file.
to change every occurrence in the whole
IN LINUX
:#,#s/old/new/g numbers of
| U. K. Roy |
where #,# are replaced with the the two lines.
[
]
System Programming in Linux Advanced Java Programming
209
Summary
SYSTEM
In this session, you have learned how to … use file permissions using the chmod command use directory-related commands namely mkdir, rmdir, cd commands use file-related commands namely cp, mv, rm commands access advanced file permissions using commands umask, suid, sgid, linking the files, stickybit create and edit files using the vi editor
PROGRAMMING IN LINUX
| U. K. Roy |
[
]
Chapter 4 UNIX
Utilities
System Programming in Linux Advanced Java Programming
211
Objectives
In this session, you will learn to:
SYSTEM
use the Unix Utilities like
• cat, echo, touch, more, file, wc, cmp, comm, find
employ redirection operators use filters like
PROGRAMMING • sort, grep, cut, head, tail, tr, and paste
use communication commands • telnet, ftp
use backup commands
IN LINUX
• zip/gzip and tar
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
212
cat
•
cat command takes the input from the keyboard, and sends the output to the monitor
•
We can redirect the input and output using the redirection operators
SYSTEM
PROGRAMMING $ cat>file1 Type the content here press
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
touch
SYSTEM
touch is used to change the time stamp of the file
Syntax: touch [options] file Options:
213
PROGRAMMING a to change the access time m to change the modification time c no create if not exists
touch
If the file does not exist, it will create a file of zero byte size.
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux Advanced Java Programming
214
echo & read
echo command is used to print output to the screen echo “This is an example” This is an example
SYSTEM
PROGRAMMING x=10 echo $x 10
IN LINUX
read command allows to read input from user and assign it to the variable specified. read x
| U. K. Roy |
[
]
System Programming in Linux
215
General purpose utilities
Advanced Java Programming
more
SYSTEM
Allows user to view one page-full of information at a time.
file
Used to display the type of the file
PROGRAMMING tty
Prints the terminal’s name
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
216
General purpose utilities
Advanced Java Programming
wc
SYSTEM
A filter used to count the number of lines, words, and characters in a disk file or from the standard input. -l
- displays the number of lines
-w
- displays the number of words
-c
- displays the number of characters
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
217
General purpose utilities
Advanced Java Programming
cmp
SYSTEM
Returns the offset and the line number of the first position where the two files differ.
comm
PROGRAMMING col1 - unique lines of first file
col2 - unique lines of second file col3 - common lines
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
218
General purpose utilities
Advanced Java Programming
diff
SYSTEM
Indicate the differences between the files a Lines added
d Lines deleted c Lines changed
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
219
find
Lets user to search set of files and directories based on various criteria Syntax: find [path...] [expression] [path]
SYSTEM
[expression] PROGRAMMING where to search
what type of file to search (specified with –type option) What action to be applied (–exec, –print, etc.) Name of the files (specified as part of –name option, enclosed in “ “)
IN LINUX
Example
find . –name “*.c” -print | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
220
find
Finding files on the basis of file size
SYSTEM
– size [+ –]n[bc]
• n represents size in bytes (c) or blocks (b) of 512 bytes • find . –size 1000c lists all files that are exactly 1000 bytes in size • find . –size +1000c lists all files that are more than 1000 bytes in size • find . –size –1000c lists all files that are less than 1000 bytes in size
PROGRAMMING IN LINUX
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
221
find
Finding files on the basis of access time (atime) or modified time (mtime)
SYSTEM
– atime [+-]n
– mtime [+-]n
PROGRAMMING •
n represents number of days ( actually 24 * n hours)
• find . –atime 2 days ago • find . –atime +2 2 days ago • find / –mtime –2 2 days ago
lists files accessed exactly 2
lists files accessed more than
IN LINUX
| U. K. Roy |
lists files modified less than
[
]
System Programming in Linux Advanced Java Programming
222
find
Applying a command on files matching the criteria with – exec and –ok options
SYSTEM
– exec command {} \;
• command is command to be applied on the matching files (does not prompt user) • find . -name “*.dat” –exec ls –l {} \; • Long listing of all files with .dat extension in the current and its subdirectories
PROGRAMMING -ok command {} \;
IN LINUX
• Functionality is similar to –exec, but prompts user before applying the command on the file matching the criteria.
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
•
•
pr
223
pr
SYSTEM
•
Used to display a file in a format to be printed.
•
Breaks up a file into pages with a header, text and footer area
PROGRAMMING Options
| U. K. Roy |
-l
to alter the length of the file
-h
to set the header
-t
to suppress the header and the footer
-n
to set the line number
IN LINUX [
]
System Programming in Linux
224
Standard files
Advanced Java Programming
Standard Input file
SYSTEM
Keyboard, file descriptor is 0
Standard Output file Monitor, file descriptor is 1
PROGRAMMING Standard Error file
Monitor, file descriptor is 2
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
225
I/O redirection
Advanced Java Programming
< file redirect standard input from file > file redirect standard output to file 2> file redirect standard error to file 2>&1 merge standard error with standard output $ cat > abc
SYSTEM
PROGRAMMING $ ls –l > outfile
$ cat xyz abc > outfile 2> errfile
$ cat xyz abc > outfile 2>&1
| U. K. Roy |
IN LINUX [
]
System Programming in Linux Advanced Java Programming
226
Filters
Filters are programs that takes its input from the standard input file, process it, and sends it to the standard output file.
Commonly used filter commands
SYSTEM
PROGRAMMING sort
grep cut
head tail paste
| U. K. Roy |
IN LINUX [
]
System Programming in Linux Advanced Java Programming
sort
SYSTEM
Sorts the contents of the given file based on the first char of each line. -n --numeric sort -r --Reverse sort -t -Specify delimiter for fields
PROGRAMMING
+num -specify sorting field numbers +num -num - to specify the range
can specify the characters in the field
227
| U. K. Roy |
IN LINUX [
]
System Programming in Linux Advanced Java Programming
228
grep
SYSTEM
grep -Global Regular Expression Printer is used for searching regular expressions Syntax grep
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
229
grep options
Advanced Java Programming
-c
SYSTEM
occurrences -n
displays count of the number of
displays line numbers along with the lines
PROGRAMMING -v
displays all lines except lines matching pattern -i
| U. K. Roy |
Ignores case for matching
IN LINUX [
]
System Programming in Linux Advanced Java Programming
230
Patterns
* - matches 0 or more characters
[^pqr] - Matches a single character which is not p ,q or r
^pqr -Matches pqr at the beginning of the line
SYSTEM
PROGRAMMING pqr$ -Matches pqr at the end of the line
“.” - Matches any one character
\ - ignores the special meaning. grep “New\[abc\]” filename
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux
231
Filter command - head
Advanced Java Programming
SYSTEM
Displays the top n lines of the file
Can specify top n lines to be displayed
$ head -3 file1
PROGRAMMING IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
232
Filter command - tail
Advanced Java Programming
Displays the end of the file Can specify last n lines to be displayed
$ tail -3 file1
SYSTEM
PROGRAMMING Can also specify the line number from which the data has to be displayed $ tail +5 file1
| U. K. Roy |
IN LINUX [
]
System Programming in Linux
233
Filter command - tr
Advanced Java Programming
SYSTEM
tr - translate filter used to translate a given set of characters
usage :
PROGRAMMING tr [a-z] [A-Z]
option -s can be used to squeeze the repeated characters.
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
234
Filter command - tr
Advanced Java Programming
SYSTEM
Useful options for tr
-s char
Squeeze multiple contiguous occurrences of the character into single char
PROGRAMMING
-d char
Remove the character
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
235
Command piping
Advanced Java Programming
SYSTEM
•
Allows the output (only the standard output) of a command to be sent as input to another command.
•
Multiple pipes may appear in one command line.
PROGRAMMING Example:
$ cat * | wc
$ cat fil1 | head | wc -l
| U. K. Roy |
IN LINUX [
]
System Programming in Linux
236
Filter command - tee
Advanced Java Programming
•
tee command allows the normal output to the standard output, as well as to a file
•
Useful to capture intermediate output of a long command pipeline for further processing, or debugging purpose.
•
SYSTEM
PROGRAMMING Example • •
| U. K. Roy |
who | tee userlist cat - | tee file1 | wc -l
IN LINUX [
]
System Programming in Linux
237
Filter command - cut
Advanced Java Programming
Used to extract specified columns from the output of certain commands -c used to extract characters -d Delimiter for fields -f Field no. Examples cut -c2-5 file1 cut -d “|” -f2,3 file1
SYSTEM
PROGRAMMING IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
238
Filter command - paste
Advanced Java Programming
Paste is used to fix two cut portions of the file vertically
-s
SYSTEM
Pastes the contents of file2 below file1
PROGRAMMING -d Specify delimiter
$ paste -d”|” file1 file2
IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
239
telnet
SYSTEM
telnet hostname or telnet
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
ftp hostname
240
ftp
SYSTEM
put/send: Transfer to Other hosts put [local_file [remote_file]]
PROGRAMMING get/recv: Transfer From Other hosts
get [remote_file [local_file]]
IN LINUX
mput: Multiple Transfer to Other hosts
| U. K. Roy |
[
]
System Programming in Linux
241
Compression utilities
Advanced Java Programming
SYSTEM
gzip, Usage is very similar to compress and pack utilities in Unix: gzip [-vc] filename
PROGRAMMING
where -v displays the compression ratio. -c sends the compressed output to standard output and leaves the original file intact.
IN LINUX
gunzip gunzip can uncompress files originally compressed with compress.
| U. K. Roy |
[
]
System Programming in Linux
242
Tape archive - tar
Advanced Java Programming
SYSTEM
•
Tar is an archiving utility to store and retrieve files from an archive, known as tarfile.
•
Though archives are created on a tape, it is common to have them as disk files as well.
PROGRAMMING –
tar c|t|x [vf destination] source...
Examples: Create a new tar file containing all .dat files (assuming a.dat, b.dat and c.dat exist) $ tar –cf mytar *.dat
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux Advanced Java Programming
•
243
Summary
In this session, you have learned to: •
•
SYSTEM
use the Unix Utilities like • cat, echo, touch, more, file, wc, cmp, comm, find employ redirection operators use filters like • sort, grep, cut, head, tail, tr, and paste communication commands • telnet, ftp backup commands • zip/gzip and tar
PROGRAMMING •
•
•
| U. K. Roy |
IN LINUX
[
]
Chapter 5 Process
System Programming in Linux Advanced Java Programming
•
245
Objectives
In this session, you will learn to:
SYSTEM
•
Define a process
•
Use process-related commands like • ps, kill, sleep
•
Start a Background process
•
Use background and foreground-related commands like • bg, fg, jobs , nice , nohup
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
246
Process
SYSTEM
•
Process - a program in execution
•
When program is executed, a new process is created.
•
The process is alive till the execution of the program is complete.
•
Each process is identified by a number called pid.
PROGRAMMING
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux Advanced Java Programming
247
Login shell
As soon as the user logs in, a process is created which executes the login shell.
Login shell is set for each login in /etc/passwd file.
SYSTEM
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
248
ps
•
The ps command is used to display the characteristics of a process
•
It fetches the pid, tty, time, and the command which has started the process.
SYSTEM
PROGRAMMING -f
lists the pid of the parent process also.
-u
lists the processes of a given user
-a
lists the processes of all the users
-e
lists all the processes including the system processes
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
249
Background process
Advanced Java Programming
SYSTEM
Enables the user to do more than one task at a time.
If the command terminates with an ampersand (&), UNIX executes the command in the background
Shell returns by displaying the process ID (PID) and job id of the process
PROGRAMMING IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
250
Background process
Advanced Java Programming
nohup
SYSTEM
Lets processes to continue to run even after logout The output of the command is sent to nohup.out if not redirected
PROGRAMMING $ nohup command args
$ nohup sort emp.lst & [1] 21356
IN LINUX
nohup: appending output to `nohup.out'
| U. K. Roy |
[
]
System Programming in Linux
251
Background process
Advanced Java Programming
SYSTEM
wait command
can be used when a process has to wait for the output of a background process The wait command, can be used to let the shell wait for all background processes terminate.
PROGRAMMING $ wait
It is possible to wait for completion of one specific process as well.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
252
Controlling background process
Advanced Java Programming
SYSTEM
•
jobs
•
List the background process fg % <job id> •
PROGRAMMING Runs a process in the foreground bg %<job id> •
•
•
Runs a process in the background
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
253
Process priority
Advanced Java Programming
•
nice •
SYSTEM
Used to reduce the priority of jobs
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
254
kill
SYSTEM
•
kill: Kills or terminates a process
•
kill command send a signal to the process The default signal is 15 ( SIGTERM)
PROGRAMMING •
kill -9 (SIGKILL) • Terminates the process abruptly
IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
•
255
Summary
In this session, you learned to:
SYSTEM
•
Define a process
•
Use process-related commands like • ps, kill, sleep
•
Start a background process
•
Use background and foreground-related commands like • bg, fg, jobs
PROGRAMMING IN LINUX | U. K. Roy |
[
]
Chapter 6 UNIX
Shell Programming
System Programming in Linux Advanced Java Programming
•
257
Objectives
In this session, you will learn to:
SYSTEM
•
Use Shell variables
•
Write scripts to process positional parameters
•
Use “test” command
•
Use “if” construct
•
Use “for” loop
•
Use “while” loop
•
Use “case” construct
•
Define and use functions
•
Debug shell scripts
PROGRAMMING
| U. K. Roy |
IN LINUX [
]
System Programming in Linux
258
Flavors of UNIX shell
Advanced Java Programming
SYSTEM
•
Bourne shell
•
C shell
•
Korn shell
•
Bourne again shell bash (shell distributed with linux)
•
sh
csh
PROGRAMMING ksh
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
259
Command processing
Advanced Java Programming
SYSTEM
•
Displays the shell prompt and reads the command typed by the user.
•
Interprets the command and classifies it as an internal (built-in), or an external command.
•
If it is NOT a built-in command, searches for the command in the PATH-specified directories, and executes that command if it is found.
PROGRAMMING IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
260
Shell features
Advanced Java Programming
SYSTEM
Parent shell process fork
(bash)
$ vi test.c
command typed by user
PROGRAMMING Child shell process (bash)
Exec of “vi test.c”
User Mode Kernel Mode
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
261
Additional shell features
Advanced Java Programming
SYSTEM
Each shell, apart from the basic features, provides additional features such as:
•
PROGRAMMING Maintaining command history (C, korn and bash) Renaming (aliasing) a command (C, korn, bash) Command editing (C, korn and bash)
IN LINUX
Programming language (all shells)
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
• • • •
262
History
SYSTEM
some UNIX shells support command history facility to keeps track of commands that were executed facility to rerun previously executed commands bash shell supports the following
PROGRAMMING !!
recall the last command and execute it.
!num
execute nth command where n is the the num specified after !
| U. K. Roy |
IN LINUX [
]
System Programming in Linux Advanced Java Programming
263
alias
SYSTEM
• alias can be used to give new name to an existing command • A better name that represents a single command or a sequence of commands to be executed, often with appropriate options • alias is an internal command
PROGRAMMING alias newname=command $ alias l=‘ls –l’
IN LINUX
The unalias command cancels previously defined alias.
| U. K. Roy |
[
]
System Programming in Linux
264
File name substitution
Advanced Java Programming
•
When the user enters a command string, the shell parses the string into following components: •
SYSTEM
Command (the first part of the string, till the first space char) Command arguments (the subsequent parts of the string)
PROGRAMMING •
•
For example, given the command-string “ls –l *.c”, this string contains the “ls” command and two arguments “-l” and “*.c”.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
265
File name substitution
Advanced Java Programming
•
SYSTEM
In arguments of a command, the shell recognizes certain characters – such as *, ?, [ ], and - as special characters and expands these characters into a filename list before executing the command.
PROGRAMMING
•
To see how this works, enter following commands while in /bin directory
$ ls a*
IN LINUX
$ ls ??
| U. K. Roy |
[
]
System Programming in Linux
266
Shell programming
Advanced Java Programming
•
Allows
SYSTEM
•
Defining and referencing variables
•
Logic control structures such as if, for, while, case
•
Input and output
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
267
Shell variables
Advanced Java Programming
•
A variable is a name associated with a data value, and it offers a symbolic way to represent and manipulate data variables in the shell. They are classified as follows
SYSTEM
•
user-defined variables
•
environment variables
•
predefined variables
PROGRAMMING
•
value assigned to the variable can then be referred to by preceding the variable name with a $ sign.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
268
Shell variables
Advanced Java Programming
SYSTEM
•
The shell provides the facility to define normal, and environment variables.
•
A normal variable can be only used in the shell where it is defined.
•
PROGRAMMING An environment variable can be used in the shell where it is defined, plus any child shells invoked from that shell.
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
269
Using normal variables
Advanced Java Programming
•
To define a normal variable, use the following syntax:
SYSTEM
variable_name=value •
Examples:
PROGRAMMING $ x=10 $ textline_1=‘This line was entered by $USER’ $ textline_2=“This line was entered by $USER” $ allusers=`who` $ usercount=`who | wc –l`
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
270
Using normal variables
Advanced Java Programming
•
SYSTEM
Once variables are defined, one can use the echo command to display the value of each variable:
$ $ $ $ $
echo echo echo echo echo
$x $textline_1 $textline_2 $allusers $usercount
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
271
Using environment variables
Advanced Java Programming
SYSTEM
• • •
To define an environment variable, use following syntax: variable_name=value export variable_name
PROGRAMMING Examples: • $ x=10; export x • $ allusers=`who` ; export allusers
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
272
Built-in environment variables
Advanced Java Programming
SYSTEM
• PATH
• BASH_ENV
• USER
• HOME
• LOGNAME
PROGRAMMING • PWD
• PS1
• SHELL
• PS2
• TERM
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
273
Sample shell script
Advanced Java Programming
SYSTEM
#! /bin/bash # # The above line has a special meaning. It must be the # first line of the script. It says that the commands in # this shell script should be executed by the bash # shell (/bin/bash). # --------------------------------------------------------------echo “Hello $USER….” echo “Welcome to programming shell scripts..” # ---------------------------------------------------------------
PROGRAMMING
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux
274
Executing shell scripts
Advanced Java Programming
There are two ways of executing a shell script:
SYSTEM
By passing the shell script name as an argument to the shell. For example:
PROGRAMMING
sh script1.sh
If the shell script is assigned execute permission, it can be executed using it’s name. For example: ./script1.sh
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux
275
Passing parameters to scripts
Advanced Java Programming
SYSTEM
•
parameter can be passed to a shell script
•
parameters are specified after the name of the shell script when invoking the script.
•
PROGRAMMING
•
Within the shell script, parameters are referenced using the predefined variables $1 through $9.
In case of more than 9 parameters, other parameters can be accessed by shifting.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
276
Built-in variables
Advanced Java Programming
•
SYSTEM
Following are built-in variables supported •
$0, $1…$9 $* $@
- positional arguments - all arguments - all arguments
PROGRAMMING • •
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
277
Passing parameters to scripts
Advanced Java Programming
SYSTEM
•
Consider following shell script:
----------------------script2.sh-------------------------echo “Total parameters entered: $#” echo “First parameter is : $1” echo “The parameters are: $*” shift echo “First parameter is : $1” ------------------------------------------------------------
PROGRAMMING •
| U. K. Roy |
IN LINUX
Execute the above script using the “script2.sh these are the parameters” command.
[
]
System Programming in Linux
278
Passing parameters to scripts
Advanced Java Programming
SYSTEM
•
The shell parameters are passed as strings.
•
to pass a string containing multiple words as a single parameter, it must be enclosed within quotes.
•
PROGRAMMING For example,
parameter”
$ script2.sh “this string is a single
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
279
Doing arithmetic operations
Advanced Java Programming
Arithmetic operations within a shell script can be performed using expr command.
Example, x=10 y=5
•
SYSTEM
PROGRAMMING
•
number_1 = `expr $x + $y` number_2 = `expr $x - $y` number_3 = `expr $x / $y`
IN LINUX
number_4 = `expr $x \* $y`
number_5 = `expr $x % $y`
| U. K. Roy |
[
]
System Programming in Linux
280
Using the test command
Advanced Java Programming
The general syntax of test command is:
SYSTEM
test <expression> •
PROGRAMMING The expression can be formed using a combination of shell variables and the operators supported by the test command. These operators provide facility to compare numbers, string and logical values, file types and file access modes.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
281
Using the test command
Advanced Java Programming
SYSTEM
To compare two integers using test following operators are available: -eq (equal to) -ne (not equal to) -lt (less than) -le (less than or equal to) -gt (greater than) -ge (greater than or equal to)
PROGRAMMING IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
282
Using the test command
Advanced Java Programming
SYSTEM
Please note that you can only compare two integers using test.
General syntax
PROGRAMMING test [expression]
test integer1 operator integer2 OR [ integer1 operator integer2 ]
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
283
Using the test command
Advanced Java Programming
SYSTEM
To compare two strings using the test command, following operators are available: string1 = string2 (equal to, please note it is a single =) string1 != string2 (not equal to) string1 (string is not NULL) -n string1 (string is not NULL and exists) -z string1 (string is NULL and exists)
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux
284
Using the test command
Advanced Java Programming
SYSTEM
The syntax for this string comparison is: test string1 operator string2 OR [ string1 operator string2 ] OR test operator string OR [ operator string ]
PROGRAMMING IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
285
Using the test command
Advanced Java Programming
SYSTEM
To check a file type/access permissions using the test command, following operators are available:
-s file (file is not empty and exists)
PROGRAMMING -f file (Ordinary file and exists)
-d file (file is a directory and exists) -r file (file is readable and exists)
-w file (file is write-able and exists)
IN LINUX
-x file (file is executable and exists)
| U. K. Roy |
[
]
System Programming in Linux
286
Using the test command
Advanced Java Programming
To check a file type/access permissions using the test command, following operators are available:
SYSTEM
-b file (file is a block device and exists) -c file (file is a character device and exists)
PROGRAMMING -p file (file is a named pipe and exists) -g file (file has sticky bit set)
-u file (file has setuid bit set)
IN LINUX
-t file_des (file descriptor is standard output)
| U. K. Roy |
[
]
System Programming in Linux
287
Combining conditions
Advanced Java Programming
•
SYSTEM
It is possible to combine conditions by using following operators:
-a (logical AND operator)
PROGRAMMING -o (logical OR operator) ! (logical NOT operator)
IN LINUX | U. K. Roy |
[
]
System Programming in Linux
288
Combining conditions
Advanced Java Programming
The syntax for this is:
SYSTEM
test expression_1 –a expression _2, OR [ expression _1 –a expression _2 ]
PROGRAMMING test expression_1 –o expression _2, OR [ expression_1 –o expression_2 ] test
! expression _1 OR [ ! expression _1 ]
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux
289
Condition checking in scripts
Advanced Java Programming
SYSTEM
Bash shell provides the if command to test if a condition is true. The general format of this command is: if condition then command fi
PROGRAMMING
| U. K. Roy |
IN LINUX
The condition is typically formed using the test command.
[
]
System Programming in Linux Advanced Java Programming
290
Example
SYSTEM
# to check if the current directory is the same as your home directory curdir=`pwd` if test “$curdir” != “$HOME” then echo your home dir is not the same as your pesent working directory else echo $HOME is your current directory fi
PROGRAMMING
| U. K. Roy |
IN LINUX
[
]
System Programming in Linux
291
Checking multiple conditions
Advanced Java Programming
SYSTEM
The complex form of if statement is as follows: if condition_1 then
PROGRAMMING command
elif condition_2 then
command else
IN LINUX
command fi
| U. K. Roy |
[
]
System Programming in Linux
292
Using for loop
Advanced Java Programming
SYSTEM
The Bash shell provides a for loop.
is:
The syntax of this loop
Example:
for i in 1 2 3 4 5 do echo -n $i \* $i = " " echo `expr $i \* $i ` done
PROGRAMMING
for variable in list do command … command done
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
293
Example
SYSTEM
----------------------script.sh--------------------------
#! /bin/sh
usernames=`who | cut –d “ “ –f1`
echo “Total users logged in = $#usernames”
PROGRAMMING #
for user in ${usernames} do
echo $user done
IN LINUX
------------------------------------------------------------
| U. K. Roy |
[
]
System Programming in Linux
294
Using while loop
Advanced Java Programming
SYSTEM
The Bash shell provides a while loop. The syntax of this loop is: while condition do command … command done
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
295
Example
SYSTEM
Shell script checks for a blank/non blank string eg: read nam while [ -z “$nam” ] do read nam done echo the string is $nam
PROGRAMMING
the above piece of code keeps accepting string variable nam until it is non zero in length.
IN LINUX
| U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
Example
SYSTEM
Shell script to compute factorial of a given number
#!/bin/bash n=$1 if [ $n -eq 0 ]; then fact=0 else fact=1 while [ $n –ne 0 ] do fact=`expr $fact \* $n` n=`expr $n – 1` done fi echo $fact
296
PROGRAMMING
| U. K. Roy |
IN LINUX [
]
System Programming in Linux
297
case statement
Advanced Java Programming
SYSTEM
- THE CASE STATEMENT case value in pattern1) command command;; pattern2) command command;; patternn) command;; esac
PROGRAMMING
| U. K. Roy |
IN LINUX [
]
System Programming in Linux Advanced Java Programming
298
Example
#!/bin/bash echo enter a choice read choice case $choice in 1) echo enter 2 nos read num1 read num2 res=`expr $num1 + $num2` echo result is $res;; 2) who;; *) echo invalid choice;;
SYSTEM
PROGRAMMING esac
| U. K. Roy |
IN LINUX [
]
System Programming in Linux Advanced Java Programming
Example
#!/bin/bash read number case $number 1) echo 1st break;; 2) echo 2nd break;; 3) echo 3rd break;; *) echo ${number}th break;; esac
SYSTEM
299
PROGRAMMING
| U. K. Roy |
IN LINUX [
]
System Programming in Linux Advanced Java Programming
300
Functions
SYSTEM
Shell functions are a way to group commands for later execution using a single name for the group. They are executed just like a "regular" command.
PROGRAMMING
Shell functions are executed in the current shell context; no new process is created to interpret them. Functions are declared using this syntax: [ function ] name () { command-list; }
IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
301
Functions
SYSTEM
Shell functions can accept arguments Arguments are passed in the same way as given to commands Functions refer to arguments using $1, $2 etc., similar to the way shell scripts refer to command line arguments
PROGRAMMING IN LINUX | U. K. Roy |
[
]
System Programming in Linux Advanced Java Programming
302
Functions
SYSTEM
Function to convert standard input into upper case
toupper() { tr A-Z a-z }
This function can be used as
$ cat abc | toupper
PROGRAMMING
| U. K. Roy |
IN LINUX [
]
System Programming in Linux
303
Debugging shell scripts
Advanced Java Programming
SYSTEM
Two options help in debugging shell scripts “-v” (verbose) option:
causes shell to print the lines of the script as they are read.
PROGRAMMING
$ bash –v script-file
“-x” (verbose) option:
IN LINUX
prints commands and their arguments as they are executed.
| U. K. Roy |
$ bash –x script-file
[
]
System Programming in Linux
304
Programming in C vs shell
Advanced Java Programming
Comparison between
SYSTEM
•
A solution in C
•
A shell solution written like a C program
•
A proper “shell/unix” solution
PROGRAMMING e.g: The problem is to count the no of lines in a file ( the file is called the_file)
IN LINUX | U. K. Roy |
[
]
Programming in C vs shell
C program to count lines in a file #include
<stdio.h> void main(void) { int lcount=0; FILE *infile; char line[500];
infile=fopen("the_file","r"); while(!feof(infile)) { fgets(line,500,infile); lcount ++; } printf("no of lines is %d\n",lcount); }
Solution in Bash count=0 while
read line
do
count=`expr $count +
1` done < the_file echo
Number of lines is $count using existing Solution
commands $ wc –l the_file
System Programming in Linux Advanced Java Programming
•
306
Summary
In this session, you have learned to:
SYSTEM
•
Use Shell variables
•
Write scripts to process positional parameters
•
Use “test” command
•
Use “if” construct
•
Use “for” loop
•
Use “while” loop
•
Use “case” construct
•
Define and use functions
•
Debug shell scripts
PROGRAMMING
| U. K. Roy |
IN LINUX [
]
System Programming in Linux
307
Bibliography
Advanced Java Programming
UNIX for the Impatient, Paul W. Abrahams & Bruce R. Larson (Addison-Wesley Publishing Company, 1992, ISBN 0-20155703-7).
SYSTEM
PROGRAMMING UNIX in a Nutshell for BSD 4.3: A Desktop Quick Reference For Berkeley (O'Reilly & Associates, Inc., 1990, ISBN 0-937175-20-X). (A handy reference for BSD.)
IN LINUX
UNIX in a Nutshell: A Desktop Quick
| U. K. Roy |
[
]
System Programming in Linux
308
Advanced Java Programming
SYSTEM Thank You
PROGRAMMING IN LINUX | U. K. Roy |
[
]
Related Documents
System Programming In Linux
November 2019 7
System Programming
November 2019 11
Vb System Programming In Practice
November 2019 3
Linux Kernel Module Programming
October 2019 16
Linux Kernel Programming
November 2019 26