Write an immortal legend

At the end of the PA, let's do something fun.

Showcasing your computer system

Currently, Nanos-lite can run up to four processes simultaneously. We can utilize all four processes effectively. Specifically, we can load "仙剑奇侠传", "Flappy Bird", "NSlider", and "hello" programs. We can maintain the current foreground program through a variable called fg_pcb, enabling the foreground program and the "hello" program to run alternately. In detail, within the events_read() function of Nanos-lite, we can bind the keys F1, F2, and F3 to three foreground programs. For example, at the beginning, "仙剑奇侠传" and the "hello" program can run alternately. After pressing F2, it switches to "Flappy Bird" and the "hello" program running alternately.

Moreover, you can also load three startup menu programs or NTerm. With VME support, they can be switched freely, just like playing three NES games simultaneously. It's pretty cool!

Showcase your computer system

Add foreground programs and their switching functionality to showcase your personally created computer system.

run ONScripter simulator

Try in the new branch

The following are optional tasks and may introduce incompatible changes to the mandatory parts, if you wish to explore these contents, please create a new branch and make the code modifications there.

ONScripter is an open-source NScripter script engine which could be used to run text adventure games written in coresponding script. we cloned the project from [this repo][onscripter github] and ported it to Navy. Running make init in the navy-apps/apps/onscripter/ directory will clone the ported project from github. The ported project can still run on Linux native: To compile ONScripter to Linux native, execute make in the repo/ directory. However, you may need to install some libraries. Please STFW to resolve this; Next, download some smaller ONS games for testing (e.g., "Dream of the Stars," approximately 100MB; please search the web for details). After extracting the game, launch it with the following command:

./repo/build/onscripter -r GAME_EXTRACTION_PATH

Since it runs on Linux native, you can use the mouse to play the game. You can also use arrow keys to move the cursor and use ENTER to confirm or ESC to cancel actions. [onscripter github]: https://github.com/LasmGratel/onscripter-jh

In order to port ONScripter to Navy, we first need to know what libraries ONScripter depends on. You can find out which libraries you depend on by reading the LDFLAGS variable in navy-apps/apps/onscripter/repo/Makefile:

• SDL - In Navy, we use libminiSDL to provide function compatible functionality.
• SDL_ttf - This is a TrueType font library, In Navy, we utilize libminiSDL and TrueType font parser in project stb, to provide partial API compatibility with SDL_ttf, primarily for rasterzing TrueType fonts.
• SDL_image - This is a image library, In Navy, we utilize libminiSDL and image decoders in project stb, to provide partial API compatibility with SDL_image, mainly for decoing JPG, PNG, BMP and other image formats
• SDL_mixer - This is an audio mixing library, In Navy, we use libminiSDL and libvorbis to provide partial API compatibility with SDL_mixer, primarily for implementing multi-channel OGG audio mixing.
• bz2 - This is a compression library, In Navy, we have removed the functionality related to accessing compressed files from ONScripter, Therefore, when compiling for Navy, ONScripter's execution does not depend on the compression library.
• m - This is the math library of glibc. In Navy, libfixedptc provides some floating-point arithmetic functionalities.

Caching and font rasterization

The TTF_RenderGlyph_Shaded() function in navy-apps/libs/libSDL_ttf/src/ttf.c is used to rasterize a character from the font library, generating the corresponding pixel information and a color palette. The code adds a small cache when generating the color palette, do you know how it works? Why does it improve performance? (though not by a huge margin).

It should be noted that due to some shortcomings of the above mentioned libraries in Navy, we can't run all ONS games perfectly on Navy. Specifically:

• The rasterization algorithm used by the truetype parser in the stb项目may not be able to rasterize some truetype fonts well, resulting in less spaced text, which is not as effective as the Linux native SDL_ttf library
• The library in Navy only supports decoding OGG audio, so it does not support ONS games that need to play other audio formats (e.g. MP3).

Supplementing SDL-related libraries

Let's first consider running ONScripter on Navy native. Since ONS games generally requires a larger screen to run, we need to define macro MODE_800x600 in navy-apps/libs/libos/src/native.cpp. Afterwards, we we can try to run ONScripter on Navy native:

cd navy-apps/apps/onscripter
make ISA=native run mainargs="-r GAME_EXTRACTION_PATH"

If you see the terminal output something like the following, ONScripter has successfully read the game information:

ONScripter-Jh version 0.7.6 (20181218, 2.96)
Display: 800 x 600 (32 bpp)
Audio: -937182692 Hz 0 bit stereo

Where the display resolution is related to the specific ONS game, the output of the audio information is some garbage, this is because we haven't implemented the sound mixing library yet. Next ONScripter may trigger an assertion fail in the miniSDL library, or report that it cannot open the file and exit.

In order for ONScripter to run successfully, we need to add to the implementation of the miniSDL library. The additional features include (be sure to RTFM for details):

• timer.c: Add timer registration and removal functions. The implementation of the callback function can be referred to the implementation of the audio data filling in PA3.

// register a counter, invoke callback function after `interval` milliseconds
SDL_TimerID SDL_AddTimer(uint32_t interval, SDL_NewTimerCallback callback, void *param);

// remove previously registered conuter
int SDL_RemoveTimer(SDL_TimerID id)

• event.c: Add event queuing and checking. SDL supports user-defined events, so we need a queue to buffer unprocessed events. After implementing the event queue, we can add the key events that read from NDL to the event queue via SDL_PushEvent() so that we can handle all kinds of events in a unified way.

// add an event `ev` to the event queue
int SDL_PushEvent(SDL_Event *ev);

// Perform the `action` on the first `numevents` events in the event queue that match the mask.
// macro `SDL_EVENTMASK()` well illustrate the meaning of `mask`
// In NScripter, `numevents` is always 1 and `action` is always `SDL_GETEVENT` which could be used to simplify implementation
int SDL_PeepEvents(SDL_Event *ev, int numevents, int action, uint32_t mask);

• file.c: The SDL library provides user programs with a unified interface such as SDL_RWread(), SDL_RWwrite(). It also abstracts file operations on various platforms through function pointers, so that users do not need to care about the details of specific file operations. This idea is very similar to the VFS we introduced in PA3, see 这里. In ONScripter, we only use ordinary files and "memory files", you need to implement the corresponding file operations for them. An "in-memory file" is a section of memory that is treated as a sequence of bytes and is accessed through file operations. Note that the semantics and return values of these operations may differ from the corresponding library functions in libc, so please RTFM carefully.

glibc support for in-memory files

In fact, glibc provides a library function at fmemopen() to support in-memory file manipulation, you can use fmemopen() to greatly simplify your implementation, please refer to RTFM for details.

Apart from miniSDL library, we also need to implement another two APIs in SDL_image. The first API is

SDL_Surface* IMG_Load_RW(SDL_RWops *src, int freesrc);

It is very similar to the IMG_Load() in PA3, except that it decodes the pixel infomation of the image from the SDL abstract file. When used by ONScripter, the type of src is always an in-memory file, while freesrc is always 0 , and this information can help you simplify your implementation.

The second API is

int IMG_isPNG(SDL_RWops *src);

It is used to determine whether the SDL abstract file src is an image file in PNG format. The best way to determine the type of a file is to check the magic number stored in the file: recall that we consider a file to be an ELF file when it has a magic number of 0x7f 0x45 0x4c 0x46. PNG files have a similar magic number, please STFW for more details.

Running ONScripter

After conquering the above tasks, you can run in ONScripter Navy native! There's no sound yet, but you can still see the image and manipulate it.

Since Navy doesn't support mouse, you can only use keyboard to perform operation. We add a simple cursor of 4x4 pixels to the ONScripter code, so you can see the cursor move when you type the arrow keys. However, the implementation of this simple cursor is not perfect, sometimes you will see more than one cursor on the screen.

Implementation of the mixer library SDL_mixer

This part is totally optional

Pre-task: Implement NDL and miniSDL audio playback in PA3.

Is should be noted that even without implementing a sound mixing library, ONScripter can still run without audio (but cannot support auto-reading). However, audio counts a lot in terms of text adventure gameplay experience.

Multiple audio clips are usually played at the same time in a game, for example, during a battle, there will be a background music BGM, the sound effect of the spell will be played during the casting of the spell, and the sound effect of the enemy's injury will be played when the spell causes damage to the enemy. qq the player's point of view, these audio clips are played simultaneously, and the mixer library SDL_mixer is used to manage multiple audio clips and realize the effect of simultaneous playback through mixing.

First we provide the manual for the mixer library SDL_mixer. Although the manual describes a lot of APIs, we don't need to implement all of them. The APIs used by ONScripter are listed at navy- apps/libs/libSDL_mixer/src/mixer.c . We don't need to implement all of them, some of which are just used for linking and ONScripter doesn't call them when running some of the games. It is important to note that when implementing these APIs, please be sure to read the details via RTFM.

Is is possible to utilize the API of SDL sould to implement SDL_mixer. Specifically, you can call SDL_OpenAudio() and SDL_PauseAudio() from Mix_OpenAudio() and SDL_CloseAudio() from Mix_CloseAudio(). Recall that SDL_OpenAudio() needs to provide a callback function to populate the audio data, so the implementation of SDL_mixer can be divided into two parts, one for implementing various APIS that maintain the audio state and the other for implementing the real mixer effect in the callback function.

Play BGM

Playing BGM is relatively simple, so we can implement it first. Specifically, you need to implement the following API:

Mix_Music *Mix_LoadMUS_RW(SDL_RWops *src);
void Mix_FreeMusic(Mix_Music *music);
int Mix_PlayMusic(Mix_Music *music, int loops);
int Mix_VolumeMusic(int volume);
int Mix_HaltMusic();
int Mix_PlayingMusic();

Since there is only the BGM audio, no other sound effect audio exists. We need to do the mixing in the callback function so that we can realize the BGM playback.

Playing BGM in ONScripter

Implement the above API to play ONS game BGM in ONScripter.

In these APIS, Mix_PlayMusic() is used to start playing a piece of music, which can be done by opening an audio file via stb_vorbis_open_memory() in libvorbis and then decoding the audio via stb_vorbis_get_samples_short_interleaved() in a callback function, It is suggested to read documentation in navy-apps/libs/libvorbis/include/vorbis.h or reference the implementation of NPlayer for more details. The rest of the API is related to audio state maintenance, so it's up to you to decide how to implement state maintenance.

BGM auto-replay in ONScripter

The SDL_mixer library supports auto-playback of audio: when the audio has finished playing, it is automatically replayed from the beginning, without the user having to play it

::::manually.

This is accomplished by using the loops parameter in Mix_PlayMusic(). In addition, you can tell if the audio has finished playing by the return value of stb_vorbis_get_samples_short_interleaved() You can also play the audio from the beginning by stb_vorbis_seek_start(), please RTFM for more details.

Once implemented correctly, you can enjoy auto-replayed BGM in ONScripter.

Play sound effects

In order to support the simultaneous playback of multiple sound effects, the SDL_mixer library refers to a sound object as a "chunk" and introduces the concept of a "channel". Users can put a clip on any channel to play. Multiple channels of the clip will be mixed with the BGM so as to realize the effect of BGM and multiple sound effects at the same time. Note that the "channel" in SDL_mixer and the "channel" in the audio files have different meaning although they have the same name. The following diagram well illustrates the difference between the two.

      +---> Left Channel
     +++-+
 * = |L|R|
     +-+++
        +---> Right Channel

          +-----+------------------------------------------------------------+-----+
Channel 1 |     |************************ Chunk 1 ***************************|     |
          +-----+------------------------------------------------------------+-----+

          +-----+-------------+--------------------+-------------------+-----------+
Channel 2 |     |** Chunk 2 **|                    |***** Chunk 3 *****|           |
          +-----+-------------+--------------------+-------------------+-----------+

          +---------------------------------+-------------+------------------------+
Channel 3 |                                 |** Chunk 2 **|                        |
          +---------------------------------+-------------+------------------------+

The above figure shows three channels, each of which plays its clip at the same time. When multiple channels need clips simultaneously, the callback function needs to mix them. Considering the clips themselves, they are dual-channel, i.e. each sample has both left and right channel data.

Once you understand the above concepts, you can implement the following APIs related to sound playback:

Mix_Chunk *Mix_LoadWAV_RW(SDL_RWops *src, int freesrc)
void Mix_FreeChunk(Mix_Chunk *chunk)
int Mix_AllocateChannels(int numchans);
int Mix_PlayChannel(int channel, Mix_Chunk *chunk, int loops);
int Mix_Volume(int channel, int volume);
void Mix_Pause(int channel);
void Mix_ChannelFinished(void (*channel_finished)(int channel));

Mix_AllocateChannels() is used to allocate the appropriate number of channels and Mix_ChannelFinished()is used to set a callback function to notify the user that the clip is finished,which is used by ONScripter to realize the auto-reading function of the text adventure game. The rest of the API is very similar to the corresponding API for BGM, but the object is now a channel, please refer to RTFM for the exact behavior.

Finally, you need to implement the mixing in the callback function that fills in the audio data: you need to check if the BGM and the channels are playing. If they are, you should mix the corresponding audio data accordingly..

Play sound effects in ONScripter

Implement the sound playback API and sound mixing functionality. Once implemented correctly, you will be able to run ONS games in ONScripter in a more complete way.

Conversion of sampling frequency and number of channels

ONScripter will initialize the audio device with "44100Hz Dual Channel" by default and ONS games can be played normally if the audio files match this attribute, such as "CLANNAD". However, if the audio files to be played do not have the "44100Hz Dual Channel" attribute, playing them directly will result in distortion. For example, in one of the ONS versions of "Ever 17", the BGM is sampled at 22050Hz, while in "Starscream", a few sound effects are even mono. In order to solve the distortion problem of these audio files, we need to do some conversion operations on the audio data.

The conversion operation is very simple: if the audio file is played with a sample frequency or number of channels smaller than the way the audio device is turned on, the audio file will be "expanded". Specifically, we just need to copy each decoded sample.

            +-A-+-B-+-C-+
  Before    +-+-+-+-+-+-+
convertion  |L|R|L|R|L|R|
  22050Hz   +-+-+-+-+-+-+

            +-A-+-A-+-B-+-B-+-C-+-C-+
   After    +-+-+-+-+-+-+-+-+-+-+-+-+
convertion  |L|R|L|R|L|R|L|R|L|R|L|R|
  44100Hz   +-+-+-+-+-+-+-+-+-+-+-+-+
=====================================
            +A+B+C+
  Before    +-+-+-+
convertion  |S|S|S|
   mono     +-+-+-+

            +-A-+-B-+-C-+
   After    +-+-+-+-+-+-+
convertion  |L|R|L|R|L|R|
  stereo    +-+-+-+-+-+-+

If the sampling frequency or number of channels of the audio file being played is greater than the way the audio device is turned on, the audio file is "truncated". However, most games do not have audio quality higher than "44100Hz Dual Channel", so we can leave this case alone.

One final question: How do we get the attributes of an audio file? It turns out that libvorbis library provides a stb_vorbis_get_info() API, which can be used to read out the properties of an audio file. Please refer to the implementation of NPlayer or RTFM for more detail.

Playing sound effects in ONScripter(2)

Converts audio data so that ONScripter can playback audio of different quality.

Implement disk

With the addition of the above library implementation, ONScripter will run perfectly on Navy native. In order to run ONScripter on AM native or NEMU, we also need to consider the storage space issue. AM native and NEMU both assume that the size of physical memory is 128MB, but ONS game data files generally occupy a lot of space. For example, Starscream's data files are nearly 100MB. Therefore, if we put them on ramdisk, we'll have less than 30MB of physical memory available to the system. (Actually it will be less, because Nanos-lite itself need to load user processes and perform paging mechanism which also need to use physical memory). As ONScripter engages in image and audio decoding, the system may be "running out of physical memory". The "CLANNAD" data file is nearly 1GB which is impossible to put into the ramdisk. Therefore, we need a storage device that doesn't use up physical memory, which is the disk.

Unlike ramdisk, the access latency of a real disk is much higher compared to memory. If the disk can only be accessed to read or write one byte at a time, the efficiency of disk access is intolerably low. Therefore, disk controllers usually access disks in blocks, which are typically 512 bytes or more in size.

The IOE in AM has provided the abstraction for disk. Specifically, abstract-machine/am/amdev.h has provided three abstraction registers for disk:

• AM_DISK_CONFIG: AM disk controller information, you can read the presence flag present, block size blksz and disk size blkcnt. In addition, AM assumes that the block size and disk size will not change while the system is running.
• AM_DISK_STATUS: AM Disk Status Register, reads whether the disk is currently in a ready state ready .
• AM_DISK_BLKIO: AM Disk Status Register, reads whether the disk is currently in a ready state ready . if write is 1, you can write the blkcnt disk block starting at buf to the disk blkno location if write is 0, you can read the blkcnt disk block starting at the blkno disk block to buf .

We start by implementing the disk on AM native. Since AM native can use the Linux runtime environment, we can easily access files on Linux, we just need a way for the AM native to know the path of disk image. Environment variables can make it:

const char *diskpath = getenv("diskimg");

After that, we could specify diskimg argument for make:

make ARCH=native run diskimg=$NAVY_HOME/build/ramdisk.img

You need to implement the above abstract register operations on the AM native's IOE:

• AM_DISK_CONFIG
  • If the image indicated by diskimg exists, set the flag present to 1, otherwise set it to 0.
  • Block size blksz is set to 512(字节)
  • Disk size blkcnt i.e. the size of the image file is calculated in units of blksz.
• AM_DISK_STATUS - We always assume the disk is ready.
• AM_DISK_BLKIO - This can be achieved by reading and writing files, but you need to pay attention to the unit conversion.

After implementing disks on AM native, we need to add disk support to Nanos-lite. Specifically, you need to implement the following API.

size_t disk_read(void *buf, size_t offset, size_t len);
size_t disk_write(const void *buf, size_t offset, size_t len);
void init_disk();

These APIs are very similar to the ramdisk API. You should also be aware that the file system sees sequences of bytes, whereas the disk can only be accessed in blocks. Therefore, you still need to do some unit conversion. To implement this, change the code at fs.c to replace ramdisk access with disk access. You also need to remove the ramdisk code from resources.S .

Implementing disks for AM native

Based on the above, add disk support to AM native and Nanos-lite. In addition, in order to make AM native support bigger screen, you need to add corresponding code accroding to this. Then, define a macro MODE_800x600.

实现正确后, 你就可以在AM native上运行ONScripter了.

Finally, In order to run ONScripter in NEMU, we need to add disk device support to NEMU(nemu/src/device/disk.c). First of all, let's make NEMU's disk device get the path to the image file by means of the following environment variable.

// Attention, below is the presudo code.
diskpath = getenv("NAVY_HOME") + "/build/ramdisk.img";

Then we need to add some device registers to allow the program to communicate with the disk device and access these device registers to implement the disk-related abstract registers in AM. For disk read/write operations, we can agree that the program writes other information to the device registers first, then writes the read/write command to a command register called CMD. When the disk device finds out that the command register has been written to, it will perform the specified read/write operation.

NEMU磁盘设备的读写操作同样可以通过文件操作来实现, 不过程序给出的地址buf究竟是什么地址呢? 注意到这个地址可能是从Navy的应用程序一路传递过来的, 而Navy应用程序使用的地址是虚拟地址, 但磁盘设备无法理解虚拟地址, 这是因为虚拟地址是CPU中的MMU提供的虚存机制而产生的概念, 设备直接使用这个地址进行磁盘操作会导致错误.

可以理解虚拟地址的设备

事实上, 一些功能复杂的现代设备也可以理解虚拟地址, 在这些设备的内部, 有一个叫IOMMU的模块, 用来将设备发出的虚拟地址转换成物理地址, 然后再访问内存. 这样以后, 操作系统就可以直接把应用程序提供的虚拟地址写入到设备里面了.

不过我们需要面临一个问题: 我们如何保证IOMMU对同一个虚拟地址的转换和CPU中MMU的转换结果一致呢? 如果这个转换不一致, 设备就会访问到错误的物理内存位置. 为了解决这个问题, 操作系统还需要维护CPU MMU和IOMMU之间的一致性. 嗯, 我们在PA中还是不要弄得这么复杂了.

为了解决这个问题, 我们可以在Nanos-lite的磁盘支持中添加一个专门用于磁盘读写的小缓存:

uint8_t blkbuf[blksz];

从磁盘中读出数据时, 先把数据块读到blkbuf中, 然后再拷贝到应用程序提供的buf中; 往磁盘中写入数据时, 先把数据块写到blkbuf中, 然后再把blkbuf的内容写入到磁盘中. 注意到blkbuf位于Nanos-lite中, 当分页机制开启时, 它位于地址空间的恒等映射中, 因此它的虚拟地址可以直接作为物理地址来使用. 于是我们就通过了blkbuf的中转, 解决了磁盘设备无法理解虚拟地址的问题.

磁盘和缓存

我们只使用了一个数据块大小的缓存, 但在真实的操作系统中, 磁盘的缓存要大得多. 这时, 磁盘缓存充当的角色和CPU cache非常类似, 都是利用程序的局部性提高磁盘访问的性能.

最后, 虽然NEMU的磁盘设备拿到了物理地址, 但这个物理地址是客户程序看到的pmem地址. 为了调用fread()/fwrite(), 我们还需要把这个物理地址转换成NEMU作为一个用户进程看到的虚拟地址:

guest_to_host(addr - PMEM_BASE)

这样以后, NEMU就可以通过native的glibc来读写镜像文件了.

实现NEMU的磁盘

根据上述内容, 在NEMU和相应的AM中添加磁盘的支持. 编译NEMU时, 需要在menuconfig中选择磁盘相关的选项. 至于NEMU的磁盘设备需要支持哪些设备寄存器, 以及这些设备寄存器的地址位于哪里, 就交给你来思考和约定吧.

此外为了让NEMU支持更大的屏幕, 你还需要在menuconfig中选择800 x 600的屏幕大小:

[*] Devices  --->
  [*]   Enable VGA  --->
        Screen Size (800 x 600)  --->

实现正确后, 你就可以在NEMU上运行ONScripter了.

DMA和CPU cache

在NEMU的所有设备中, 磁盘是最特殊的一个设备, 因为它可以直接访问物理内存, 设备这样的工作方式称为DMA. 而现代CPU一般都配备cache, 如果磁盘想要访问的最新数据在cache里面, DMA应该如何访问到它们呢? 尝试查阅相关资料了解这个问题.

下学期预告 - 操作系统课程铺垫

ICS和PA作为操作系统课程的前导内容, 最重要的是让大家理解两个概念:

• 程序是个状态机
• 计算机是个抽象层

而操作系统作为计算机中一个非常重要的抽象层, 相信你在完成PA的过程中也略知一二了. 作为一个裁剪版的操作系统, Nanos-lite已经可以支撑起各种不简单的Navy应用(例如仙剑奇侠传), 那么它距离真正的操作系统, 究竟还有多远呢? 我们可以在PA这个计算机系统中体会一下Nanos-lite暂不支持的那些残缺的功能, 来让大家思考真正的操作系统究竟还需要解决什么样的问题, 从而为下学期的操作系统课程做一个承上启下的铺垫.

体验虚拟化 - 窗口管理器NWM

我们知道硬件的物理资源是有限的, 而为了支持多个用户进程的运行, 操作系统必须考虑如何对这些物理资源进行分配和管理. 而操作系统解决这个问题的手段, 就是虚拟化: 为物理资源创建相应的虚拟资源的概念, 让用户进程使用这些虚拟资源, 然后由操作系统来维护虚拟资源到物理资源之间的映射.

事实上, 你在PA4中已经体会过虚拟化的作用了:

• NEMU模拟了一个物理CPU, 但Nanos-lite却可以支持多个进程的分时运行, 这是因为Nanos-lite将NEMU中的物理CPU进行了虚拟化, 为每个进程分配一个虚拟CPU, 然后通过进程调度来决定下一时刻将哪一个进程的虚拟CPU映射到物理CPU, 并通过上下文切换完成映射的落实
• NEMU模拟了一段物理内存, 但Nanos-lite却可以支持多个进程访问到各自的内存而不会相互覆盖, 这是因为Nanos-lite将NEMU中的物理内存进行了虚拟化, 为每个进程分配一段虚拟内存的地址空间, 然后通过分页机制将进程的虚拟地址空间映射到物理内存, 并通过MMU的操作完成映射的落实

操作系统中"进程"的概念, 就是通过虚拟化的手段来实现的 (所以我们在PA4之前都无法解释清楚什么叫进程). 运行在Nanos-lite上的用户进程, 可以通过SYS_execve来实现进程的重置, 将当前进程重置成某个程序的初始状态, 也可以通过SYS_exit实现进程的退出, 但用户进程却没有办法实现进程的创建(如果我们在init_proc()中创建两个进程, 那么在系统运行的过程中, 无论如何也不会出现使用第三个PCB的进程).

在类Unix操作系统中, 进程的创建是通过系统调用SYS_fork来实现的, 它的功能非常特殊: 如果把进程看做一个状态机, 这个系统调用会把状态机的当前状态完整地克隆一份, 这时候系统中就多了一个"几乎完全一样"(除了系统调用的返回值有所不同)的进程在运行.

如何在操作系统中实现`fork()`?

思考一下, 基于上述功能的介绍, 我们应该如何在操作系统中实现fork()?

事实上, 我们在Nanos-lite中并不能完美地实现这个系统调用, 所以我们并不要求大家在PA中实现它. 不过我们还是可以在Navy的native中体验一下进程的创建. 我们在Navy中提供了一个叫NWM(NJU Window Manager)的应用, 这个应用非常特殊, 它是一个窗口管理器, 我们可以通过它创建一个新窗口, 并创建一个新进程关联到这个新窗口, 之后让这个新进程来执行execve(), 我们就实现了"在新窗口中执行一个新程序"的效果.

NWM默认支持运行7个程序(见navy-apps/apps/nwm/include/winimpl.h), 如果你没有完成之前的选做内容, 相应的程序将无法运行, 但你还是可以运行3个必做内容所要求的程序(NTerm, NSlider和仙剑奇侠传). 由于NWM需要更多系统调用的支持, 我们无法在Nanos-lite上运行它. 为了体验NWM, 你首先需要将navy-apps/fsimg/目录下的程序更换成Navy的native:

cd navy-apps
make ISA=native fsimg  # dummy无法编译到Navy native, 请手动去掉它

然后就可以在Navy的native上运行NWM了.

体验窗口管理器NWM (NJU Window Manager)

NWM启动后, 下方会出现一个菜单栏, 可以通过左右方向键选择程序, 键入回车键运行. 窗口相关的操作方式如下:

• A-up(ALT + 上方向键) - 当前窗口上移
• A-down - 当前窗口下移
• A-left - 当前窗口左移
• A-right - 当前窗口右移
• A-</code>(<code>是位于tab上方的按键) - 切换窗口
• A-R - 呼叫菜单栏

除了上述组合键之外, 其余按键将会转发到当前窗口.

支持按键缓冲

我们在PA3中实现NDL时, 是假设一次从/dev/events读出最多一个事件. 但如果我们在NWM中按键过快, NDL的NDL_PollEvent()可能会一次读出多个按键事件, 目前NDL可能无法处理(导致按键丢失或者触发assertion fail). 为了完美地解决这个问题, 我们可以在NDL_PollEvent()中实现一个事件缓冲区, 如果缓冲区中还存在事件, 就返回缓冲区中的事件, 否则就先将事件读入到缓冲区中.

NWM是如何实现的?

NWM的视觉效果和我们平时使用的GUI操作系统非常相似, 但我们通过不到1000行代码就实现它了. 感兴趣的同学可以阅读NWM的代码, 如果你遇到了不熟悉的系统调用, 不必担心, 你可以通过RTFM了解它们的行为. 这也可以作为对下学期操作系统课程的一个小小的预习: 你很可能会在操作系统课程上遇到这些系统调用.

体验并发 - 绘图Bug

操作系统通过虚拟化可以支持多个进程的并发执行. 如果这些进程做的事情是相互独立的, 那并不会出先太大的问题; 但如果这些进程需要访问相同的资源, 事情就会变得麻烦起来: 例如, 如果多个用户进程往同一个文件进行写入, 可以预想有可能会发生数据丢失的现象. 这些由于并发造成的bug, 称为并发bug.

体验PA中的并发bug

事实上, PA中也隐藏了一个并发bug, 我们可以通过以下方式让它暴露出来. 让Nanos-lite加载仙剑奇侠传和NTerm, 然后快速地来回键入F1和F2, 来回切换仙剑奇侠传和NTerm. 一段时间后, 你可能会观察到绘图不正确的现象:

思考一下, 这个bug是如何造成的?

通过上述体验, 你应该能体会到并发bug的如下特征:

• 难观测 - 并发bug造成的行为属于UB, 什么都有可能发生. 我们在这里已经选择了一个比较容易观测的例子: 绘图. 想象一下, 如果并发bug发生在其它地方(例如对内存中某个数据结构的访问), 我们应该如何有效地观测它?
• 难重现 - 进程分别单独运行的时候, 行为都是正确的; 但并发运行的时候则可能会出错. 而且并发bug并不是每次操作都能重现, 它与两个(或以上)进程之间的执行顺序有关: 如果进程切换的时机不对, 那这个并发bug就可能无法重现. 这直接增大了调试并发bug的困难.
• 难理解 - 即使我们能观测并重现出并发bug, 它的原因也比普通的bug更难理解. 普通的bug只需要明白单个进程的行为就能比较好地理解, 但要理解并发bug, 我们不仅要明白单个进程各自的行为, 还需要找到多个进程之间执行的某种交织, 才能比较好地理解. 而这样的交织有非常多的可能, 这对并发bug的理解带来了非常大的挑战.

为了解决并发带来的问题, 操作系统还需要提供如下的机制:

• 互斥 - 阻止多个进程同时访问某些关键的共享资源, 从而避免发生数据丢失的现象
• 同步 - 让多个进程之间按照某种安全的顺序来先后执行

基于这些机制, 操作系统就可以提供进程之间相互通信的机制. 现代操作系统上各个进程之间可以协同工作, 也是基于通信机制实现的. NWM中的窗口管理也是通过父子进程之间的通信实现的.

体验持久化 - 磁盘和游戏存档

操作系统作为计算机系统资源的管理者, 它需要管理一类和数据直接相关的设备: 存储设备. 数据是程序处理的对象, 而存储设备作为数据存储的载体, 操作系统必须对其进行额外的支持, 来保证程序可以正确地访问存储设备上的数据. 对存储设备来说, 这个问题就相当于"如何让数据正确持久地被存储".

如果把和存储设备数据访问相关的抽象层单独拿出来讨论, 我们就会得到一个和"系统栈"很类似的"存储栈". 要画出这个"存储栈"其实并不难, 这就相当于回答下面这个问题:

仙剑奇侠传是如何通过计算机系统中的层层抽象读出文件中的像素信息的?

噢, 你已经在PA3中回答过这个问题了.

在PA中, 我们其实把持久化的问题弱化了: 应用程序几乎不会对ramdisk进行写操作 (只有仙剑奇侠传存档的时候才会发生). 因此, 我们在PA3中介绍的sfs非常奏效, 我们通过少量的代码就可以支撑应用程序对ramdisk访问的需求了.

但在真实的计算机系统中不可能没有写操作, 考虑写操作的第一个问题, 就是要重新设计文件系统: 让文件在存储设备上连续存放不再是一个好的方案, 因为这会使得操作系统在存储设备上来回地搬运那些大小发生变化的文件. 这个问题的解决方法和我们在PA4中介绍的虚存管理非常类似, 回想一下, 我们是如何解决虚存管理中分段机制的缺陷的?

既然有写入操作, 那么我们需要考虑的第二个问题, 就是如何保证写入是成功的. 这个问题看上去好像很蠢, 写入就写入, 还会失败? 还真是会的, 首先我们知道磁盘是以块为单位访问的, 如果一个文件的大小超过一个块, 那么它就必须分多次进行写入, 如果一个文件写到一半的时候, 系统突然掉电, 那这个文件就会受损; 再者, 就算往磁盘中写入一个块的操作, 也并不总是成功的, 比如有可能遇到磁盘坏道. 因此, Windows在自动更新的时候会提醒你不要关机, 以免一些重要的系统文件受损, 导致操作系统无法启动. 你可能会想, 只要我不去强制关机, 这些事件发生的概率应该非常低, 真遇到就自认倒霉吧, 但操作系统设计者不能这样想, 他们都需要假设客户的数据是无比珍贵的. 虽然操作系统没有办法阻止掉电和坏道的发生, 但它仍然需要想方设法地让数据从这些灾难中存活下来, 至少避免让用户看到"一个文件只写了一半"的情况, 这样的性质叫"崩溃一致性".

体验PA中的"崩溃不一致性"

仙剑奇侠传的存档结构体SAVEDGAME_COMMON在navy-apps/apps/pal/repo/src/global/global.c中定义. 修改Nanos-lite中ramdisk_write()的代码, 使得它写入N字节后直接返回, 来模拟系统掉电的情况. 你可以根据存档结构体的定义来精心计算N, 使得存档只写入部分数据, 例如经过战斗后进行存档, 然后马上读档, 你可能会看到金钱更新了, 但角色的经验值没有更新.

如果你实现了磁盘的选做内容, 那就更简单了: 你只需要在NEMU磁盘设备的写入代码处随机触发assert(0)即可. 这样以后, 你下次就很可能会读到一个已经损坏的存档. 你不必担心无法取回正确的存档, 因为我们可以重新制作一个正确的磁盘镜像.

虚拟机和崩溃一致性

如果你用虚拟机来做实验, 有可能碰到过虚拟机在运行过程中, 真机死机了, 重启之后虚拟机就损坏的情况. 这个问题其实和崩溃一致性有关. 对虚拟机里面的应用来说, 它们进行数据写入的存储栈其实非常深: 数据穿过了客户机里面的存储栈之后, 才会到达虚拟机软件(VMWare或VirtualBox)的文件管理模块, 然后数据又要穿过真机的存储栈, 最终才会到达真正的存储设备. 因此, 虚拟机的崩溃一致性要比一般的程序更难保证, 从这个方面来说, 强制关闭虚拟机比强制关闭真机更容易造成问题.

即使数据被成功写入了, 我们还需要考虑第三个问题: 如果数据读出来不正确怎么办? 存储设备也不是100%可靠的, 随着存储设备的老化, 这个问题可能会越来越明显. 如果你今天往一个劣质U盘里面存储了一个文件, 明天打开这个文件的时候系统就可能会提示"文件已损坏". 你可能听说过解决这个问题的方法, 那就是多副本备份+校验/纠错, 至于如何高效地做到这些, 这就是另一个问题了.

最后, 为了提高访问存储设备的性能, 操作系统一般会在存储栈的某些层次上添加缓存, 不要让数据每次都直接写入存储设备, 而是想方设法地让数据尽可能长时间地留在缓存中. 但这样就持久化的目标有着明显的冲突, 持久化的目标要求尽快将数据写入到磁盘中. 如何在性能和持久化之间取得权衡, 也是操作系统设计的一大挑战.

如果你发现你在编写应用程序的时候从来不需要考虑这些问题, 这就对了, 这恰恰反应出操作系统已经比较好地帮我们解决了这些问题, 使得作为操作系统用户的我们感知不到这些问题的存在.

什么是操作系统?

我们给大家简单梳理了操作系统在虚拟化, 并发, 和持久化三个方面的挑战. 但对一个系统来说, 最复杂的问题则是来源于各种机制之间的交互: 多个进程执行fork()后并发地通过mmap()读写磁盘上的同一个文件, 其行为会怎么样?

这个问题并不是为了故意刁难大家: 真实的问题很有可能就是在多个模块和机制的相互作用下产生的, 要解决真实的问题, 你就需要学会从多个角度系统地思考. 操作系统作为一个世界上最复杂的软件, 相信你在下学期学习的时候也会对系统的复杂性有所体会.

OSlab来啦

课程网站见这里.

从一到无穷大

事实上, 计算机系统的工作只做两件事情:

• make things work
• make things work better

PA让大家体会了一次make things work的全过程. 具体地, PA以AM为主线, 从零开始展示了硬件, 运行时环境(操作系统)和应用程序之间同步演进的关系:

• TRM - 硬件有指令和内存, 几乎无需任何运行时环境, 就能运行所有的可计算算法
• IOE - 硬件添加输入输出, 运行时环境提供设备访问的抽象, 就能运行单一的交互式程序
• CTE - 硬件添加异常处理, 运行时环境添加上下文管理, 就可以支持批处理系统, 让用户程序顺序地自动运行
• VME - 硬件添加虚存机制, 运行时环境添加虚存管理, 就可以支持分时多任务, 让多个用户程序分时运行

必答题

分时多任务的具体过程 请结合代码, 解释分页机制和硬件中断是如何支撑仙剑奇侠传和hello程序在我们的计算机系统(Nanos-lite, AM, NEMU)中分时运行的.

理解计算机系统 尝试在Linux中编写并运行以下程序:

int main() {
  char *p = "abc";
  p[0] = 'A';
  return 0;
}

你会看到程序因为往只读字符串进行写入而触发了段错误. 请你根据学习的知识和工具, 从程序, 编译器, 链接器, 运行时环境, 操作系统和硬件等视角分析"字符串的写保护机制是如何实现的". 换句话说, 上述程序在执行p[0] = 'A'的时候, 计算机系统究竟发生了什么而引发段错误? 计算机系统又是如何保证段错误会发生? 如何使用合适的工具来证明你的想法?

温馨提示

PA4到此结束. 请你编写好实验报告(不要忘记在实验报告中回答必答题), 然后把命名为学号.pdf的实验报告文件放置在工程目录下, 执行make submit对工程进行打包, 最后将压缩包提交到指定网站.

欢迎二周目

你在一周目的PA中学到了什么? 二周目的时候就知道了: 二周目很顺利的部分就是你已经掌握的内容.

这就是PA的全部内容.

当然, 还有各种原则和方法

除了"程序如何在计算机中执行", PA还展示了很多做事的原则和方法, 现在的你能回想起哪些内容呢?

如果你想不起来, 或者无法回忆起"程序如何在计算机中执行"的每一处细节, 那么也许你应该尝试一下独立完成二周目了. 坚持独立完成, 你将会对这些问题有全新的理解.

但为了make things work better, 各种各样的技术被开发出来.

交互时代

就硬件而言, 摩尔定律预测了集成电路工艺的发展规律, 电路的集成度会越来越高. 这对计算机来说可谓是免费的午餐: 即使硬件架构师和软件设计师什么都不做, 芯片中的电路也会越来越小, 越来越快, 越来越省电. 电路工艺的发展直接推动了工作站和PC机的诞生, 搭载小型芯片的PC机开始走进寻常百姓家. 这意味着计算机不再像40-60年代那样只能进行核弹模拟, 密码破译等军事任务了, 它需要与普通用户进行交互, 于是需要一个支持交互的操作系统来方便用户使用, 当时最著名的就要数Unix和DOS了. 伴随着Unix的出现, 还有另一个流传至今的项目, 那就是C语言. 有了C语言编译器, 一些专业用户就可以开发自己的程序了. 办公和编程, 算是那个时代最普遍的应用了.

见证着摩尔定律的快速增长, 显然硬件架构师们并不会置身事外. 电路越来越小, 意味着同样大小的芯片上可以容纳更多部件, 实现更加复杂的控制逻辑. 从硬件微结构设计来看, 提升性能的一条路线是提高并行度, 从多级流水线, 超标量, 到乱序执行, SIMD, 超线程... CPU的并行度被逐渐挖掘出来; 提升性能的另一条路线是利用局部性, 于是有了cache, TLB, 分支预测, 以及相应的替换算法和预取算法... 在这些技术的支撑下, CPU等待数据的时间大幅降低, 从而能投入更多的时间来进行计算. 每当这些新名词出现, 都能把计算机的性能往上推. 计算机越来越快, 就能做越来越复杂的事情了. 一个例子是大大降低了计算机使用门槛的GUI, PC机上的分时多任务操作系统越来越普遍, 音乐, 视频, 游戏等休闲娱乐的应用开始大规模出现.

PC的足迹

PC的足迹系列博文对PC发展史作了简要的介绍, 上文提到的大部分术语都涵盖其中, 感兴趣的同学可以在茶余饭后阅读这些内容. 另外这里有一张x86系列发展的时间表, 在了解各种技术的同时, 不妨了解一下它们的时代背景.

上面的微结构技术都是在让一个处理器的性能变得更强(scale up), 而大型机和超级计算机早就用上了这些技术了, 它们在另一个维度上让自己变得更强: 通过片上互联技术(interconnect)把更多的处理器连接起来, 让它们协同工作(scala out). 于是有了SMP, ccNUMA, MPP, 以及各种互联拓扑结构. 同时为了高效应对多处理器架构中的数据共享问题, cache一致性和内存一致性也逐渐进入人们的视野. 为了适配片上互联技术, 可以管理众多处理器资源的集中式操作系统被设计出来, 随之而来的还有新的编程模型, 用于在这些强大的计算机上开发并运行应用. 过去诸如大气模拟, 物理建模等科学计算应用, 如今可以更快更好地在这些超级计算机上运行. 但片上互联技术要扩展规模较为困难, 大规模的处理器互联成本非常昂贵, 一般只有超级计算机能承受得起.

互联时代

如果没有互联网的普及, 计算机的发展估计就这样到头了. TCP/IP协议的标准化解决了互联网的传输控制问题, 让互联网从局域网迈向全球, 真正的因特网从此诞生. 因特网让人们变成了地球村的村民, 只要一根网线, 就可以轻而易举地访问到世界上任何一个角落的计算机. 另一方面, HTTP和URL的出现则真正让因特网广为人们所知, 网页浏览, 电子邮件, 文件传输, 即时语音等网络应用开始流行, 通过PC机的屏幕, 用户可以看到全世界.

除了PC机, 互联网的出现也让机器之间的互联成为了可能, 于是有了集群. 而集群需要一个可以管理众多计算机资源的分布式操作系统, 相应的分布式编程模型也开始出现, 过去在一个计算机上运行的任务, 现在可以编写相应的分布式版本来在集群中运行. 集群的出现一下子解决了系统扩展性的成本问题, 只要几个廉价的计算机和几根网线, 就能组成一个集群. 从此, 互联网公司如雨后春笋般诞生, 人类开始迈进互联时代.

集群的规模进一步扩大, 就成了数据中心. 由于集群实在太容易构建了, 有大量的机器却缺少可以运行的程序. 另一方面, 摩尔定律并没有停下脚步, 为了进一步挖掘处理器的并行度, 多核架构开始出现. 集群和多核架构造成了计算资源的供过于求, 数据中心的利用率非常低. 于是虚拟化技术诞生了, 在hypervisor的支持下, 一个计算机可以同时运行多个不同的操作系统. 这还不够, 为了进一步提高集群的利用率, 互联网公司开始以虚拟机为单位出租给客户, 让客户在其上自由运行自己的系统和应用. 后来, 硬件厂商在芯片中新增了虚拟化的硬件支持, 降低了虚拟化技术的性能开销, 虚拟机的性能和真机越来越接近. 云计算的大门从此打开, 越来越多的应用开始移动到云端.

此外, iPhone的诞生重新定义了手机的概念, 手机从过去的通讯工具变成了一台名副其实的计算机. 于是手机处理器和手机操作系统再次进入人们的视野, 和PC机相比, 手机上的处理器和操作系统还需要面对功耗问题的严峻考验. 手机应用开始大量涌现, 包括即时通信和移动支付在内的各种手机应用已经改变了用户的习惯. 各种应用也开始采用端云结合的运行模式, 现在我们在手机上点击一下微信应用的图标, 登录请求就会通过网络传输到云端, 被数据中心中的上百台服务器进行处理, 最后我们才会看到登录界面.

融合时代

互联网把人和计算机连接起来, 但这并没有结束. 摩尔定律还在发展, 处理器面积进一步减小, 以前把设备接入计算机, 现在可以把计算机嵌入到设备中了. 于是各种小型设备和物品也可以接入到互联网中, 这就是物联网.

随着接入互联网的人机物越来越多, 这些终端产生的数据也日益增加, 大数据时代拉开了序幕: 据IBM统计, 在2012年, 每天大约产生2.5EB(1EB = 10^6TB)的数据. 为了处理这些大数据, 人工智能和机器学习的概念再次流行起来, 但这一下子带来了海量的数据处理任务, 于是GPU和FPGA也加入到这场大数据的持久战当中来. 还有一支奇兵就是ASIC, 和CPU不同, ASIC是一个专用电路, 可以对某一应用进行深度优化. 以AI芯片为例, 与CPU相比, AI芯片可以提升成千上万倍的性能功耗比. AlphaGo的横空出世让人们感受到了人工智能的强大, 现在人工智能芯片也已经开始集成到手机中了, 人们也逐渐发现照片越拍越漂亮, 应用越用越智能.

在这个时代, 貌似没什么是不可能的. 计算机, 用户, 网络, 设备, 云, 数据, 智能... 这些概念之间的边界变得越来越模糊, 直接和应用打交道的用户, 也越来越感受不到操作系统和硬件的存在. 这反而说明了, 那些一脉相承的计算机基本原理已经在时代的发展中留下了挥之不去的烙印.

万变之宗 - 重新审视计算机

什么是计算机? 为什么看似平淡无奇的机械, 竟然能够搭建出如此缤纷多彩的计算机世界? 那些酷炫的游戏画面, 究竟和冷冰冰的电路有什么关系?

"一"究竟起源于何处? "无穷"又会把我们带到怎么样的未来? 思考这些问题, 你会发现CS的世界有太多值得探索的地方了.

世界诞生的故事 - 终章

感谢你帮助先驱创造了这个美妙的世界! 同时也为自己编写了一段不朽的传奇! 也希望你可以和我们分享成功的喜悦! ^_^

故事到这里就告一段落了, PA也将要结束, 但对计算机的探索并没有终点. 如果你想知道这个美妙世界后来的样子, 可以翻一翻IA-32手册. 又或许, 你可以通过从先驱身上习得的创造力, 来改变这个美妙世界的轨迹, 书写故事新的篇章.