A. S. Tanenbaum. Modern Operating System 2nd Ed.

1.1 WHAT IS AN OPERATING SYSTEM?

Most computer users have had some experience with an operating system, but it is difficult to pin down precisely what an operating system is. Part of the problem is that operating systems perform two basically unrelated functions, extending the machine and managing resources, and depending on who is doing the talking, you hear mostly about one function or the other. Let us now look at both.

1.1.1 The Operating System as an Extended Machine

The program that hides the truth about the hardware from the programmer and presents a nice, simple view of named files that can be read and written is, of course, the operating system. Just as the operating system shields the programmer from the disk hardware and presents a simple file-oriented interface, it also conceals a lot of unpleasant business concerning interrupts, timers, memory management, and other low-level features. In each case, the abstraction offered by the operating system is simpler and easier to use than that offered by the underlying hardware.

In this view, the function of the operating system is to present the user with the equivalent of an extended machine or virtual machine that is easier to program than the underlying hardware. How the operating system achieves this goal is a long story, which we will study in detail throughout this book. To summarize it in a nutshell, the operating system provides a variety of services that programs can obtain using special instructions called system calls. We will examine some of the more common system calls later in this chapter.

1.1.2 The Operating System as a Resource Manager

The concept of the operating system as primarily providing its users with a convenient interface is a top-down view. An alternative, bottom-up, view holds that the operating system is there to manage all the pieces of a complex system. Modern computers consist of processors, memories, timers, disks, mice, network interfaces, printers, and a wide variety of other devices. In the alternative view, the job of the operating system is to provide for an orderly and controlled allocation of the processors, memories, and I/O devices among the various programs competing for them.

Imagine what would happen if three programs running on some computer all tried to print their output simultaneously on the same printer. The first few lines of printout might be from program 1, the next few from program 2, then some from program 3, and so forth. The result would be chaos. The operating system can bring order to the potential chaos by buffering all the output destined for the printer on the disk. When one program is finished, the operating system can then copy its output from the disk file where it has been stored to the printer, while at the same time the other program can continue generating more output, oblivious to the fact that the output is not really going to the printer (yet).

When a computer (or network) has multiple users, the need for managing and protecting the memory, I/O devices, and other resources is even greater, since the users might otherwise interfere with one another. In addition, users often need to share not only hardware, but information (files, databases, etc.) as well. In short, this view of the operating system holds that its primary task is to keep track of who is using which resource, to grant resource requests, to account for usage, and to mediate conflicting requests from different programs and users.

Resource management includes multiplexing (sharing) resources in two ways: in time and in space. When a resource is time multiplexed, different programs or users take turns using it. First one of them gets to use the resource, then another, and so on. For example, with only one CPU and multiple programs that want to run on it, the operating system first allocates the CPU to one program, then after it has run long enough, another one gets to use the CPU, then another, and then eventually the first one again. Determining how the resource is time multiplexed — who goes next and for how long — is the task of the operating system. Another example of time multiplexing is sharing the printer. When multiple print jobs are queued up for printing on a single printer, a decision has to be made about which one is to be printed next.

The other kind of multiplexing is space multiplexing, instead of the customers taking turns, each one gets part of the resource. For example, main memory is normally divided up among several running programs, so each one can be resident at the same time (for example, in order to take turns using the CPU). Assuming there is enough memory to hold multiple programs, it is more efficient to hold several programs in memory at once rather than give one of them all of it, especially if it only needs a small fraction of the total. Of course, this raises issues of fairness, protection, and so on, and it is up to the operating system to solve them. Another resource that is space multiplexed is the (hard) disk. In many systems a single disk can hold files from many users at the same time. Allocating disk space and keeping track of who is using which disk blocks is a typical operating system resource management task.

1.10 METRIC UNITS

To avoid any confusion, it is worth stating explicitly that in this book, as in computer science in general, metric units are used instead of traditional English units (the furlong-stone-fortnight system). The principal metric prefixes are listed in Fig. 1-29. The prefixes are typically abbreviated by their first letters, with the units greater than 1 capitalized. Thus a 1-TB database occupies 10¹² bytes of storage and a 100 psec (or 100 ps) clock ticks every 10⁻¹⁰ seconds. Since milli and micro both begin with the letter “m” a choice had to be made. Normally, “m” is for milli and “µ” (the Greek letter mu) is for micro.

Figure 1-29. The principal metric prefixes.

It is also worth pointing out that for measuring memory sizes, in common industry practice, the units have slightly different meanings. There Kilo means 2¹⁰ (1024) rather than 10³ (1000) because memories are always a power of two. Thus a 1-KB memory contains 1024 bytes, not 1000 bytes. Similarly, a 1-MB memory contains 2²⁰ (1,048,576) bytes and a 1-GB memory contains 2³⁰ (1,073,741,824) bytes. However, a 1-Kbps communication line transmits 1000 bits per second and a 10-Mbps LAN runs at 10,000,000 bits/sec because these speeds are not powers of two. Unfortunately, many people tend to mix up these two systems, especially for disk sizes. To avoid ambiguity, in this book, we will use the symbols KB, MB, and GB for 2¹⁰, 2²⁰, and 2³⁰ bytes respectively, and the symbols Kbps, Mbps, and Gbps for 10³, 10⁶ and 10⁹ bits/sec, respectively.

1.11 SUMMARY

Operating systems can be viewed from two viewpoints: resource managers and extended machines. In the resource manager view, the operating system’s job is to manage the different parts of the system efficiently. In the extended machine view, the job of the system is to provide the users with a virtual machine that is more convenient to use than the actual machine.

Operating systems have a long history, starting from the days when they replaced the operator, to modern multiprogramming systems. Highlights include early batch systems, multiprogramming systems, and personal computer systems.

Since operating systems interact closely with the hardware, some knowledge of computer hardware is useful to understanding them. Computers are built up of processors, memories, and I/O devices. These parts are connected by buses.

The basic concepts on which all operating systems are built are processes, memory management, I/O management, the file system, and security. Each of these will be treated in a subsequent chapter.

The heart of any operating system is the set of system calls that it can handle. These tell what the operating system really does. For UNIX, we have looked at four groups of system calls. The first group of system calls relates to process creation and termination. The second group is for reading and writing files. The third group is for directory management. The fourth group contains miscellaneous calls.

Operating systems can be structured in several ways. The most common ones are as a monolithic system, a hierarchy of layers, a virtual machine system, an exokernel, or using the client-server model.

SLIDES

Download: https://github.com/anhnh2/Modern-Operating-Systems/blob/master/OSG202-slides.zip?raw=true

PROBLEMS

1.9. Which of the following instructions should be allowed only in kernel mode?
(a) Disable all interrupts.
(b) Read the time-of-day clock.
(c) Set the time-of-day dock.
(d) Change the memory heap.

1-12. Consider a computer system that has cache memory, main memory (RAM) and disk, and the operating system uses virtual memory. It takes 2 nsec to access a word from the cache, 10 nsec to access a word from RAM, and 10 ms to access a word from the disk. If the cache hit rate is 95% and memory hit rate (after a cache miss) is 99%, what is the average time to access a word?

1-11 [2nd edition]. An alert reviewer notices a consistent spelling error in the manuscript of an operating systems textbook that is about to go to press. The book has approximately 700 pages, each with 50 lines of 80 characters each. How long will it take to electronically scan the text for the case of the master copy being in each of the levels of memory of Fig. 1-7? For internal storage methods, consider that the access time given is per character, for disk devices assume the time is per block of 1024 characters, and for tape assume the time given is to the start of the data with subsequent access at the same speed as disk access.

Figure 1-7. A typical memory hierarchy. The numbers are very rough approximations.

2-3. A computer system has enough room to hold four programs in its main memory. These programs are idle waiting for I/O half the time. What fraction of the CPU time is wasted?

2-4. A computer has 2 GB of RAM of which the operating system occupies 256 MB. The processes are all 128 MB (for simplicity) and have the same characteristics. If the goal is 99% CPU utilization, what is the maximum I/O wait that can be tolerated?

2.33. Five jobs are waiting to be run. Their expected run times are 9, 6, 3, 5, and X. In what order should they be run to minimize average response time? (Your answer will depend on X.)

2.34. Five batch jobs A through E, arrive at a computer center at almost the same time. They have estimated running times of 10, 6, 2, 4, and 8 minutes. Their (externally determined) priorities are 3, 5, 2, 1, and 4, respectively, with 5 being the highest priority. For each of the following scheduling algorithms, determine the mean process turnaround time. Ignore process switching overhead.
(a) Round robin.
(b) Priority scheduling.
(c) First-come, first-served (run in order 10, 6, 2, 4, 8).
(d) Shortest job first.
For (a), assume that the system is multiprogrammed, and that each job gets its fair share of the CPU. For (b) through (d) assume that only one job at a time runs, until it finishes. All jobs are completely CPU bound.

3.4. Consider a swapping system in which memory consists of the following hole sizes in memory order: 10 KB, 4 KB, 20 KB, 18 KB, 7 KB, 9 KB, 12 KB, and 15 KB. Which hole is taken for successive segment requests of
(a) 12 KB
(b) 10 KB
(c) 9 KB
for first fit? Now repeat the question for best fit, worst fit, and next fit.

3-6. Using the page table of Fig. 3-9, give the physical address corresponding to each of the following virtual addresses:
(a) 20
(b) 4100
(c) 8300

Figure 3-9. The relation between virtual addresses and physical memory address is given by the page table. Every page begins on a multiple of 4096 and ends 4095 addresses higher, so 4K-8K means 4096-8191 and 8K to 12K means 8192-12287.

3-11. A computer with a 32-bit address uses a two-level page table. Virtual addresses are split into a 9-bit top-level page table field, an 11-bit second-level page table field, and an offset. How large are the pages and how many are there in the address space?

3-16. A system with 32 bit virtual address. If the page size is 16KB and each table entry occupies 4 bytes, what is the size of the page table?

3-18. A machine has 48-bit virtual addresses and 32-bit physical addresses. Pages are 8K. How many entries are needed for a conventional page table? For an inverted page table?

3-20. Given the logical address 0xAEF9 (in hexadecimal) with a page size of 256 bytes, what is the page number?

3-22. Suppose a virtual address space of 2^32 words and the page size is 2^12 words. If the virtual address is 12345678 in Hexadecimal, what would be the page number in Hexadecimal? (a) 123; (b) 1234; (c) 12345; (d) 123456

3-24. Assume that the Page Table below is in effect with the number of lines per page is 400. What is the actual memory location for line 834?

Page Number  Page Frame Number
0            8
1            10
2            5
3            11

3-28. A computer has four page frames. The time of loading, time of last access, and the R and M bits for each page are as show below (the times are in clock ticks):

Page	Loaded	Last ref.	R	M
0	126	280		1	0
1	230	265		0	01
2	140	270		0	0
3	110	285		1	1

(a) Which page will NRU replace?
(b) Which page will FIFO replace?
(c) Which page will LRU replace?
(d) Which page will second chance replace?

4-14. Consider the i-node shown in Fig. 4-13. If it contains 10 direct addresses of 4 bytes each and all disk blocks are 1024 KB, what is the largest possible file?

Figure 4-13. An example inode.

4-29. A UNIX file system has 1-KB blocks and 4-byte disk addresses. What is the maximum file size if i-nodes contain 10 direct entries, and one single, double, and triple indirect entry each?

4-32. How large is the block size, if the maximum partition size is 128 MB and the FAT type is FAT-16?

4-34. Which FAT type is used, if the maximum partition size is 256 MB and the block size is 4KB?

4-40. A file system manages the files, directories, its storage in the hard disk, and how the files get loaded into memory and used by programs. Each hard disk partition is divided into groups. A group size is ideally in accordance with the structure of the tracks and sectors of the hard disk to make for efficient retrieval. There is no significant performance loss when retrieving data in the same group. Performance loss is noticeable when retrieving data across different groups. Figure 1 shows the structure of a group for some file system. Each group contains a superblock, a group descriptor, a block bitmap, an inode bitmap, an inode table, and finally data blocks.

Figure 4-41. Structure of a group.

File information in inode table contains mode (file permission and kind of file), owner information, size, time stamp, and 8 direct pointers (dbptr 01 to 08) to data blocks plus 2 indirect pointers (dbptr 09 and 10) to more data blocks. If a file makes use of 8 data blocks or less, then up to 8 direct pointers will point to the data blocks used. If the file makes use of 9 data blocks or more, each indirect pointer will point to the data block containing the next 1024 direct pointers for succeeding data blocks.

Figure 4-42. Inode of 4 different files in the same group. Note: “nil” indicates “unused”.

Figure 4-43. Data blocks of the group in Figure 4-31. The addressing is in row-order form. It begins with A01 through A06 and followed by the next row and so on.

(1) Figure 4-32 represents 4 files found in a group, and Figure 4-33 shows the data blocks of the group. Then, what is the value in hexadecimal that the block bitmap in the group contains?
a) D26 F25 FE4
b) D9F 9F9 FE4
c) E52 ED1 EDC
d) FA2 F41 EDC

(2) The file system takes into consideration design issue of fragmentation but does not eliminate it. In the example shown in Figure 4-32 and 4-33, internal fragmentation (unused space) will exist where the file with inode (?) will be most fragmented and the file with inode (?) will have ZERO fragmentation.
a) 39
b) 8D
c) A5
d) FA

(3) Assuming that a series of append file operations are performed in the following order:
• File of inode 8D doubles in size
• File of inode A5 increases by 13000 bytes
• File of inode FA increases by 10000 bytes
• File of inode 39 increases by 8000 bytes
The group will run out of data blocks when the file with inode (?) tries to write its updates.
a) 39
b) 8D
c) A5
d) FA

5.13. How much cylinder skew is needed for a 7200-rpm disk with a track-to-track seek time of 1 msec? The disk has 200 sectors of 512 bytes each on each track.

5.22. Disk requests come in to the disk driver for cylinders 10, 22, 20, 2, 40, 6, and 38, in that order. A seek takes 6 msec per cylinder moved. How much seek time is needed for
(a) First-Come, first served.
(b) Closest cylinder next.
(c) Elevator algorithm (initially moving upward).
In all cases, the arm is initially at cylinder 20.

5-27. The clock interrupt handler on a certain computer requires 2 msec (including process switching overhead) per clock tick. The clock runs at 60 Hz. What fraction of the CPU is devoted to the clock?

5-28. A computer uses a programmable clock in square-wave mode. If a 500 Mhz crystal is used, what should be the value of the holding register to achieve a clock resolution of
(a) a millisecond (a clock tick once every millisecond)?
(b) 100 microseconds?

5-37. Assuming that it takes 10 nsec to copy a byte, how much time does it take to completely rewrite the screen of an 80 character x 25 line text mode memory-mapped screen? What about a 1024 x 768 pixel graphics screen with 24-bit color?

6-18. A computer has six tape drives, with n processes competing for them. Each process may need two drives. For which values of n is the system deadlock free?

6.20. A system has four processes and five allocatable resources. The current allocation and maximum needs are as follows:

              Allocated     Maximum       Available
Process A     1 0 2 1 1     1 1 2 1 3     0 0 x 1 1  
Process B     2 0 1 1 0     2 2 2 1 0  
Process C     1 1 0 1 0     2 1 3 1 0  
Process D     1 1 1 1 0     1 1 2 2 1

What is the smallest value of x for which this is a safe state?

QUIZ

A CPU may have two or more complete processors, so that can carry out multiple threads in the same time is called:
a. Pipeline
b. Superscalar
c. Multicore
d. None of the other choices
Examples of general purpose stored program computers include the following except
a. Personal computers
b. Network servers
c. Workstations
d. MP3 player
Which of the following instructions should be allowed in user mode?
a. Disable all interrupts
b. Read the time-of-day clock
c. Set the time-of-day clock
d. Change the memory map
As one proceeds down the memory hierarchy (from inboard memory to offline storage), which of the following conditions is correct?
a. Decreasing cost per bit
b. Decreasing capacity
c. Decreasing access time
d. None of the other choices
Which of the following actions generates an external interrupt?
a. An input/output operation is completed.
b. A page that does not exist in the main memory is accessed by the virtual storage management.
c. A system call instruction is executed.
d. Division by zero occurs.
What is not a main function of an operating system?
a. Provide the users with an extended (virtual) machine
b. Manage the I/O devices
c. Provide user interfaces
d. Support virtual memory
What is the main characteristic of real-time operating system?
a. Multiple CPU
b. Time-sharing
c. Time is key parameter
d. Many I/O devices
What is correct about trap instructions and interrupts?
a. Trap instruction switches the execution mode of a CPU from the user mode to the kernel mode
b. A trap instruction is caused by a user program to invoke functions in the OS kernel
c. An interrupt is caused by an external event
d. All of the other choices
A simple structuring model for monolithic system includes:
a. A main program that invokes the requested service procedure
b. A set of service procedures that carry out the system calls
c. A set of utility procedures that help the service procedures
d. All of the other choices
A process where no concurrency inside process; everything happens sequentially is called:
a. Random access process
b. Sequential process
c. Sequential access process
d. None of the other choices
Which of the following process state transitions is correct, when the external event for which a process was waiting happens?
a. Running -> Blocked (waiting)
b. Running -> ready
c. Blocked (waiting) -> ready
d. Ready -> running
How many percent of the CPU time is wasted, when a computer system has enough room to hold two program and these programs are idle waiting for I/O half the time?
a. 50%
b. 25%
c. 75%
d. None of the other choices

LAB

Một số chú ý khi sử dụng Ubuntu Linux:

Keywords: ubuntu 12.04 repository archive
https://superuser.com/questions/339537/where-can-i-get-the-repositories-for-old-ubuntu-versions
sudo gedit /etc/apt/sources.list
precise
sudo apt-get update
sudo apt-get install netbeans

Process Monintor: Getting started with Procmon: The Beginner’s Guide to Monitoring Windows Systems

Basic Linux commands: https://github.com/anhnh2/Modern-Operating-Systems/raw/master/os-lab_Linux-commands.pdf

Shell programming: https://github.com/anhnh2/Modern-Operating-Systems/raw/master/os-lab_Shell_programming.pdf

Bài 1: Nhập một số từ bàn phím, in ra màn hình tam giác như sau:

Bài 2: Nhập một số từ bàn phím, in ra màn hình tam giác như sau:

Bài 3: Nhập một số từ bàn phím, in ra màn hình tam giác đối xứng như sau:

Bài 4: Nhập một số từ bàn phím, in ra màn hình hình vẽ sau:

Bài 5: Nhập một số từ bàn phím, in ra màn hình hình vẽ sau:

Bài 6: Viết một Shell script để tạo ra menu tương tác với người dùng gồm 5 lựa chọn như sau (mỗi lựa chọn được 2 điểm):

[1] Show information about you (name, student ID, class)
[2] Show today date/time
[3] Show all files in current directory
[4] Show calendar
[5] Exit/Stop

Tùy vào lựa chọn của người dùng, chương trình đưa ra thông tin tương ứng, nếu người dùng chọn từ 1-4 thì sau khi thực hiện xong một việc phải quay lại để người dùng chọn chức năng tiếp theo. Chỉ khi ấn số 5 thì chương trình mới thoát.

Bài 7: Sử dụng các lệnh sau để kiểm tra thông tin liên quan đến bộ nhớ (memory):

systeminfo | findstr /C:"Total Physical Memory"
$free -m
$cat /proc/meminfo
$vmstat -s
$top
$htop
#dmidecode -t 17
Tools: Task Manager, System Information (msinfo32), System Monitor, CPU-Z…

Tham khảo: https://devconnected.com/how-to-check-ram-on-linux/ và https://book.hacktricks.xyz/forensics/basic-forensic-methodology/memory-dump-analysis/volatility-examples

Bài 8: Dựa trên bài mẫu “copyfile.c” (Tham khảo: https://github.com/anhnh2/Modern-Operating-Systems) bổ sung các yêu cầu sau cho chương trình:
(a) Đưa ra thông báo lỗi khi không nhập đủ tên file nguồn, file đích
(b) Kiểm tra, nếu đối tượng yêu cầu copy không tồn tại hoặc là thư mục thì không copy, và đưa ra thông báo lỗi giống hệt như khi sử dụng lệnh cp trong Linux
(c) Đặt thiết lập các quyền permission cho file mới tạo ra như sau: rw-rw-rw-

Bài 9: Lần lượt chạy các lệnh sau:

winsat disk -drive d
diskspd -d120 -W10 -C10 -c512M -t4 -o4 -b8k -L -r -Sh -w50 D:\io.dat
Get-CimInstance -ClassName Win32_DiskDrive | Select-Object -Property DeviceID, Model, Size, Partitions
dd if=/dev/zero of=testfile bs=1G count=1 oflag=direct (write speed)
dd if=testfile of=/dev/null bs=1G (read speed)
sudo hdparm -Tt /dev/sda (sda, sda1, sda2,..)
Tools: Task Manager, Performance Monitor, Resource Monitor, iostat (package sysstat), fio, System Monitor…