目錄
chapter0
chapter1
?binary system
chapter2
chapter3
chapter4
chapter5
Pseudo-Code (or Program Design Language)
way to use fuction
?Algorithm Efficiency
Proof of correctness
chapter6
chapter7
chapter8
Basic Data Structures
?data structures
Related Concepts
Storing Arrays
chapter0
A representation of an algorithm is called a program.
算法的表示稱為程序。
The process of developing a program, encoding it in machine-compatible form, and inserting
it into a machine is called programming.
開發(fā)程序的過程,以機(jī)器兼容的形式編碼它,并插入它進(jìn)入一臺機(jī)器叫做編程。
Programs, and the algorithms they represent, are collectively referred to as software,
in contrast to the machinery itself, which is known as hardware.?
程序,以及它們所代表的算法,被統(tǒng)稱為軟件,與機(jī)器本身形成鮮明對比,即硬件。
chapter1
A device that produces the output of a Boolean operation when given the operation’s input values is called a gate.
當(dāng)給定操作的輸入值稱為柵極時,產(chǎn)生布爾操作輸出的設(shè)備。
Gates provide the building blocks from which computers are constructed.One important step in this direction is depicted in the circuit in Figure 1.3. This is a particular example from a collection of circuits known as a flip-flop.
門提供了建造計(jì)算機(jī)的單元。圖1.3中描述了這個方向的一個重要步驟。這是一個特定的例子,從一個被稱為觸發(fā)器的電路集合。
A technology known as
very large-scale integration (VLSI),
which allows millions of electrical components to be constructed on a wafer (called a chip
), is used to create miniature devices containing millions of flip-flops along with their controlling circuitry. Consequently, these chips are used as abstract tools in the construction of computer systems. In fact, in some cases VLSI is used to create an entire computer system on a single chip.
一種被稱為超大規(guī)模集成(VLSI)的技術(shù)，允許在一塊晶片(稱為芯片)上構(gòu)造數(shù)百萬個電子元件，被用來制造包含數(shù)百萬個觸發(fā)器及其控制電路的微型設(shè)備。因此，這些芯片被用作構(gòu)建計(jì)算機(jī)系統(tǒng)的抽象工具。事實(shí)上，在某些情況下，VLSI被用來在單個芯片上創(chuàng)建一個完整的計(jì)算機(jī)系統(tǒng)。
For the purpose of storing data, a computer contains a large collection of circuits (such as flip-flops), each capable of storing a single bit. This bit reservoir is known as the machine’s main memory.
為了存儲數(shù)據(jù)，計(jì)算機(jī)包含大量的電路(例如觸發(fā)器)，每一個都能存儲一個比特。這個位儲層被稱為機(jī)器的主存儲器。
A computer’s main memory is organized in manageable units called
cells, with a typical cell size being eight bits. (A string of eight bits is called a byte.
計(jì)算機(jī)的主存儲器是由稱為單元的可管理單元組織起來的，單元的典型大小為8位。(由8位組成的字符串稱為字節(jié)。
The left end of this row is called the high-order end,
and the right end is called the low-order end.
這一行的左端稱為高階端，右端稱為低階端。
The left most bit is called either the high-order bit or the most significant bit
in reference to the fact that if the contents of the cell were interpreted as representing a numeric value, this bit would be the most significant digit in the number. Similarly, the rightmost bit is referred to as the low-order bit or the least significant bit.
最左邊的位被稱為高階位或最高有效位，因?yàn)槿绻麊卧竦膬?nèi)容被解釋為表示一個數(shù)值，那么這個位將是數(shù)字中的最高有效位。類似地，最右邊的位稱為低階位或最低有效位。
To identify individual cells in a computer’s main memory, each cell is assigned a unique “name,” called its address.
為了識別計(jì)算機(jī)主存儲器中的各個單元，給每個單元分配一個唯一的“名稱”，稱為其地址
Because a computer’s main memory is organized as individual, addressable cells, the cells can be accessed independently as required. To reflect the ability to access cells in any order, a computer’s main memory is often called random
access memory (RAM).
This random access feature of main memory is in stark contrast to the mass storage systems that we will discuss in the next section, in which long strings of bits are manipulated as amalgamated blocks.
由于計(jì)算機(jī)的主存儲器是作為單獨(dú)的、可尋址的單元組織起來的，這些單元可以根據(jù)需要獨(dú)立地訪問。為了反映以任何順序訪問單元的能力，計(jì)算機(jī)的主存儲器通常稱為隨機(jī)訪問存儲器(RAM)。主存儲器的這種隨機(jī)訪問特性與我們將在下一節(jié)討論的大容量存儲系統(tǒng)形成了鮮明的對比，在大容量存儲系統(tǒng)中，長串的位元被當(dāng)作合并的塊來處理。
In recognition of this volatility, computer memory constructed from such technology is often called dynamic
memory,
leading to the term
DRAM
(pronounced “DEE–ram”) meaning Dynamic RAM. Or, at times the term SDRAM (pronounced “ES-DEE-ram”), meaning Synchronous DRAM, is used in reference to DRAM that applies additional techniques to decrease the time needed to retrieve the contents from its memory cells.
由于認(rèn)識到這種波動性，由這種技術(shù)構(gòu)建的計(jì)算機(jī)存儲器通常被稱為動態(tài)存儲器，因此DRAM(讀作“DEE-ram”)一詞的意思就是動態(tài)RAM?；蛘?，有時術(shù)語SDRAM(發(fā)音為ES-DEE-ram)，意思是同步DRAM，用于參考DRAM，它應(yīng)用額外的技術(shù)來減少從其存儲單元檢索內(nèi)容所需的時間。
Due to the volatility and limited size of a computer’s main memory, most computers have additional memory devices called mass storage (or secondary storage) systems, including magnetic disks, CDs, DVDs, magnetic tapes, flash drives, and solid-state disks (all of which we will discuss shortly). The advantages of mass storage systems over main memory include less volatility, large storage capacities, low cost, and in many cases, the ability to remove the storage medium from the machine for archival purposes. A major disadvantage of magnetic and optical mass storage systems is that they typically require mechanical motion and therefore require significantly more time to store and retrieve data than a machine’s main memory, where all activities are performed electronically. Moreover, storage systems with moving parts are more prone to mechanical failures than solid state systems.
由于計(jì)算機(jī)主存儲器的易揮發(fā)性和有限的大小，大多數(shù)計(jì)算機(jī)都有稱為大容量存儲(或次要存儲)系統(tǒng)的額外存儲設(shè)備，包括磁盤、cd、dvd、磁帶、閃存驅(qū)動器和固態(tài)磁盤(我們將很快討論所有這些)。與主存儲器相比，大容量存儲系統(tǒng)的優(yōu)點(diǎn)包括更少的波動性、更大的存儲容量、更低的成本，并且在許多情況下，還可以將存儲介質(zhì)從機(jī)器中移除以進(jìn)行歸檔。磁性和光學(xué)海量存儲系統(tǒng)的一個主要缺點(diǎn)是，它們通常需要機(jī)械運(yùn)動，因此需要比機(jī)器主存儲器更多的時間來存儲和檢索數(shù)據(jù)，而在主存儲器中所有的活動都是電子執(zhí)行的。此外，帶有移動部件的存儲系統(tǒng)比固態(tài)系統(tǒng)更容易發(fā)生機(jī)械故障。
The most common example in use today is the magnetic disk
or
hard disk drive
(HDD),
in which a thin spinning disk with magnetic coating is used to hold data (Figure 1.9). Read/write heads are placed above and/or below the disk so that as the disk spins, each head traverses a circle, called a track.
In many cases, a
disk storage system consists of several disks mounted on a common spindle, one
on top of the other, with enough space for the read/write heads to slip between
the platters. In such cases, the read/write heads move in unison. Each time
the read/write heads are
repositioned, a new set of tracks—which is called a
cylinder
—becomes accessible.
今天最常用的例子是磁盤或硬盤驅(qū)動器(HDD)，其中使用一個帶有磁性涂層的薄旋轉(zhuǎn)磁盤來保存數(shù)據(jù)(圖1.9)。讀/寫磁頭放在磁盤的上方和/或下方，這樣當(dāng)磁盤旋轉(zhuǎn)時，每個磁頭穿過一個稱為磁道的圓。在許多情況下，磁盤存儲系統(tǒng)由安裝在一個公共主軸上的多個磁盤組成，一個在另一個上面，有足夠的空間讓讀/寫磁頭在盤片之間滑動。在這種情況下，讀寫頭會一致移動。每次讀取/寫入磁頭被重新定位時，就會有一組新的軌道(稱為圓柱)被訪問。
Since a track can contain more information than we would normally want to manipulate at any one time, each track is divided into small arcs called sectors
on which information is recorded as a continuous string of bits. All sectors on a disk contain the same number of bits (typical capacities are in the range of 512 bytes toa few KB), and in the simplest disk storage systems each track contains the samenumber of sectors. Thus, the bits within a sector on a track near the outer edge of the disk are less compactly stored than those on the tracks near the center, since the outer tracks are longer than the inner ones. In contrast, in high-capacity disk storage systems, the tracks near the outer edge are capable of containing significantly more sectors than those near the center, and this capability is often used by applying a technique called zoned-bit recording. Using zoned-bit recording, several adjacent tracks are collectively known as zones, with a typical disk containing approximately 10 zones. All tracks within a zone have the same number of sectors, but each zone has more sectors per track than the zone inside of it. In this manner, efficient use of the entire disk surface is achieved. Regardless of the details, a disk storage system consists of many individual sectors, each of which can be accessed as an independent string of bits.
由于磁道包含的信息比我們通常想要在任何時候操作的信息都要多，每個磁道被劃分為稱為扇區(qū)的小弧，在扇區(qū)上信息被記錄為一個連續(xù)的比特串。磁盤上的所有扇區(qū)包含相同數(shù)量的位(典型的容量在512字節(jié)到幾KB的范圍內(nèi))，并且在最簡單的磁盤存儲系統(tǒng)中，每個磁道包含相同數(shù)量的扇區(qū)。因此，由于外層磁道比內(nèi)部磁道長，靠近磁盤外緣的磁道上扇區(qū)內(nèi)的位存儲的緊湊程度要低于靠近中心的磁道上的位。相反，在大容量磁盤存儲系統(tǒng)中，靠近外緣的磁道比靠近中心的磁道能夠包含更多的扇區(qū)，這種能力通常通過應(yīng)用一種稱為分區(qū)位記錄的技術(shù)來使用。使用分區(qū)位記錄，幾個相鄰的磁道統(tǒng)稱為分區(qū)，一個典型的磁盤大約包含10個分區(qū)。區(qū)域內(nèi)的所有磁道都有相同數(shù)量的扇區(qū)，但是每個區(qū)域每個磁道的扇區(qū)比其中的區(qū)域多。通過這種方式，可以有效地利用整個磁盤表面。不管細(xì)節(jié)如何，磁盤存儲系統(tǒng)由許多單獨(dú)的扇區(qū)組成，每個扇區(qū)都可以作為一個獨(dú)立的位串訪問。
seek time?：the time required to move the read/write heads from one track to another
尋道時間:將讀寫磁頭從一個磁道移動到另一個磁道所需的時間
rotation delay
or
latency time?：half the time required for the disk to make a complete rotation, which is the average amount of time required for the desired data to rotate around to the read/write head once the head has been positioned over the desired track
旋轉(zhuǎn)延遲或延遲時間:磁盤完成旋轉(zhuǎn)所需時間的一半，即當(dāng)磁頭定位在所需磁道上時，所需數(shù)據(jù)旋轉(zhuǎn)到讀寫磁頭所需的平均時間
access time?：the sum of seek time and rotation delay
訪問時間:尋道時間和旋轉(zhuǎn)時延之和
transfer rate?：the rate at which data can be transferred to or from the disk
傳輸速率:數(shù)據(jù)傳輸?shù)酱疟P或從磁盤傳輸?shù)乃俾?
Note that in the case of zone-bit recording, the amount of data passing a read/write head in a single disk rotation is greater for tracks in an outer zone than for an inner zone, and therefore the data transfer rate varies depending on the portion of the disk being used.
請注意，在zone-bit記錄的情況下，在單個磁盤旋轉(zhuǎn)中通過讀/寫頭的數(shù)據(jù)量在外部區(qū)域的磁道中要大于內(nèi)部區(qū)域，因此數(shù)據(jù)傳輸速率取決于所使用的磁盤部分。
Magnetic storage technologies that are now less widely used include
magnetic
tape,
in which information is recorded on the magnetic coating of a thin plastic tape wound on reels, and floppy disk drives, in which single platters with a magnetic coating are encased in a portable cartridge designed to be readily removed from the drive.
磁存儲技術(shù),現(xiàn)在廣泛使用的包括磁帶、信息記錄在磁層的一層薄薄的塑料帶纏繞在卷,和軟盤驅(qū)動器,單盤與一個磁性涂層是裝在便攜盒設(shè)計(jì)成容易從驅(qū)動器中刪除。
Flash memory technology has the potential of alleviating this drawback. In a flash memory system, bits are stored by sending electronic signals directly to the storage medium where they cause electrons to be trapped in tiny chambers of silicon dioxide, thus altering the characteristics of small electronic circuits. Since these chambers are able to hold their captive electrons for many years without external power, this technology is excellent for portable, nonvolatile data storage.
閃存技術(shù)有可能緩解這一缺點(diǎn)。在閃存系統(tǒng)中，比特是通過直接向存儲介質(zhì)發(fā)送電子信號來存儲的，在存儲介質(zhì)中，電子被困在二氧化硅的小腔中，從而改變了小型電子電路的特性。由于這些腔室能夠在沒有外部電源的情況下保持其捕獲的電子多年，這項(xiàng)技術(shù)非常適合便攜式、非易失性的數(shù)據(jù)存儲。
Flash memory devices called
flash drives, with capacities of hundreds of GBs, are available for general mass storage applications
.閃存設(shè)備稱為閃存驅(qū)動器，具有數(shù)百gb的容量，可用于一般的大容量存儲應(yīng)用。
Larger flash memory devices called
SSDs (solid-state disks)
are explicitly designed to take the place of magnetic hard disks. SSDs compare favorably to hard disks in their resilience to vibrations and physical shock, their quiet operation (due to no moving parts), and their lower access times. SSDs remain more expensive than hard disks of comparable size and thus are still considered a high-end option when buying a computer. SSD sectors suffer from the more limited lifetime of all flash memory technologies, but the use of wear-leveling techniques can reduce the impact of this by relocating frequently altered data blocks to fresh locations on the drive.?
被稱為ssd(固態(tài)硬盤)的更大的閃存設(shè)備被明確地設(shè)計(jì)來取代磁碟。與硬盤相比，ssd在抗振動和物理沖擊方面更有優(yōu)勢，其操作安靜(由于沒有移動部件)，以及更低的訪問時間。ssd仍然比同等大小的硬盤更貴，因此在購買計(jì)算機(jī)時仍被視為高端選擇。SSD扇區(qū)的壽命比所有閃存技術(shù)都要短，但是使用磨損均衡技術(shù)可以通過將頻繁更改的數(shù)據(jù)塊重新定位到驅(qū)動器上的新位置來減少這種影響
Another application of flash technology is found in
SD (Secure Digital)
memory cards
(or just SD Card). These provide up to two GBs of storage and are packaged in a plastic rigged wafer about the size a postage stamp (SD cards are also available in smaller mini and micro sizes), SDHC (High Capacity)
memory cards can provide up to 32 GBs and the next generation SDXC (Extended Capac
ity) memory cards may exceed a TB.
閃存技術(shù)的另一個應(yīng)用是在SD(安全數(shù)字)存儲卡(或僅僅是SD卡)中。這些提供2 gb的存儲和打包在一個塑料操縱晶片大小郵票(SD卡也可以在較小的小型和微型大小),SDHC記憶卡(大容量)可以提供32 GBs和下一代SDXC(擴(kuò)展能力)記憶卡可能超過一個結(jié)核病。
?binary system
one’s complement notation:如果是正整數(shù)，為原二進(jìn)制碼。如果是負(fù)整數(shù)，將二進(jìn)制數(shù)反轉(zhuǎn)（包括符號位），得到的數(shù)即為原二進(jìn)制的一的補(bǔ)數(shù)（ones' complement）。若某一位為0，則使其變?yōu)?，反之亦然。
two’s complement notation:如果是正數(shù)， 補(bǔ)碼與原碼一樣。如果是負(fù)數(shù)，在反碼的基礎(chǔ)上+1。
excess notation:2的n-1次方+原數(shù)(與two’s complement notation就符號位相反)
floating-point notation:sign bite(符號位)+exponent（用excess notation表示，
正數(shù):將基數(shù)向右移動；
負(fù)數(shù):將基數(shù)向左移動
）+mantissa（如果超出要去除lsm——最后一位）
One means of representing an image is to interpret the image as a collection of dots, each of which is called a pixel, short for “picture element.” The appearance of each pixel is then encoded and the entire image is represented as a collection of these encoded pixels. Such a collection is called a bit map.
表示圖像的一種方法是將圖像解釋為點(diǎn)的集合，每個點(diǎn)稱為像素，即“圖像元素”的縮寫。然后對每個像素的外觀進(jìn)行編碼，并將整個圖像表示為這些編碼像素的集合。這樣的集合稱為位圖。
For the purpose of storing or transferring data, it is often helpful (and sometimes mandatory) to reduce the size of the data involved while retaining the underlying information. The technique for accomplishing this is called data compression.
為了存儲或傳輸數(shù)據(jù)，在保留基礎(chǔ)信息的同時減少所涉及的數(shù)據(jù)的大小通常是有幫助的(有時是強(qiáng)制性的)。實(shí)現(xiàn)這一點(diǎn)的技術(shù)稱為數(shù)據(jù)壓縮。
In cases where the data being compressed consist of long sequences of the same value, the compression technique called run-length encoding,
which is a lossless method, is popular.
在被壓縮的數(shù)據(jù)由相同值的長序列組成的情況下，稱為游程編碼的壓縮技術(shù)是一種無損方法，它很受歡迎。
The parity system just described is called odd parity, because we designed our system so that each correct pattern contains an odd number of 1s. Another technique is called even parity.
剛才描述的奇偶校驗(yàn)系統(tǒng)被稱為奇偶校驗(yàn)，因?yàn)槲覀冊O(shè)計(jì)的系統(tǒng)使每個正確的圖案包含一個奇數(shù)個1。另一種技術(shù)叫做偶奇偶校驗(yàn)。
chapter2
The circuitry in a computer that controls the manipulation of data is called the
central processing unit,
or
CPU (often referred to as merely the processor).
計(jì)算機(jī)中控制數(shù)據(jù)操作的電路稱為中央處理單元(central processing unit，簡稱CPU)(通常簡稱處理器)。
The CPUs found in today’s desktop computers and notebooks are packaged as small flat squares (approximately two inches by two inches) whose connecting pins plug into a socket mounted on the machine’s main circuit board (called the motherboard). In smartphones, mini-notebooks, and other Mobile Internet Devices (MID), CPUs are around half the size of a postage stamp. Due to their small size, these processors are called microprocessors.
今天的臺式電腦和筆記本電腦中的cpu被包裝成正方形(大約2英寸乘2英寸)，其連接引腳插入安裝在機(jī)器主電路板(稱為主板)上的插座。在智能手機(jī)、迷你筆記本電腦和其他移動互聯(lián)網(wǎng)設(shè)備(MID)中，cpu大約只有郵票的一半大小。由于體積小，這些處理器被稱為微處理器。
A CPU consists of three parts:the
arithmetic/logic unit,
which contains the circuitry that performs operations on data (such as addition and subtraction); the control unit,
which contains the circuitry for coordinating the machine’s activities; and the register unit,
which contains data storage cells (similar to main memory cells), called registers, that are used for temporary storage of information within the CPU.
CPU由三部分組成:算術(shù)/邏輯單元，它包含對數(shù)據(jù)進(jìn)行運(yùn)算(如加減)的電路;控制單元，包含協(xié)調(diào)機(jī)器活動的電路;和寄存器單元，它包含數(shù)據(jù)存儲單元(類似于主存儲器單元)，稱為寄存器，用于在CPU內(nèi)臨時存儲信息。
Some of the registers within the register unit are considered
general-purpose
registers,
whereas others are special-purpose registers.
寄存器單元內(nèi)的一些寄存器被認(rèn)為是通用寄存器，而另一些則是專用寄存器。
For the purpose of transferring bit patterns, a machine’s CPU and main memory are connected by a collection of wires called a bus.
為了傳輸位模式，機(jī)器的CPU和主存儲器由一組稱為總線的導(dǎo)線連接起來
The idea of storing a computer’s program in its main memory is called the stored-program concept and has become the standard approach used today—so standard, in fact, that it seems obvious.
把計(jì)算機(jī)程序存儲在主存儲器中的想法被稱為存儲程序的概念，它已經(jīng)成為今天使用的標(biāo)準(zhǔn)方法——事實(shí)上，它是如此的標(biāo)準(zhǔn)，以至于看起來是顯而易見的。
This collection of instructions along with the encoding system is called the machine language.
An instruction expressed in this language is called a machine-level instruction or, more commonly, a machine instruction.
這種指令集合連同編碼系統(tǒng)被稱為機(jī)器語言。用這種語言表示的指令稱為機(jī)器級指令，或者更常見的是機(jī)器指令。
Reduced instruction set computer (RISC) is that a CPU should be designed to execute a minimal set of machine instructions.?The argument in favor of RISC architecture is that such a machine is efficient, fast, and less expensive to manufacture.
精簡指令集計(jì)算機(jī)(RISC)是指CPU應(yīng)該被設(shè)計(jì)用來執(zhí)行最小的機(jī)器指令集。支持RISC架構(gòu)的論點(diǎn)是，這樣的機(jī)器是高效的，快速的，而且制造成本更低。
Others argue in favor of CPUs with the ability to execute a large number of complex instructions, even though many of them are technically redundant. The result of this approach is known as a complex instruction set computer (CISC).
另一些人則認(rèn)為cpu應(yīng)該具備執(zhí)行大量復(fù)雜指令的能力，盡管從技術(shù)上講，許多指令是多余的。這種方法的結(jié)果被稱為復(fù)雜指令集計(jì)算機(jī)(CISC)。
An important group of instructions within the data transfer category consists of the commands for communicating with devices outside the CPU-main memory context (printers, keyboards, display screens, disk drives, etc.). Since these instructions handle the input/output (I/O) activities of the machine, they are called I/O instructions and are sometimes considered as a category in their own right.?
數(shù)據(jù)傳輸類中的一組重要指令由用于與cpu -主存上下文之外的設(shè)備(打印機(jī)、鍵盤、顯示屏、磁盤驅(qū)動器等)通信的命令組成。因?yàn)檫@些指令處理機(jī)器的輸入/輸出(I/O)活動，所以它們被稱為I/O指令，有時被認(rèn)為是它們自己的一類。
To understand how the overall execution process takes place, it is necessary to consider two of the special purpose registers within the CPU: the instruction
register
and the program counter.
為了理解整個執(zhí)行過程是如何發(fā)生的，有必要考慮CPU中兩個特殊用途的寄存器:指令寄存器和程序計(jì)數(shù)器。
The CPU performs its job by continually repeating an algorithm that guides it through a three-step process known as the machine cycle.
CPU通過不斷重復(fù)一個算法來完成它的工作，這個算法通過一個被稱為機(jī)器周期的三步過程來指導(dǎo)它。
Technologies to increase
throughput:
提高輸出量的技術(shù):
Pipelining: Overlap steps of the machine cycle
流水線:機(jī)器循環(huán)的重疊步驟
Parallel Processing
: Use multiple processors simultaneously
并行處理:同時使用多個處理器
?
SISD (single-instruction stream, single-data stream)→ No parallel processing
SISD(單指令流，單數(shù)據(jù)流)→沒有并行處理
?
MIMD (Multiple-instruction stream, Multiple-data stream)→ Different programs, different data
MIMD(多指令流，多數(shù)據(jù)流)→ 不同的程序，不同的數(shù)據(jù)
?
SIMD (single-instruction stream, Multiple-data stream)→ Same program, different data
SIMD(單指令流，多數(shù)據(jù)流)→同一個程序，不同的數(shù)據(jù)
chapter3
The execution of each program, called a job, was handled as an isolated activity—the machine was prepared for executing the program, the program was executed, and then all the tapes, punched cards, etc. had to be retrieved before the next program preparation could begin.
每個程序的執(zhí)行，稱為一個作業(yè)，被作為一個獨(dú)立的活動處理——機(jī)器為執(zhí)行程序做好了準(zhǔn)備，程序被執(zhí)行，然后所有的磁帶、穿孔卡片等，必須在開始下一個程序準(zhǔn)備之前取回。
This was the beginning of
batch processing—the execution of jobs by collecting them in a single batch, then executing them without further interaction with the user.
這是批處理的開始——通過將作業(yè)收集到單個批處理中來執(zhí)行作業(yè)，然后在不與用戶進(jìn)行進(jìn)一步交互的情況下執(zhí)行它們。
One early development was the separation of users and equipment, which eliminated the physical transition of people in and out of the computer room. For this purpose a computer operator was hired to operate the machine. Anyone wanting a program run was required to submit it, along with any required data and special directions about the program’s requirements, to the operator and return later for the results. The operator, in turn, loaded these materials into the machine’s mass storage where a program called the operating system could read and execute them one at a time. This was the beginning of batch processing—the execution of jobs by collecting them in a single batch, then executing them without further interaction with the user.
一個早期的發(fā)展是用戶和設(shè)備的分離，這消除了人進(jìn)出計(jì)算機(jī)房間的物理轉(zhuǎn)換。為此，雇了一個電腦操作員來操作這臺機(jī)器。任何想要運(yùn)行程序的人都需要將程序提交給操作人員，連同任何所需的數(shù)據(jù)和關(guān)于程序要求的特殊說明，然后返回結(jié)果。接著，操作員將這些材料裝入機(jī)器的大容量存儲器中，一個稱為操作系統(tǒng)的程序可以一次讀取并執(zhí)行它們。這是批處理的開始——通過將作業(yè)收集到單個批處理中來執(zhí)行作業(yè)，然后在不與用戶進(jìn)行進(jìn)一步交互的情況下執(zhí)行它們。
A
queue
is a storage organization in which objects (in this case, jobs) are ordered in first-in, first-out (abbreviated FIFO and pronounced “FI-foe”) fashion.
隊(duì)列是一種存儲組織，其中對象(在本例中是作業(yè))按照先進(jìn)先出(縮寫為FIFO，發(fā)音為“FI-foe”)的方式進(jìn)行排序。
To accommodate these needs, new operating systems were developed that allowed a program being executed to carry on a dialogue with the user through remote terminals—a feature known as interactive processing.
為了滿足這些需求，新的操作系統(tǒng)被開發(fā)出來，允許一個正在執(zhí)行的程序通過遠(yuǎn)程終端與用戶進(jìn)行對話，這種特性被稱為交互處理。
In a sense, the computer is forced to execute tasks under a deadline, a process that became known as real-time processing in which the actions performed are said to occur in real-time.
從某種意義上說，計(jì)算機(jī)被迫在一個期限內(nèi)執(zhí)行任務(wù)，這個過程后來被稱為實(shí)時處理，在這個過程中，所執(zhí)行的操作被稱為實(shí)時發(fā)生的。
The solution to this problem was to design operating systems that provided service to multiple users at the same time: a feature called time-sharing. One means of implementing time-sharing is to apply the technique called
multiprogramming in which time is divided into intervals and then the execution of each job is restricted to only one interval at a time. At the end of each interval, the current job is temporarily set aside and another is allowed to execute during the next interval. By rapidly shuffling the jobs back and forth in this manner, the illusion of several jobs executing simultaneously is created. Depending on the types of jobs being executed, early time-sharing systems were able to provide acceptable real-time processing to as many as 30 users simultaneously. Today, multiprogramming techniques are used in single-user as well as multiuser systems, although in the former the result is usually called multitasking. That is, time-sharing refers to multiple users sharing access to a common computer, whereas multitasking refers to one user executing numerous tasks simultaneously.
這個問題的解決方案是設(shè)計(jì)能夠同時為多個用戶提供服務(wù)的操作系統(tǒng):這一特性被稱為分時。實(shí)現(xiàn)分時的一種方法是應(yīng)用稱為多道程序設(shè)計(jì)的技術(shù)，在這種技術(shù)中，時間被劃分為多個間隔，然后每個作業(yè)的執(zhí)行被限制在一個時間間隔內(nèi)。在每個間隔結(jié)束時，當(dāng)前作業(yè)將被暫時擱置，并允許在下一個間隔期間執(zhí)行另一個作業(yè)。通過以這種方式快速地來回移動作業(yè)，就會產(chǎn)生多個作業(yè)同時執(zhí)行的錯覺。根據(jù)正在執(zhí)行的作業(yè)的類型，早期的分時系統(tǒng)能夠同時為多達(dá)30個用戶提供可接受的實(shí)時處理。今天，多程序設(shè)計(jì)技術(shù)被用于單用戶和多用戶系統(tǒng)，盡管前者的結(jié)果通常被稱為多任務(wù)處理。也就是說，分時指的是多個用戶共享對一臺普通計(jì)算機(jī)的訪問，而多任務(wù)處理指的是一個用戶同時執(zhí)行多個任務(wù)。
The development of multiprocessor machines has led to operating systems that provide time-sharing/ multitasking capabilities by assigning different tasks to different processors as well as by sharing the time of each single processor. These operating systems must wrestle with such problems as load balancing (dynamically allocating tasks to the various processors so that all processors are used efficiently) as well as scaling (breaking tasks into a number of subtasks compatible with the number of processors available).
多處理器機(jī)器的發(fā)展使得操作系統(tǒng)通過將不同的任務(wù)分配給不同的處理器以及共享每個處理器的時間來提供分時/多任務(wù)處理能力。這些操作系統(tǒng)必須處理負(fù)載平衡(將任務(wù)動態(tài)分配給各種處理器，以便有效地使用所有處理器)和可伸縮性(將任務(wù)分解為與可用處理器數(shù)量相匹配的許多子任務(wù))等問題。
Still another direction of research in operating systems focuses on devices that are dedicated to specific tasks such as medical devices, vehicle electronics, home appliances, cell phones, or other hand-held computers. The computer systems found in these devices are known as embedded systems.
操作系統(tǒng)的另一個研究方向是專注于用于特定任務(wù)的設(shè)備，如醫(yī)療設(shè)備、車輛電子設(shè)備、家用電器、手機(jī)或其他手持電腦。在這些設(shè)備中發(fā)現(xiàn)的計(jì)算機(jī)系統(tǒng)被稱為嵌入式系統(tǒng)。
Application software consists of the programs for performing tasks particular to the machine’s utilization. A machine used to maintain the inventory for a manufacturing company will contain different application software from that found on a machine used by an electrical engineer. Examples of application software include spreadsheets, database systems, desktop publishing systems, accounting systems, program development software, and games.
應(yīng)用軟件由執(zhí)行與機(jī)器利用率有關(guān)的特定任務(wù)的程序組成。制造公司用于維護(hù)庫存的機(jī)器將包含不同于電氣工程師使用的機(jī)器上的應(yīng)用軟件。應(yīng)用軟件的例子包括電子表格、數(shù)據(jù)庫系統(tǒng)、桌面出版系統(tǒng)、會計(jì)系統(tǒng)、程序開發(fā)軟件和游戲。
In contrast to application software, system software performs those tasks that are common to computer systems in general. In a sense, the system software provides the infrastructure that the application software requires, in much the same manner as a nation’s infrastructure (government, roads, utilities, financial institutions, etc.) provides the foundation on which its citizens rely for their individual lifestyles.
與應(yīng)用軟件相比，系統(tǒng)軟件執(zhí)行的任務(wù)通常是計(jì)算機(jī)系統(tǒng)所共有的。在某種意義上，系統(tǒng)軟件提供了應(yīng)用軟件所需的基礎(chǔ)設(shè)施，就像一個國家的基礎(chǔ)設(shè)施(政府、道路、公用事業(yè)、金融機(jī)構(gòu)等)為其公民的個人生活方式提供基礎(chǔ)一樣。
In order to perform the actions requested by the computer’s users, an operating system must be able to communicate with those users. The portion of an operating system that handles this communication is often called the user interface.
為了執(zhí)行計(jì)算機(jī)用戶所要求的操作，操作系統(tǒng)必須能夠與這些用戶進(jìn)行通信。操作系統(tǒng)中處理這種通信的部分通常稱為用戶界面。
Older user interfaces,called?shells,communicated with users through textual messages using a keyboard and monitor screen.
舊的用戶界面稱為shell，通過鍵盤和顯示器屏幕通過文本消息與用戶通信。
More modern systems perform this task by means of a graphical user interface (GUI—pronounced “GOO–ee”) in which objects to be manipulated, such as files and programs, are represented pictorially on the display as icons.
更現(xiàn)代的系統(tǒng)通過圖形用戶界面(gui -發(fā)音為“gooe - ee”)來執(zhí)行這項(xiàng)任務(wù)，在圖形用戶界面中，要操作的對象，如文件和程序，在顯示器上以圖形化的圖標(biāo)表示。
An important component within today’s GUI shells is the window manager, which allocates blocks of space on the screen, called windows, and keeps track of which application is associated with each window.
今天GUI shell中的一個重要組件是窗口管理器，它在屏幕上分配稱為窗口的空間塊，并跟蹤哪個應(yīng)用程序與每個窗口相關(guān)聯(lián)。
In contrast to an operating system’s user interface, the internal part of an operating system is called the kernel.
An operating system’s kernel contains those software components that perform the very basic functions required by the computer installation. One such unit is the file manager,
whose job is to coordinate the use of the machine’s mass storage facilities. More precisely, the filemanager maintains records of all the files stored in mass storage, including whereeach file is located, which users are allowed to access the various files, and which portions of mass storage are available for new files or extensions to existing files. These records are kept on the individual storage medium containing the related files so that each time the medium is placed online, the file manager can retrieve them and thus know what is stored on that particular medium.
與操作系統(tǒng)的用戶界面相比，操作系統(tǒng)的內(nèi)部部分稱為內(nèi)核。操作系統(tǒng)的內(nèi)核包含那些執(zhí)行計(jì)算機(jī)安裝所需要的基本功能的軟件組件。其中一個這樣的單元是文件管理器，它的工作是協(xié)調(diào)機(jī)器的大量存儲設(shè)施的使用。更準(zhǔn)確地說，file manager維護(hù)存儲在大容量存儲中的所有文件的記錄，包括每個文件的位置、允許哪些用戶訪問各種文件，以及大容量存儲中的哪些部分可用于新文件或現(xiàn)有文件的擴(kuò)展名。這些記錄保存在包含相關(guān)文件的單個存儲媒體上，因此每次將媒體置于在線狀態(tài)時，文件管理器就可以檢索它們，從而知道在該特定媒體上存儲了什么。
For the convenience of the machine’s users, most file managers allow files to be grouped into a bundle called a directory
or
folder. This approach allows a user to organize his or her files according to their purposes by placing related files in the same directory. Moreover, by allowing directories to contain other directories, called subdirectories, a hierarchical organization can be constructed.
為了方便計(jì)算機(jī)用戶，大多數(shù)文件管理器允許將文件分組到一個稱為目錄或文件夾的包中。通過將相關(guān)文件放置在相同的目錄中，用戶可以根據(jù)文件的目的來組織文件。此外，通過允許目錄包含其他目錄(稱為子目錄)，可以構(gòu)建層次結(jié)構(gòu)組織。
A chain of directories within directories is called a
directory path. Paths are often expressed by listing the directories along the path separated by slashes.
目錄中的目錄鏈稱為目錄路徑。路徑通常是沿著用斜杠分隔的路徑列出目錄。
Another component of the kernel consists of a collection of
device drivers, which are the software units that communicate with the controllers (or at times, directly with peripheral devices) to carry out operations on the peripheral devices attached to the machine. Each device driver is uniquely designed for its particular type of device (such as a printer, disk drive, or monitor) and translates generic requests into the more technical steps required by the device assigned to that driver.
內(nèi)核的另一個組件由一組設(shè)備驅(qū)動程序組成，這些驅(qū)動程序是與控制器(有時是直接與外圍設(shè)備)通信的軟件單元，用于對附加到機(jī)器上的外圍設(shè)備進(jìn)行操作。每個設(shè)備驅(qū)動程序都是為其特定類型的設(shè)備(如打印機(jī)、磁盤驅(qū)動器或監(jiān)視器)設(shè)計(jì)的，并將通用請求轉(zhuǎn)換為分配給該驅(qū)動程序的設(shè)備所需的更技術(shù)性的步驟。
Still another component of an operating system’s kernel is the
memory
manager,
which is charged with the task of coordinating the machine’s use of main memory.The task of the memory manager is complicated further when the total main memory space required exceeds the space actually available in the computer. In this case the memory manager may create the illusion of additional memory space by rotating programs and data back and forth between main memory and mass storage (a technique called paging
). Suppose, for example, that a main memory of 8GB is required but the computer only has 4GB. To create the illusion of the larger memory space, the memory manager reserves 4GB of storage space on a magnetic disk. There it records the bit patterns that would be stored in main memory if main memory had an actual capacity of 8GB. This data is divided into uniform sized units called pages,
which are typically a few KB in size. Then the memory manager shuffles these pages back and forth between main memory and mass storage so that the pages that are needed at any given time are actually present in the 4GB of main memory. The result is that the computer is able to function as though it actually had 8GB of main memory. This large “fictional” memory space created by paging is called virtual memory.
操作系統(tǒng)內(nèi)核的另一個組件是內(nèi)存管理器，它負(fù)責(zé)協(xié)調(diào)機(jī)器主內(nèi)存的使用。當(dāng)所需的總主存空間超過計(jì)算機(jī)中實(shí)際可用的空間時，內(nèi)存管理器的任務(wù)就更加復(fù)雜了。在這種情況下，內(nèi)存管理器可以通過在主存和大容量存儲之間來回旋轉(zhuǎn)程序和數(shù)據(jù)(一種稱為分頁的技術(shù))來創(chuàng)建額外內(nèi)存空間的錯覺。例如，假設(shè)需要8GB的主存，但計(jì)算機(jī)只有4GB。為了創(chuàng)建更大內(nèi)存空間的假象，內(nèi)存管理器在磁盤上保留4GB的存儲空間。如果主存的實(shí)際容量為8GB，它會在那里記錄將存儲在主存中的位模式。這些數(shù)據(jù)被劃分為大小一致的單位，稱為頁面，其大小通常為幾KB。然后，內(nèi)存管理器在主存和大容量存儲之間來回切換這些頁面，以便在任何給定時間需要的頁面實(shí)際上都存在于4GB的主存中。其結(jié)果是，這臺計(jì)算機(jī)可以像它實(shí)際上有8GB主存一樣工作。由分頁創(chuàng)建的這個巨大的“虛構(gòu)”內(nèi)存空間稱為虛擬內(nèi)存。
Two additional components within the kernel of an operating system are the scheduler
and
dispatcher, which we will study in the next section. For now we merely note that in a multiprogramming system the scheduler determines which activities are to be considered for execution, and the dispatcher controls the allocation of time to these activities.
操作系統(tǒng)內(nèi)核中的另外兩個組件是調(diào)度器和調(diào)度器，我們將在下一節(jié)中研究這兩個組件?，F(xiàn)在我們只注意到，在多道程序系統(tǒng)中，調(diào)度器決定哪些活動要考慮執(zhí)行，而調(diào)度器控制這些活動的時間分配。
boot strapping
(often shortened to
booting
)? is performed by a computer each time it is turned on.
引導(dǎo)捆綁(通?？s短為引導(dǎo))是由計(jì)算機(jī)每次打開時執(zhí)行的。
To resolve this dilemma, a small portion of a computer’s main memory where the CPU expects to find its initial program is constructed from special nonvolatile memory cells. Such memory is known as read-only memory (ROM) because its contents can be read but not altered.
為了解決這個難題，計(jì)算機(jī)主存的一小部分由特殊的非易失性存儲單元構(gòu)造而成，中央處理器希望在這里找到它的初始程序。這種存儲器被稱為只讀存儲器(ROM)，因?yàn)樗膬?nèi)容可以讀取，但不能更改。
In a general-purpose computer, a program called the
boot loader is permanently stored in the machine’s ROM.
在通用計(jì)算機(jī)中，一個稱為引導(dǎo)加載程序的程序永久地存儲在計(jì)算機(jī)的ROM中。
The overall process of executing the boot loader and thus starting the operating system is called booting the computer.
執(zhí)行引導(dǎo)加載程序從而啟動操作系統(tǒng)的整個過程稱為啟動計(jì)算機(jī)。
The activity of executing a program under the control of the operating system is known as a process. Associated with a process is the current status of the activity, called the process
state.
在操作系統(tǒng)的控制下執(zhí)行程序的活動稱為過程。與流程相關(guān)聯(lián)的是活動的當(dāng)前狀態(tài)，稱為流程
狀態(tài)。
To keep track of all the processes, the scheduler maintains a block of information in main memory called the process table.
為了跟蹤所有進(jìn)程，調(diào)度器在主內(nèi)存中維護(hù)一個稱為進(jìn)程表的信息塊。
Scheduler ：1.Allows multiple processes to be loaded into executable memory at a time and the loaded process shares CPU (time sharing). 2.Maintains a record of processes present. 3.Adds new processes to the process table and removes completed processes from the process table.調(diào)度程序:1。允許多個進(jìn)程一次加載到可執(zhí)行內(nèi)存中，加載的進(jìn)程共享CPU(時間共享)。2.?維護(hù)當(dāng)前進(jìn)程的記錄。3.向進(jìn)程表中添加新進(jìn)程，并從進(jìn)程表中刪除已完成的進(jìn)程。
Dispatcher :1.Oversees the execution of scheduled processes.2.Controls the allocation of time slices
to the processes in the process table. 3.The end of a time slice is signaled by an?interrupt.
調(diào)度員:1。監(jiān)督計(jì)劃流程的執(zhí)行。控制將時間片分配給進(jìn)程表中的進(jìn)程。3.一個時間片的結(jié)束以一個中斷作為信號。
Each process occupies CPU for a short period of time (
a few tens of ms) .Time period is called time slice.Multiprogramming between process A and B.Process switch (or context switch).Changing one process to another
每個進(jìn)程占用一小段時間(幾十毫秒)，這段時間稱為時間片。進(jìn)程A和進(jìn)程b之間的多程序設(shè)計(jì)。進(jìn)程切換(或上下文切換)。將一個進(jìn)程更改為另一個進(jìn)程
The solution to this problem is to insist that the task of testing and possibly setting the flag be completed without interruption. One approach is to use the interrupt disable and interrupt enable instructions provided in most machine languages. When executed, an interrupt disable instruction causes future interrupts to be blocked, whereas an interrupt enable instruction causes the CPU to resume responding to interrupt signals. Thus, if the operating system starts the flag-testing routine with a disable interrupt instruction and ends it with an enable interrupt instruction, no other activity can interrupt the routine once it starts.Another approach is to use the test-and-set instruction that is available inmany machine languages. This instruction directs the CPU to retrieve the value of a flag, note the value received, and then set the flag—all within a single machine instruction. The advantage here is that because the CPU always completes an instruction before recognizing an interrupt, the task of testing and setting the flag cannot be split when it is implemented as a single instruction.
這個問題的解決方案是堅(jiān)持測試和可能設(shè)置標(biāo)志的任務(wù)必須不中斷地完成。一種方法是使用大多數(shù)機(jī)器語言中提供的中斷禁用和中斷啟用指令。當(dāng)中斷執(zhí)行時，interrupt disable指令會導(dǎo)致以后的中斷被阻塞，而interrupt enable指令會導(dǎo)致CPU恢復(fù)響應(yīng)中斷信號。因此，如果操作系統(tǒng)用一個禁用的中斷指令啟動標(biāo)志測試?yán)?，并以一個啟用的中斷指令結(jié)束它，那么一旦例程啟動，其他任何活動都不能中斷它。另一種方法是使用在許多機(jī)器語言中可用的測試和設(shè)置指令。這條指令指示CPU檢索一個標(biāo)志的值，記錄接收到的值，然后設(shè)置該標(biāo)志——所有這些都在一條機(jī)器指令中。這樣做的好處是，因?yàn)镃PU總是在識別到一個中斷之前完成一條指令，所以測試和設(shè)置標(biāo)志的任務(wù)不能被拆分，當(dāng)它被實(shí)現(xiàn)為一個單獨(dú)的指令時。
A properly implemented flag, as just described, is called a
semaphore, in reference to the railroad signals used to control access to sections of track.
正如前面所描述的，一個被正確實(shí)現(xiàn)的標(biāo)志被稱為信號燈，它指的是用來控制進(jìn)入軌道部分的鐵路信號。
Corresponding to the section of track that can contain only
one train at a time is a sequence of instructions that should be executed by only
one process at a time. Such a sequence of instructions is called a critical region.
與在同一時間只能包含一列火車的軌道部分相對應(yīng)的是一個指令序列，在同一時間只能由一個進(jìn)程執(zhí)行。這樣的指令序列稱為臨界區(qū)。
The requirement that only one process at a time be allowed to execute a critical region is known as mutual exclusion.
一次只允許一個進(jìn)程執(zhí)行臨界區(qū)域的要求稱為互斥。
Another problem that can arise during resource allocation is deadlock, the condition in which two or more processes are blocked from progressing because each is waiting for a resource that is allocated to another.
在資源分配期間可能出現(xiàn)的另一個問題是死鎖，即兩個或多個進(jìn)程因等待分配給另一個進(jìn)程的資源而被阻塞。
This technique of holding data for output at a later but more convenient time is called spooling.
這種保存數(shù)據(jù)以便在以后更方便的時候輸出的技術(shù)稱為假脫機(jī)。
chapter4
chapter5
Algorithmic operations
?
Ordered (first instruction, second instruction, etc.)
?
Able to alter the order of its instructions. (
→
control structure)
Three Categories of Algorithmic Operations:
?
Sequential
operations: instructions are executed in order
順序操作:指令按順序執(zhí)行
?
Conditional operations: asks true/false question and then selects the next instruction based on the answer
條件操作:詢問正誤問題，然后根據(jù)答案選擇下一條指令
?
Iterative
operations (loops): repeats the execution of a block of instructions
迭代操作(循環(huán)):重復(fù)執(zhí)行一個指令塊
Pseudo-Code (or Program Design Language)
?
Informal way to express the design of a computer program or an algorithm
1.Consists of
natural language-like statements that precisely describe the steps of an algorithm or program
由類似于自然語言的語句組成，這些語句精確地描述了算法或程序的步驟
2.
Statements describe actions
語句描述操作
3.?
Focuses on the
logic of the algorithm or program
重點(diǎn)討論算法或程序的邏輯
4.?
Avoids language-specific elements
避免特定于語言的元素
5.?
Written at a level so that the desired programming code can be generated almost automatically from each statement (i.e., easy to translate statement
→
programming code
)
編寫在一個級別上，以便可以從每個語句自動生成所需的編程代碼(例如，易于翻譯的語句→編程代碼)
6.?
Steps
are numbered. Subordinate numbers and/or
indentation are used for dependent statements in selection and repetition structures
步驟已經(jīng)屈指可數(shù)了。在選擇和重復(fù)結(jié)構(gòu)中，從屬數(shù)和/或縮進(jìn)用于從屬語句
example：
?
?
Binary Search Algorithm
way to use fuction
?Algorithm Efficiency
Big theta
notation: Used to represent efficiency classes
Example:
Sequential search
is in
Θ
(n)
????????????????Insertion sort
is in
Θ
(n
2
)
????????????????Binary search
is in
Θ
(log
2
n)
Best, worst, and average case analysis
Insertion sort in a worst-case situation
Proof of correctness
?
Assertions:
true-false statement placed in a program to assert that it is true at that point
在一個程序中,錯誤的語句斷言它在這一點(diǎn)上是正確的
?
Preconditions:
assertion placed before a statement.True before the execution of the algorithm
在語句前放置的斷言。在算法執(zhí)行之前
?
Postconditions
: assertion placed after a statement .True after the execution of the algorithm
在語句后放置的斷言。在算法執(zhí)行之后
?
Loop invariant
: assertion supposed to be true before and after each iteration of the loop
在循環(huán)的每次迭代前后都應(yīng)該是正確的
?
An assertion must specify the desired output of the algorithm.
斷言必須指定算法的預(yù)期輸出。
?
If
, given the preconditions, each identified
assertion is true
when the execution reaches that particular point, then the algorithm is
correct
如果考慮到先決條件,當(dāng)執(zhí)行到達(dá)該特定的點(diǎn)時,每個確定的斷言是正確的,那么算法是正確的
chapter6
chapter7
chapter8
Basic Data Structures
Array:
A block of data whose entries are of
same type
?
A two
dimensional
array consists for rows and columns
?
Indices
are used to identify positions
?
A
two-dimensional array
with two rows and nine columns
Aggregate
: A block of data items that might be of
different type or sizes
?
Each data item is called a
field
?
Fields are usually accessed by name
List
: A collection of data whose entries are arranged sequentially
?
Head
: The beginning of the list
?
Tail
: The end of the list
Tree:
A collection of data whose entries have a hierarchical organization
?
Node:
An entry in a tree
?
Root node:
The node at the top
?
Terminal
(or
leaf
)
node:
A node at the bottom
?
Parent
: The node immediately above a specified node
?
Child
: A node immediately below a specified node
?
Ancestor
: Parent, parent of parent, etc.
?
Descendent
: Child, child of child, etc.
?
Siblings: Nodes sharing a common parent
?data structures
Stack
: A list in which entries are removed and inserted only at the
head
?
LIFO
: Last-in-first-out
?
Top
: The head of list (stack)
?
Bottom
or base: The tail of list (stack)
?
Pop
: To remove the entry at the top
?
Push
: To insert an entry at the top
Queue
: A list in which entries are removed at the head and are inserted at the tail
?
FIFO
: First-in-first-out
Related Concepts
Abstraction
?
Shield
users
(application software) from details of actual data storage
從實(shí)際數(shù)據(jù)存儲的細(xì)節(jié)中,保護(hù)用戶(應(yīng)用軟件)
Static vs. Dynamic Structure
?
Does the shape and size change over time?
隨著時間的推移,形狀和大小會改變嗎?
Pointer
?
A storage area that encodes an address where data is stored
一個存儲區(qū)域,它編碼一個數(shù)據(jù)存儲的地址
?
Later used to access the data
后來使用的用于訪問數(shù)據(jù)
Storing Arrays
?
?
文章來源：http://www.zghlxwxcb.cn/news/detail-456144.html
?
文章來源地址http://www.zghlxwxcb.cn/news/detail-456144.html
到了這里，關(guān)于計(jì)算機(jī)系統(tǒng)概論基本知識的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
