132 The Newcastle Connection

The previous section explored a tightly coupled system configuration where all file subsystem calls on a satellite processor are trapped and forwarded to a remote (central) processor. This view extends to more loosely coupled systems, where each machine wants to access files on the other machines. In a network of personal computers and work stations, for example, users may want to access files stored on a mainframe. The next two sections consider system configurations where local systems...

518 File System Maintenance

The kernel maintains consistency of the file system during normal operation. However, extraordinary circumstances such as a power failure may cause a system crash that leaves a file system in an inconsistent state most of the data in the file system is acceptable for use, but some inconsistencies exist. The command fsck checks for such inconsistencies and repairs the file system if necessary. It accesses the file system by its block or raw interface (Chapter 10) and bypasses the regular file...

84

Mapping a File into a Region The page stealer is a kernel process that swaps out memory pages that are no longer part of the working set of a process. The kernel creates the page stealer during system initialization and invokes it throughout the lifetime of the system when low on free pages. It examines every active, unlocked region, skipping locked regions in the expectation of examining them during its next pass through the region list, and increments the age field of all valid...

Preface

The UNIX system was first described in a 1974 paper in the Communications of the ACM Thompson 74 by Ken Thompson and Dennis Ritchie. Since that time, it has become increasingly widespread and popular throughout the computer industry where more and more vendors are offering support for it on their machines. It is especially popular in universities where it is frequently used for operating systems research and case studies. Many books and papers have described parts of the system, among them, two...

79 System Boot And The Init Process

To initialize a system from an inactive state, an administrator goes through a bootstrap sequence The administrator boots the system. Boot procedures vary according to machine type, but the goal is common to all machines to get a copy of the operating system into machine memory and to start executing it. This is usually done in a series of stages hence the name bootstrap. The administrator may set switches on the computer console to specify the address of a special hard-coded bootstrap program...

Aqw

Free disk blocks for file (algorithm free, section 4.7) set file type to 0 free inode (algorithm ifrce, section 4.6) if (file accessed or inode changed or file changed) update disk inode put inode on free list When the kernel releases an inodc (algorithm iput, Figure 4.4), it decrements its in-core reference count. If the count drops to 0, the kernel writes the inode to disk if the in-core copy differs from the disk copy. They differ if the file data has changed, if the file access time has...

Fhi

Program where Parent and Child Share File Access The parent and child processes call the function rdwrt, independently, of course, and execute a loop, reading one byte from the source file and wWring it to the target file. The function rdwrt returns when the read system call encounters the end of file. The kernel had incremented the file table counts of the source and target files, and the file descriptors in both processes refer to the same file table entries. That is, the file...

Ymi

If (CP(buffer semaphore) fails) * buffer busy V t V(hash queue semaphore) P(buffer semaphore) * sleep until free * if (CPihash queue semaphore) fails) ( V(buffer semaphore) continue * to while loop * else if (dev or block num changed) V(buffer semaphore) V(hash queue semaphore) continue while (CP(free list semaphore) fails) * spin loop * mark buffer busy remove buffer from free list V(free list semaphore) V(hash queue semaphore) return buffer else * buffer not in hash queue * remainder of...

Vlx

Failed Simulation of Wakeup with V reversed order, the CP operation prevents the deadlock, as shown in Figure 12.12 If the CP fails, process B releases its resources to avoid the deadlock and reenters the algorithm at a later time, presumably when process A completes use of the resource. An interrupt handler may have to lock a semaphore to prevent processes from using a resource simultaneously, but it cannot go to sleep, as explained in Chapter 6, and therefore cannot use a P...

1

Enqueue process at end of sleep list of semaphore Figure 12.8. Algorithm for Implementation of P to test the semaphore and find its value equal to 0 and for process B on processor B to do a P, decrementing the value of the semaphore to 1 (Figure 12.10) just after the test on A, Process A would continue executing, assuming that it had awakened every sleeping process on the semaphore. Hence, the loop does not insure that every sleeping process wakes up, because it is not atomic. algorithm V * V...

Qpv

Lastid - (procid+1) NUMPROCS * reset to next processor * semaphore, vallprocidl 0 Figure 12.6. Implementation of Semaphore Locking (continued) semantics similar to those of the regular sleep algorithm (Chapter 6) It checks for signals according to the priority value, enqueues the executing process on a first-in-first-out list of sleeping processes, and docs a context switch. The V function (Figure 12.9) gains exclusive access to the semaphore via the Pprim primitive and increments the semaphore...

58 Creation Of Special Files

The system call mknod creates special files in the system, including named pipes, device files, and directories. It is similar to creat in that the kernel allocates an node for the file. The syntax of the mknod system call is mknod (pathname, type and permissions, dev) where pathname is the name of the node to be created, type and permissions give the node type (directory, for example) and access permissions for the new file to be created, and dev specifies the major and minor device numbers...

Appendix System Calls

This appendix contains a brief synopsis of the UNIX system calls. Refer to the UNIX System V User Programmer's Manual for a complete specification of these calls. The specification here is sufficient for reference when reading the various program examples in the book. The specified file names are null terminated character strings, whose individual components are separated by slash characters. All system calls return 1 on error, and the external variable errno indicates the specific error....

Figure 732 Sample Inittab File

Getty processes to monitor the terminal lines configured on a system. When a user successfully logs in, getty goes through a login procedure and execs a login shell, described in Chapter 10, Meanwhile, irut executes the wait system call, monitoring the death of its child processes and the death of processes orphaned by exit ing parents. Processes in the UNIX system are either user processes, daemon processes, or kernel processes. Most processes on typical systems are user processes, associated...

Lsx

Example of Wait and Ignoring Death of Child Signal Hie kernel does the above procedure each time the parent receives a death of child signal, until it finally goes through the wait loop and finds that the parent has no children. The wait system call then returns a 1. The difference between the two invocations of the program is that the parent process waits for the termination of any child process in the first case but waits for the termination of all child processes in the second...

121 Problem Of Multiprocessor Systems

Recall from Chapter 2 that the design of the UNIX system protects the integrity of kernel data structures by two policies The kernel cannot preempt a process and switch context to another process while executing in kernel mode, and it masks out interrupts when executing a critical region of code if an interrupt handler could corrupt kernel data structures. On a multiprocessor, however, if two or more processes execute simultaneously in the kernel on separate processors, the kernel could become...

The Structure Of Processes

Chapter 2 formulated the high-level characteristics of processes. This chaptcr presents the ideas more formally, defining the context of a process and showing how the kernel identifies and locatcs a process. Section 6.1 defines the process state model for the UNIX system and the set of state transitions. The kernel contains a process table with an entry that describes the state of every active process in the system. The u area contains additional information that controls the operation of a...

1 10000

Algorithm malloc * algorithm to allocate map space * input (1) map address * indicates which map to use * (2) requested number of units output address, if successful 0, otherwise if (current map entry can fit requested units) if (requested units number of units in entry) delete entry from map adjust start address of entry return (original address of entry) Figure 9.2. Algorithm for Allocating Space from Maps As the kernel allocates and frees resources, it updates the map so that it continues to...

16 Summary

This chapter has described the overall structure of the UNIX system, the relationship between processes running in user mode versus kernel mode, and the assumptions the kernel makes about the hardware. Processes execute in user mode or kernel mode, where they avail themselves of system services using a well-defined set of system calls. The system design encourages programmers to write small programs that do only a few operations but do them well, and then to combine the programs using pipes and...

Info

Range of Process Priorities time and system throughput are better. Second, a process waiting for a free buffer may be waiting for a buffer held by the process waiting for completion of I O. When the I O completes, both processes wake up because they sleep on the same address. If the process waiting for the buffer were to run first, it would sleep again anyway until the other process frees the buffer hence its priority is lower. The kernel adjusts the priority of a process that...

Multiprocessor Systems

The classic design of the UNIX system assumes the use of a uniprocessor architecture, consisting of one CPU, memory, and peripherals. A multiprocessor architecture contains two or more CPUs that share common memory and peripherals (Figure 12.1), potentially providing greater system throughput, because processes can run concurrently on different processors. Each CPU executes independently, but all of them execute one copy of the kernel. Processes behave exactly as they would on a uniprocessor...

Process Scheduling And Time

On a time sharing system, the kernel allocates the CPU to a process for a period of time called a time slice or time quantum, preempts the process and schedules another one when the time slice expires, and reschedules the process to continue execution at a later time. The scheduler function on the UNIX system uses relative time of execution as a parameter to determine which process to schedule next. Every active process has a scheduling priority the kernel switches context to that of the...

Working Of Page Stealer Process

Printf(global d local d n, global, local) Figure 9,16. Vfork and Corruption of Process Memory For example, consider the program in Figure 9.16. After the vfork call, the child process does not exec, but resets the variables global and local and exits.4 The system guarantees that the parent process is suspended until the child process execs or exits. When the parent process finally resumes execution, it finds that the values of the two variables are not the same as they were before the vforkl...

3

The use of pipes frequently makes it unnecessary to create temporary files. 1.4 OPERATING SYSTEM SERVICES Figure 1.1 depicts the kernel layer immediately below the layer of user application programs. The kernel performs various primitive operations on behalf of user processes to support the user interface described above. Among the services provided by the kernel arc Controlling the execution of processes by allowing their creation, termination or suspension, and communication Scheduling...

J

If (first block was originally in cache) ( read first block (algorithm bread) return buffer sleep (event first buffer contains valid data) return buffer Figure 3.14. Algorithm for Block Read Ahead releases the buffer when it awakens. If the write is asynchronous, the kernel starts the disk write but does not wait for the write to complete. The kernel will release the buffer when the I O completes. There are occasions, described in the next two chapters, when the kernel does not write data...

32

For example, if a machine has 2 bytes of physical memory and a page size of IK bytes+ it has 222 pages of physical memory every 32-bit address can be treated as a pair consisting of a 22-bit page number and a 10-bit offset into the page (Figure 6.3). When the kernel assigns physical pages of memory to a region, it need not assign the pages contiguously or in a particular order. The purpose of paged memory is to allow greater flexibility in assigning physical memory, analogous to the...

32k

This section defines the memory model that will be used throughout this book, but it is not specific to the UNIX system. In a memory management architecture based on pages, the memory management hardware divides physical memory into a set of equal-sized blocks called pages. Typical page sises range from 512 bytes to 4K bytes and are defined by the hardware. Every addressable location in memory is contained in a page and, consequently, every memory location can be addressed by a

42 Structure Of A Regular File

As mentioned above, the inode contains the table of contents to locate a file's data on disk. Since each block on a disk is addressable by number, the table of contents consists of a set of disk block numbers. If the data in a file were stored in a contiguous section of the disk (that is, the file occupied a linear sequence of disk blocks), then storing the start block address and the file size in the inode would suffice to access all the data in the file. However, such an allocation strategy...

5

The kernel invokes the interrupt handler. The kernel stack for the new context layer is logically distinct from the kernel stack of the previous context layer. Some implementations use the kernel stack of the executing process to store the interrupt handler stack frames, and other implementations use a global interrupt stack to store the frames for interrupt handlers that are guaranteed to return without switching context. 4. The interrupt handler completes it work and returns. The kernel...

Weo

Get buffer for block removed from super block list (algorithm getblk) decrement total count of free blocks Figure 4,19. Algorithm for Allocating Disk Block 1. The kernel can determine whether an inode is free by inspection If the file type field is clear, the inode is free. The kernel needs no other mechanism to describe free inodes. However, it cannot determine whether a block is free just by looking at it. It could not distinguish between a bit pattern that indicates the block is free and...

Figure 740 Truth Program

The shell tests the exit return from a process, treating a 0 value as true and a non-0 value as false (note the inconsistency with C). Suppose the name of the executable file corresponding to the program in Figure 7.40 is truth. Describe what happens when the shell executes the following loop. Enhancc the sample shell code to handle this case. 33. Why must the shell create the processes to handle the two command components of a pipeline in the indicated order (Figure 7.29) 34. Make the...

99

Search for Block 18, Empty Free List Figure 3.9. Fourth Scenario for Allocating Buffer buffer. For example, if process A attempts to read a disk block and allocates a buffer as in scenario 2, then it will sleep while it waits for the I O transmission from disk to complete. While process A sleeps, suppose the kernel schedules a second process, B, which tries to access the disk block whose buffer was just locked by process A. Process B (going through scenario 5) will find the locked block on the...

711 Exercises

Run the program in Figure 7.33 at the terminal. Redirect its standard output to a file and compare the results. printf(hcllo n) if (forkO 0) Figure 7.33. Fork and the Standard I O Package 2. Describe what happens in the program in Figure 7.34 and compare to the results of Figure 7.4. 3. Reconsider the program in Figure 7.5, where two processes exchange messages through a pair of pipes. What happens if they try to exchange messages through one pipe 4. In general, could there be any loss of...

92 Demand Paging

Machines whose memory architecture is based on pages and whose CPU has restartable instructions3 can support a kernel that implements a demand paging algorithm, swapping pages of memory between main memory and a swap device. Demand paging systems free processes from size limitations otherwise imposed by the amount of physical memory available on a machine. For instance, machines that contain 1 or 2 megabytes of physical memory can execute processes whose sizes are 4 or 5 megabytes. The kernel...

55adjusting The Position Of File Io Lseek

The ordinary use of read and write system calls provides sequential access to a file, but processes can use the seek system call to position the I O and allow random access to a file. The syntax for the system call is position lseek(fd, offset, reference) where fd is the file descriptor identifying the file, offset is a byte offset, and reference indicates whether offset should be considered from the beginning of the file, from the current position of the read write offset, or from the end of...

116

Figure 7.10* Disassembly of Program that Catches Signals User Stack Prior to Receipt of Signal User Stack Prior to Receipt of Signal Kernel Context Layer 1 Kernel Context Layer 1 Register Save Area Register Save Area Figure 7.11. User Stack and Kernel Save Area Before and After Receipt of Signal ramifications A race condition results because a second instance of the signal may arrive before the process has a chance to invoke the system call. Since the process is executing in user mode, the...

Qrm

Algorithm for Receiving a Message the IPC CREAT flag in the msgget call and receives all messages of type I requests from client processes. It reads the message text, finds the process ID of the client process, and sets the return message type to the client process ID. In this example, it sends its proccss ID back to the client process in the message text, and the client process receives messages whose message type equals its process ID. Thus, the server process receives only...

91 Swapping

There are three parts to the description of the swapping algorithm managing space on the swap device, swapping processes out of main memory, and swapping processes into main memory. The swap device is a block device in a configurable section of a disk. Whereas the kernel allocates space for files one block at a time, it allocates space on the swap device in groups of contiguous blocks. Space allocated for files is used statically since it will exist for a long time, the allocation scheme is...

File Table Refrance Count Can Be Greater Than 1 Because Of

A process closes an open file when it no longer wants to access it. The syntax for the close system call is include < fcntl.h> main (arge, argv) int arge char *argv fd - opcniargvtll, 0_RD0NLY) if (fd -1) exitO while ((skval - rcad(fd, & c, 1)) l) ( printfC'char c n, c) skval - IseekCfd, 1023L, 1) printf(new seek val d n, skval) Figure 5.10. Program with Lseek System Call where fd is the file descriptor for the open file. The kernel does the close operation by manipulating the file...

64 Saving The Context Of A Process

As observed in previous sections, the kernel saves the context of a process whenever it pushes a new system context layer. In particular, this happens when the system receives an interrupt, when a process executes a system call, or when the kernel does a context switch. This section considers each case in detail. The system is responsible for handling interrupts, whether they result from hardware (such as from the clock or from peripheral devices), from a programmed interrupt (execution of...

73 Process Termination

Processes on a UNIX system terminate by executing the exit system call. An exiling process enters the zombie stale (recall Figure 6.1), relinquishes its resources, and dismantles its context except for its slot in the process table. The syntax for the call is where the value of status is returned to the parent process for its examination. Processes may call exit explicitly or implicitly at the end of a program the startup routine linked with all C programs calls ejtif when the program returns...

Maurice J Each

Bach traces the popularity of the UNIX System throughout the computer industry. The author describes the internal algorithms and structures that form the basis of the operating system (the kernel) and their relationship to the programmer interface. describes the outline of the kernel architecture introduces the system buffer cache mechanism includes data structures and algorithms used internally by the file system covers the system calls that provide the user...

106 Exercises

* 1, Suppose a system contains two devicc files that have the same major and minor number and are both character devices. If two processes wish to open the physical device simultaneously, show that it makes no difference whether they open the same device file or different device files. What happens when they close the device * 2. Recall from Chapter 5 that the mknod system call requires superuser permission to create a device special file. Given that device access is governed by the permission...

136 Exercises

Describe an implementation of the exit system call on a satellite processor system. How is this different from the case where a process exits as a result of receipt of an uncaught signal'.' How should the kernel dump the core file 2. Processes cannot ignore the SIGKILL signal describe what happens on a satellite system when a process receives this signal. * 3. Describe an implementation of the exec system call on a satellite processor system. * 4. How should a central processor assign...

I

PrintfCneed 2 arguments for copy program nM) exit(l) fdold openiargvtll, O RDONLY) * open source file read only * printfCcannot open file s n, argvfl ) exit(l) fdnew creat(argv 2l, 0660) * create target file rw for all * if (fdnew 1) i printfCcannot create file s n, argv 2 ) exit(l)

471

Placing Free Inode Numbers into the Super Block Consider two examples of freeing inodes. If the super block list of free inodes has room for more free inode numbers as in Figure 4.13(a), the kernel places the inode number on the list, increments the index to the next free inode, and proceeds. But if the list of free inodes is full as in Figure 4.15, the kernel compares the inode number it has freed to the remembered inode number that will start the next disk search. Starting with...

Algo For Attaching A Region In Os

Msgrcvimsgid, & msg, 256, I, 0) pint (int *) msg.mtext pid *pint printf(server receive from pid d n pid) msg.mtype pid pint getpidO msgsnd(msgid, & msg, sizeof(int), 0) Messages are formatted as type-data pairs, whereas file data is a byte stream. The type prefix allows processes to select messages of a particular type, if desired, a feature not readily available in the file system. Processes can thus extract messages of particular types from the message queue in the order that they...

34 Reading And Writing Disk Blocks

Now that the buffer allocation algorithm has been covered, the procedures for reading and writing disk blocks should be easy to understand. To read a disk block (Figure 3.13), a process uses algorithm getblk to search for it in the buffer cache. If it is in the cache, the kernel can return it immediately without physically reading the block from the disk. If it is not in the cache, the kernel calls the disk driver to schedule a read request and goes to sleep awaiting the event that the I O...

5123 Readuq and Writing Pipes

A pipe should be viewed as if processes write into one end of the pipe and read from the other end. As mentioned above, processes access data from a pipe in FIFO manner, meaning that the order that data is written into a pipe is the order that it is read from the pipe. The number of processes reading from a pipe do not necessarily equal the number of processes writing the pipe if the number of readers or writers is greater than 1, they must coordinate use of the pipe with other mechanisms. The...

515 Link

The link system call links a file to a new name in the file system directory structure, creating a new directory entry for an existing node. The syntax for the link system call is link(source file name, target file name) where source file name is the name of an existing file and target file name is the new (additional) name the file will have after completion of the link call. The file system contains a path name for each link the file has, and processes can access the file by any of the path...

82 System Calls For Time

There are several time-related system calls, stime, time, times, and alarm. The first two deal with global system time, and the latter two deal with time for individual processes. Stime allows the superuser to set a global kernel variable to a value that gives the current time where pvalue points to a long integer that gives the time as measured in seconds from midnight before (00 00 00) January 1, 1970, GMT. The clock interrupt handler increments the kernel variable once a second. Time...

11 History

In 1965, Bell Telephone Laboratories joined an effort with the General Electric Company and Project MAC of the Massachusetts Institute of Technology to develop a new operating system called Multics Organick 72J. The goals of the Multics system were to provide simultaneous computer access to a large community of users, to supply ample computation power and data storage, and to allow users to share their data easily, if desired. Many people who later took part in the early development of the UNIX...

8

Callout Table and New Entry for f Figure 8.10 shows an instance of the callout table before and after addition of a new entry for the function . (The negative time field for function a will be explained shortly.) When making a new entry, the kernel finds the correct (timed) position for the new entry and appropriately adjusts the time field of the entry immediately after the new entry. In the figure, the kernel arranges to invoke function after 5 clock ticks it creates an entry for...

M

Major number, 88, 108, 121, 218, 219, 316, 322, 352 Malloc algorithm, 273 Malloc library routine, 243 Mandatory file lock, 142 Map, 272, 273, 277, 308 messages, 361 Massachusetts Institute of Technology, 1 Master processor, 393, 410 MC 68451 memory management unit, 189 McKusick, 72 Memory contention, 410 Memory fault, 231 Memory management, 21, 17, 154 Memory management policy, 152, 271 Memory management register triple, 155-158, 174 Memory management subsystem, 151 Memory mapped I O, 321 MERT,...

26 Exercises

Consider the following sequence of commands grep main a.c b.c c.c > grepout & wc 1 < grepout & rm grepout & The ampersand (& ) at the end of each command line informs the shell to run the command in the background, and it can execute each command line in parallel. Why is this not equivalent to the following command line 2. Consider the sample kernel codc in Figure 2.7. Suppose a context switch happens when the code reaches the comment, and suppose another process removes a...

13 User Perspective

This section briefly reviews high-level features of the UNIX system such as the file system, the processing environment, and building block primitives (for example, pipes). Later chapters will explore kernel support of these features in detail. The UNIX file system is characterized by consistent treatment of file data, the ability to create and delete files, the protection of file data, the treatment of peripheral devices (such as terminals and tape units) as files. The file system is organized...

Which Singals Inform Operating System

Signals inform processes of the occurrence of asynchronous events. Processes may send each other signals with the kill system call, or the kernel may send signals internally. There are 19 signals in the System V (Release 2) UNIX system that can be classified as follows (see the description of the signal system call in SVID 851) Signals having to do with the termination of a process, sent when a process exits or when a process invokes the signal system call with the death of child parameter...

71 Process Creation

The only way for a user to create a new process in the UNIX operating system is to invoke the fork system call. The process that invokes fork is called the parent process, and the newly created process is called the child process. The syntax for the fork system call is On return from the fork system call, the two processes have identical copies of their user-level context exccpt for the return value pid. In the parent process, pid is the child process ID in the child process, pid is 0. Process...

1008000

Disk Sections for RP07 Disk Historically, the sizes and lengths of disk sections have been fixed according to the disk type. For instance, the DEC RP07 disk is partitioned into the sections shown in Figure 10.7. Suppose the files dev dskO, dev dskl, dev dsk2 and '7dev dsk3 correspond to sections 0 through 3 of an RP07 disk and have minor numbers 0 through 3. Assume the size of a logical file system block is the same as that of a disk block. If the kernel attempts to access block...

Qhz

Use major number to index into character device switch table call driver close routine parameter minor number, write device blocks in buffer cache to device use major number to index into block device switch table call driver close routine parameter minor number invalidate device blocks still in buffer cache Figure 10.4. Algorithm for Closing a Device The algorithm for closing a device is similar to the algorithm for closing a regular file (Figure 10.4). However, before the kernel releases the...

36 Summary

This chapter has presented the structure of the buffer cache and the various methods by which the kernel Locates blocks in the cache. The buffer algorithms combine several simple ideas to provide a sophisticated caching mechanism. The kernel uses the least-recently-used replacement algorithm to keep blocks in the 4. The standard I O package available to C language programs includes an j(flush call. This function call flushes data from buffers in the user address space (pari of the package) into...

513

The dup system call copies a file descriptor into the first free slot of the user file descriptor table, returning the new file descriptor to the user. It works for all file types. The syntax of the system call is where fd is the file descriptor being duped and newfd is the new file descriptor that references the file. Because dup duplicates the file descriptor, it increments the count of the corresponding file table entry, which now has one more file descriptor entry that points to it. For...

52 Read

The syntax of the read system call is where fd is the file descriptor returned by open, buffer is the address of a data structure in the user process that will contain the read data on successful completion of the call, count is the number of bytes the user wants to read, and number is the number of bytes actually read. Figure 5.5 depicts the algorithm read for reading a regular file. The kernel gets the file table entry that corresponds to address of buffer in user process number of bytes to...

51 Open

The open system call is the first step a process must take to access the data in a file. The syntax for the open system call is fd open (pathname, flags, modes) where pathname is a file name, flags indicate the type of open (such as for reading or writing), and modes give the file permissions if the file is being created. The open system call returns an integer1 called the user file descriptor. Other file operations, such as reading, writing, seeking, duplicating the file descriptor, setting...

System Calls For The File System

The last chapter described the internal data structures for the file system and the algorithms that manipulate them. This chapter deals with system calls for the file system, using the concepts explored in the previous chapter. It starts with system calls for accessing existing files, such as open, read, write, Iseek, and close, then presents system calls to create new files, namely, creat and mknod, and then examines the system calls that manipulate the inode or that maneuver through the file...

76 The User Id Of A Process

The kernel associates two user IDs with a process, independent of the proccss ID the real user ID and the effective user ID or setuid (set user ID). The real user ID identifies the user who is responsible for the running process. The effective user ID is used to assign ownership of newly created files, to check file access permissions, and to check permission to send signals to processes via the kill system call. The kernel allows a process to change its effective user ID when it execs a setuid...

45 Super Block

So far, this chapter has described the structure of a file, assuming that the inode was previously bound to a file and that the disk blocks containing the data were already assigned. The next sections cover how the kernel assigns inodes and disk blocks. To understand those algorithms, let us examine the structure of the super block. The super block consists of the following fields the size of the file system, the number of free blocks in the file system, a list of free blocks available on the...

Byte Capacity Of A File In Terms Of Direct And Indirect Blocks

Allocation of Contiguous Files and Fragmentation of Free Space For example, suppose a user creates three files, A, B and C, each consisting of 10 disk blocks of storage, and suppose the system allocated storage for the three files contiguously. If the user then wishes to add 5 blocks of data to the middle file, B, the kernel would have to copy file B to a place in the file system that had room for 15 blocks of storage. Aside from the expense of such an operation, the disk blocks...

101 Driver Interfaces

The UNIX system contains two types of devices, block devices and raw or character devices. As defined in Chapter 2, block devices, such as disks and tapes, look like random access storage devices to the rest or the system character devices include all other devices such as terminals and network media. Block devices may have a character device interface, too. The user interface to devices goes through the file system (recall Figure 2.1) Every device has a name that looks like a file name and is...

General Overview Of The System

The UNIX system has become quite popular since its inception in 1969, running on machines of varying processing power from microprocessors to mainframes and providing a common execution environment across them. The system is divided into two parts. The first part consists of programs and services that have made the UNIX system environment so popular it is the part readily apparent to users, including such programs as the shell, mail, text processing packages, and source code control systems....

Unix Building Block Primitive

While ((count read (old, buffer, sizcof(buffer))) > 0) write(new, buffer, count) The program copies any files supplied to it as arguments, provided it has permission to open the existing file and permission to create the new file. The file can be a file of printable characters, such as the source code for the program, or it can contain unprintable characters, even the program itself. Thus, the two copy copy.c newcopy.c copy copy newcopy both work. The old file can also be a directory. For...

48 49

(b) Assigning Free Inode - Super Block List Empty Figure 4.13. Two Arrays of Free Inode Numbers Consider the two pairs of arrays of free inode numbers in Figure 4.13. If the list of free inodes in the super block looks like the first array in Figure 4.13(a) when the kernel assigns an inode, it decrements the index for the next valid inode number to 18 and takes inode number 48. If the list of free inodes in the super block looks like the first array in Figure 4.13(b), it will notice that the...

15 Assumptions About Hardware

The execution of user processes on UNIX systems is divided into two levels user and kernel. When a process executes a system call, the execution mode of the process changes from user mode to kernel mode the operating system executes and attempts to service the user request, returning an error code if it fails. Even if the user makes no explicit requests for operating system services, the operating system still does bookkeeping operations that relate to the user process, handling interrupts,...

Vef

Value of -stack pointer time of trap saved register context for level 0 (user) Figure 6.14. Stack Configuration for Crcat System Call Several library functions can map into one system call entry point. The system call entry point defines the true syntax and semantics for every system call, but the libraries frequently provide a more convenient interface. For example, there are several flavors of the exec system call, such as exeel and execle, which provide slightly different interfaces for one...

Jys

* traced process should resume execution * ptraceCTR RESUME, pid, 1,0) Figure 11.3. Debug A Tracing Process 31. A debugger such as sdb has access to the traced process's symbol table, from which it determines the addresses it uses as parameters to ptrace calls. The use of ptrace for process tracing is primitive and suffers several drawbacks. The kernel must do four context switches to transfer a word of data between a debugger and a traced process The kernel switches context in the debugger in...

59 Change Directory And Change Root

When the system is first booted, process 0 makes the file system root its current directory during initialization. It executes the algorithm iget on the root inode, saves it in the u area as its current directory, and releases the inode lock. When a new process is created via the fork system call, the new process inherits the current directory of the old process in its u area, and the kernel increments the inode reference count accordingly. The algorithm chdir (Figure 5.14) changes the current...

94 Summary

This chapter has explored the UNIX System V algorithms for process swapping and demand paging. The swapping algorithm swaps entire processes between main memory and a swap device. The kernel swaps processes from memory if their size grows such that there is no more room in main memory (as a result of a fork, exec, or sbrk system call or as a result of normal stack growth), or if it has to make room for a process being swapped in. The kernel swaps processes in via the special swapper proccss,...

Mpx Forks In Unix

Push a msg discipline on mpx side continue * back to for loop * open other member of pscudo tty pair, get stdin, stdout, stderr push tty line discipline exec shell * looks like virtual tty * * regular data from tty coming up for virtual tty * demultiplex data read from physical tty, strip off headers and write to appropriate pty continue * back to for loop V case logical tty * a virtual tty is writing a window * encode header indicating what window data is for write header and data to physical...

75 Invoking Other Programs

The exec system call invokes another program, overlaying the memory space of a process with a copy of an executable file. The contents of the user-level context that existed before the exec call are no longer acccssiblc afterward exccpt for exec's parameters, which the kernel copies from the old address space to the new address space. The syntax for the system call is where filename is the name of the executable file being invoked, argv is a pointer to an array of character pointers that arc...

Vhm

Algorithm for Recognizing Signals The kernel handles signals in the context of the process that receives them so a process must run to handle signals. There are three cases for handling signals the process exits on receipt of the signal, it ignores the signal, or it executes a particular (user) function on receipt of the signal. The default action is to call exit in kernel mode, but a process can specify special action to take on receipt of certain signals with the signal system...

Figur 536 A Big Read in a Little Buffer

What happens when the program is executed Why What would happen if the declaration of buf were sandwiched between the declaration of two other arrays of size 10247 How does the kernel recognize that the read is too big for the buffer * 7. The BSD file system allows fragmentation of the last block of a file as needed, according to the following rules Structures similar to the super block keep track of free fragments The kernel does not keep a prcallocatcd...

47 Allocation Of Disk Blocks

When a process writes data to a file, the kernel must allocate disk blocks from the file system for direct data blocks and, sometimes, for indirect blocks. The file system super block contains an array that is used to cache the numbers of free disk blocks in the file system. The utility program mkfs (make file system) organizes the data blocks of a file system in a linked list, such that each link of the list is a disk block that contains an array of free disk block numbers, and one array entry...

What Are The Two Anomalies In Sleep System Call

So far, this chapter has covered all the low-level functions that are executed for the transitions to and from the state kernel running except for the functions that move a proccss into the sleep state. It will conclude with a presentation of the algorithms for sleep, which changes the process state from kernel running to asleep in memory, and wakeup, which changes the process state from asleep to ready to run in memory or swapped. Kernel Context Layer 1 Execute Sys Call Figure 6.29. Typical...

Named Unnamed Pipes Algorithm

Algorithm for Creation of (Unnamed) Pipes Figure 5.16 shows the algorithm for creating unnamed pipes. The kernel assigns an node for a pipe from a file system designated the pipe device using algorithm ialtoc. A pipe device is just a file system from which the kernel can assign inodes and data blocks for pipes. System administrators specify a pipe device during system configuration, and it may be identical to another file system. While a pipe is active, the kernel cannot reassign...

System V Ipc Package In Unix

The UNIX System V IPC package consists of three mechanisms. Messages allow processes to send formatted data streams to arbitrary processes, shared memory allows processes to share parts of their virtual address space, and semaphores allow processes to synchronize execution. Implemented as a unit, they share common properties. Each mechanism contains a table whose entries describe all instances of the mechanism. Each entry contains a numcric key, which is its user-chosen name. Each mechanism...

243

(d) After assigning block number (109) replenish super block free list Figure 4*20 Requesting and Freeing Disk Blocks The UNIX system supports two other file types pipes and special files. A pipe, sometimes called a fifo (for first-in-first-out), differs from a regular file in that its data is transient Once data is read from a pipe, it cannot be read again. Also, the data is read in the order that it was written to the pipe, and the system allows no deviation from that order. The kernel stores...

Algorithm For Freeing Inode In Unix Os

Store inode number in inode list return Figure 4,14. Algorithm for Freeing Inode The algorithm for freeing an inode is much simpler. After incrementing the total number of available inodes in the file system, the kernel checks the lock on the super block. If locked, it avoids race conditions by returning immediately The inode number is not put into the super block, but it can be found on disk and is available for reassignment. If the list is not locked, the kernel checks if it has room for more...

The Io Subsystem

The I O subsystem allows a process to communicate with peripheral devices such as disks, tape drives, terminals, printers, and networks, and the kernel modules that control devices are known as device drivers. There is usually a one-to-one correspondence between device drivers and device types Systems may contain one disk driver to control all disk drives, one terminal driver to control all terminals, and one tape driver to control all tape drives. Installations that have devices from more than...

What Cause Process To Wake Up In Unix

To wake up sleeping processes, the kernel executes the wakeup algorithm (Figure 6.32), either during the usual system call algorithms or when handling an interrupt. For instance, the algorithm iput releases a loeked inode and awakens all processes waiting for the lock to become free. Similarly, the disk interrupt handler awakens a process waiting for I O completion. The kernel raises the processor execution level in wakeup to block out interrupts. Then for every process sleeping on the input...

Scenario Where Kernel Removes The Entries For Sticky Bit Text Regions

Attach region to process (algorithm attachreg) * no such text region exists create one * allocate text region (algorithm allocreg) * region is locked * if (inode mode has sticky bit set) turn on region sticky flag attach region to virtual address indicated by inode file header (algorithm attachreg) if (file specially formatted for paging system) * Chapter 9 discusses this case * else * not formatted for paging system * read file text into region (algorithm loadreg) change region protection in...

The Buffer Cache

As mentioned in the previous chapter, the kernel maintains files on mass storage devices such as disks, and it allows processes to store new information or to recall previously stored information. When a process wants to access data from a file, the kernel brings the data into main memory where the process can examine it, alter it, and request that the data be saved in the file system again. For example, recall the copy program in Figure 1.3 The kernel reads the data from the first file into...

21 Architecture Of The Unix Operating System

It has been noted (see page 239 of Christian 83 ) that the UNIX system supports the illusions that the file system has places and that processes have life. The two entities, files and processes, are the two central concepts in the UNIX system model. Figure 2.1 gives a block diagram of the kernel, showing various modules and their relationships to each other. In particular, it shows the file subsystem on the left and the process control subsystem on the right, the two major components of the...

61 Process States And Transitions

Process Transition Diagram

As outlined in Chapter 2, the lifetime of a process can be conceptually divided into a set of states that describe the proccss. The following list contains the complete set of process states. 1. The process is executing in user mode. 2. The process is executing in kernel mode. 3. The process is not executing but is ready to run as soon as the kernel schedules it. 4. The process is sleeping and resides n main memory. 5. The proccss is ready to run, but the swapper (process 0) must swap the...

131 Satellite Processors

Figure 13.2 shows the architecture for a satellite processor configuration. The purpose of such a configuration is to improve system throughput by offloading processes from the central processor and executing them on the satellite processors. Each satellite processor has no local peripherals cxcept for those it needs to communicate with the central processor The file system and all devices are on the central processor. Without loss of generality, assume that all user processes run on a...

779k

Example of Attaching to an Existing Text Region for one process and causing another process to grow beyond the system limit for proccss size. The two cases where the kernel uses growreg on an existing region are sbrk on the data region of a process and automatic growth of the user stack. Both regions are private. Text regions and shared memory regions cannot grow after they are initialized. These cases will become clear in the next chapter. The kernel now allocates page tables (or...

Riz

Fd - open ( etc passwd' O RDONLY) read (fd, lilbuf, 20) read (fd, bigbuf, 1024) read(fd, lilbuf, 20) Figure 5.7. Sample Program for Reading a File Consider the program in Figure 5.7. The open returns a file descriptor that the user assigns to the variable fd and uses in the subsequent read calls. In the read system call, the kernel verifies that the file descriptor parameter is legal, and that the process had previously opened the file for reading. It stores the values lilbuf, 20, and 0 in the...

Mcf

While (no process picked to execute) for (every process on run queue) pick highest priority process that is loaded in memory else * running on a slave processor * for (every process on run queue that need not run on master) pick highest priority process that is loaded in memory if (no process eligible to execute) idle the machine * interrupt takes machine out of idle state * remove chosen process from run queue switch context to that of chosen process, resume its execution algorithm syscall *...

Pwv

Semid - semgetiSEMKEY, 2, 0777) psembufsemop 1 psembuf.semflg - SFM_lJNDO vsembuf .sem op vsembuf.se mflg - SEM UNDO printf(proc d count d n. gctpidO, count), scmctl(semid, 2, IPC RMID, 0) exitO Figure 11.14. Locking and Unlocking Operations (continued) The kernel reads the array of semaphore operations, oplist, from the user address space and verifies that the semaphore numbers are legal and that the process has the necessary permissions to read or change the semaphores (Figure 11.15). If...

46 Inode Assignment To A New File

The kernel uses algorithm iget to allocate a known inode, one whose (file system and) inode number was previously determined. In algorithm rtamei for instance, the kernel determines the inode number by matching a path name component to a name in a directory. Another algorithm, ialloc, assigns a disk inode to a newly created file. The file system contains a linear list of inodes, as mentioned in Chapter 2. An inode is free if its type field is zero. When a process needs a new inode, the kernel...

512 Pipes

Pipes allow transfer of data between processes in a first-in-first-out manner (F FO), and they also allow synchronization of process execution. Their implementation allows processes to communicate even though they do not know what processes are on the other end of the pipe. The traditional implementation of pipes uses the file system for data storage. There are two kinds of pipes named pipes and, for lack of a better term, unnamed pipes, which are identical except for the way that a process...