/Teaching/Operating Systems/Tutorials/Allgemeines

Allgemeines

Where do I get the zsh together with an appropriate configuration?

Enter: sudo apt-get install zsh && wget -O ~/.zshrc http://git.grml.org/f/grml-etc-core/etc/zsh/zshrc && chsh -s /usr/bin/zsh

Where do I find the manuals for the x86 or ARM-Architecture?

Intel Manuals are available here.

Regarding ARM-Manuals there are differences depending on the version. The ARMv5-Manual is a good starting point for SWEB-Development. However, the ARMv8-Manual will be useful as well, depending on the architecture you will choose in SWEB.

Do we HAVE to output to debug/kprintfd? Or is it enough to comment our code well?

You have to have at least some debug output, but there is no requirement for how many debug messages you need to generate. Please use the debug(…)-function, so you can control the output via debug flags. You can create your own flags, so you can have more fine-tuned control over which debug output gets displayed. Obviously, comments in the code are usually also a good idea, but a well-structured debug output cannot be replaced by a comment.

The test system score is only shown relative to the best group, how are we supposed to know that we’ve got enough points for the proof of concept?

This design is intentional. You are encouraged to implement as much as possible until the proof of concept deadline. Not only are you getting more feedback if you simply implement a wider range of features, but you also get bonus points for your hard work. If the deadline is coming closer and you’re getting nervous about achieving the required points: Ask your tutor about the current state of affairs.

Our group does not want to compete in the high score ranking with other groups. Is there a way to hide them?

Yes, there is. Just scroll down the ranking page and click “Opt out of the ranking”.

Do we get points for implementing library functions?

In general, you will only get points for kernel-related features. If the library functions in question make use of any Syscalls, which you have to implement, then you will most likely get points for them. Ask your tutor about any specific Syscalls not listed on the points sheet.

My unlocked points changed overnight, what happened?

One of your team members might have pushed something to a different branch while you were gone. The unlocked points always correspond to the currently tested branch, which is the branch the most recent commit was pushed to.

Compiling + Linking

If I add Assembler Code into the project or edit existing parts, will those files be compiled with Make automatically, or do I have to do this manually? What about C/C++?

As long as you add your files to already existing folders (which should contain a Makefile) and then run cmake, they will be integrated into sweb. The detection works via file endings: .cpp for C++, .c for C, .S for Assembly with AT&T-like Syntax (GNU assembler).

I’m having some trouble successfully compiling and executing 32-bit Sweb for the first time.

Make sure that after calling cmake, and before calling make, you executed make x86_32. This command switches the architecture to 32-bit.

Multithreading

How do I acquire a new address for a new user stack and how can I request memory for this?

They don’t “get” anything on their own. Since all threads of a process have to share the same virtual address space, all stacks of all threads have to fit in there. Where you put the stacks of the new threads is left for you to decide. It is then your job to insert this design into sweb.

On a 32-bit system the function parameters are passed via the stack, how does it work for 64bit?

On 64bit systems the first parameters are passed via the following registers in order: RDI, RSI, RDX, RCX, R8, R9 (Unix calling convention). Any remaining arguments will be passed via stack.

Which kind of threads should be forked by us? Should we only fork user threads? Or any kind of thread? What about if a kernel thread calls fork?

Since fork will be implemented as a syscall, only user threads will call it. We will not fork kernel threads. The details of how you fork will depend on your design and implementation, and it is part of your assignment to decide how to best go about it.

What is considered a good benchmark regarding total concurrent active threads?

Your operating system should be able to keep ~300 concurrent threads alive without running out of kernel heap. There should be no limit in terms of creating and destroying threads one after another.

Syscalls

If a user thread is currently handling a syscall in the kernel space and it calls yield(), where does the user thread continue, after it got resumed by the scheduler?

In the kernel space after the yield().

Is the syscall ‘exit’ called every time? Even if the program just reaches its last line of code?

If a program has reached the end of its code, then this program is terminated without the syscall exit. exit() is called in any case. If you look at the file userspace/libc/src/nonstd.c you will notice that it calls the main function first and the syscall exit.

Do we have to care for the correct ERRNO return values in case a Syscall fails?

No. You can simply return any value other than zero to signify that an error occurred, with -1 being the obvious candidate.

Kernel (in general)

We need a system time!

IRQ0 is issued periodically. You can count how many IRQ0s occurred (we call that ticks). Based on the frequency of the IRQ0 you get your system time. Sometimes you need more accurate timing. You can use the timestamp counter (rdtsc) for that or the RealTimeClock if you need the bios set date and time.

What is the frequency of the IRQ0 (timer interrupt)?

The default frequency is 18.2065Hz (that is approximately 54,9254ms between each IRQ0).

Do we need to handle out-of-memory errors for pthread_create(), fork(), …

The idea of handling out-of-memory scenarios based on the current occupation of your kernel heap sounds like a good idea, but this feat would require changing a lot of code that is already present in base Sweb (e.g., the ustl library).  You do not need to handle this case. Running out of free physical pages, on the other hand, is a topic that is covered in the second assignment.

User Programs

The Posix-Norm specifies void* for pointers. Can we use the type “pointer” instead, like it is defined in SWEB?

arch/x86/include/types.h is not used in Userspace-libc, just in the Kernel. The simplest approach would be to use the provided Types of the libc-Part and not violate POSIX. In the Kernel, however, you can feel free to use the predefined types or add your own ones, as long as it is compatible with the libc-page and is documented.

Is there a possibility to use Classes in the Userspace?

No, currently only C programs are supported in userspace.

Where in MemoryManagement is the classification into Data, Text, Stack, and Heap? I have looked through PageManager, but it does not differentiate.

The PageManager only has one task: Managing the free physical pages. That has nothing to do with the sections of an executable nor the ELF format. It is marked in the executable at which linear address which section (Data, Text, BSS) should be put. The Loader reads that info, gets a Page from PageManager, creates the mapping of the desired address to the just received physical address, and then writes the ByteCode on the specified linear address range.

Userspace Locks, Pipes, Waitpid

Are we allowed to use Syscalls when dealing with Userspace Locks?

The only Syscall that is allowed for userspace locks is yield. If a thread fails to acquire a mutex and wants to go to sleep, one single yield call is permitted. The purpose of that is to hand control over to the next thread as soon as possible, otherwise, the thread would have to busy-wait until it gets de-scheduled by the timer interrupt. Thus, continuously using the yield Syscall to busy-wait is not a viable option to implement mutexes. You are also not allowed to add arguments to the yield syscall for your locking purposes. Though, you can change the typedefs of the provided spinlock, mutex, semaphore, and CV datatypes.

Which mutex type are we supposed to implement for userspace locks?

We expect you to implement the ERRORCHECK type.

May I use the pthread_self() function to get the tid of the current thread for deadlock detection?

If your pthread_self() implementation is userspace only, sure!

Since I do not have access to malloc, I want to create a global fixed-size array in userspace for my locking purposes, is this a valid approach?

A fixed-size array implies that for every process, the user is bound to a maximum amount of locking primitives. This idea becomes impractical quite quickly: Imagine the user creating a lot of structs that contain locking primitives.

I managed to implement pipes by creating files in userspace, is it really that easy?

Pipe operations should not trigger any file I/O. Consider another approach.

I looked through the waitpid man-page and it is really confusing, are we supposed to implement everything that is listed on there?

No, since a strict process hierarchy is not expected nor recommended. Think of the waitpid Syscall as a process-level join.

Paging

The MMU does the address translation, for which it needs the paging structure. It knows where that is by putting the starting address of the table into the register. But how does it know the structure itself?

Correct, the register is called CR3. However, this does not point to the pageTABLE but first to the PageMappingLevel4, whose entries point to pageDirectoryPageTables and so on. The CPU determines the structure, which is also how it knows it. The OS then needs to adhere to that structure, you cannot change the structure of the CPU. You will find the barebones struct in paging-definitions.h in arch/x86/include/...

I understand the concept of the IdentityMapping and that it is used to access pages based on their physical page number. But who is responsible to set it up? Is it the MMU’s job?

No, the OS needs to set it up. This is done during booting by taking the whole physical address space and mapping each of its PPNs to a well-defined, consecutive virtual memory region in the kernel’s address space. The MMU treats the IdentityMapping just like any other mapped virtual memory region.

Assume 5 processes share a common physical page. As soon as this page is modified, the dirty flag is set in the modifying process’s PTE, right? The other 4 processes do not notice any modification.

Yes. However, this only holds if the PTE is not shared between the processes as well, but is exclusive to the modifying process.

How does the MMU know that a memory access results in a page fault?

Each memory access to a virtual address is resolved by the MMU. It translates the virtual address to a physical one by performing a multi-level page table walk. At each level, it checks the present bit to be set, if it is not set, the virtual address is not mapped and a page fault is triggered. Otherwise, the permission bits in the PTE are considered and matched to the thread’s privilege level (kernel- or userspace) as well as the memory access’s properties (reading, writing, instruction fetch). If one of these checks is violated, a page fault is again issued.

Where are the already loaded pages accessed? And where exactly is the Accessed Bit set?

On every access of a virtual address (read or write), the accessed bit will be set in the corresponding PTE automatically by the hardware (CPU/MMU).

Swapping

Where should we start our swapping implementations?

The main idea of swapping is to store memory content temporarily on the block device (BD). SWEB already provides the BD abstractions and methods to interact with the disk in the class BDVirtualDevice. Have a look at BDVirtualDevice::readData() and BDVirtualDevice::writeData(). To query the right BD, use BDManager::getDeviceByNumber(). SWEB’s swap device has number 3.

How can we find the block size of our disk? Is there a way of changing it?

You can query and adapt the block size using the getter and setter in BDVirtualDevice.h.

Are we allowed to change the Page Manager (PM) Class? Is it possible to add code and members without breaking everything?

Yes, you are allowed to add new members to the PM. HINT: Consider creating some Classes (f.e Swap-Management, PageTable, Inverse PageTable, ..) and just add these as members instead of coding everything into the PM)

Can we also swap a PT to the disk? And should we only swap PTs when all its pages are currently swapped as well?

Yes, and yes. Implementing PT swapping gives you additional points. Actually swapping a PT out is only meaningful when all its mapped pages are swapped too because the PT is at least as often accessed as its pages.

There are many descriptions of WorkingSet-*-algorithm on the internet, which one shall we implement?

All descriptions have something in common:

    • Each process has a working set size N (defined by a number or by time)
    • Each process has a number of mapped pages M
    • Each page has a process internal timestamp (process time(!), not real time) T
    • The N youngest pages are in the working set, the remaining M-N pages are not
    • Any page in no working set can be swapped
    • The working set size for all processes is decreased upon certain occasions (for example: when the number of free pages reaches zero)
    • The working set size for a process is increased upon certain occasions (for example: when a pagefault for this process occurs)

Apart from that, implement it as you like.

File System

Do I have to care for locking? For example, one or more threads have a file open and another thread writes to the same file.

No, you don’t. This is already implemented.

I’ve created a new test program, but actually, I can not run it. It seems that the program is not even copied to the SWEB image.

Does your test program have a long filename? Minix, the used file system, restricts filenames to a maximum of 30 chars. So if your file has a name longer than 30 chars (including the extension!) it can not be copied to the image. If you’re using CLion, make sure to never tick the add to targets option when creating a new file. If you accidentally already did that once, locate the CMakeList.txt for your userspace tests and replace it with the one that is present in base sweb.