/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.

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 structure is determined by the CPU, 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/...

Ich habe mittlerweile verstanden, dass der vierte GB des virtuellen Speichers ein 1:1 Mapping des physikalischen Speichers ist. Man verwendet also ‘get3GBAddress’, um direkt auf den physikalischen Speicher zuzugreifen. Aber: Bietet die MMU dieses Mapping von Haus aus an?

die Umsetzung der linearen Adressen in physikalische Adressen macht natürlich schon der Prozessor. SWEB kümmert sich nur darum, dass alle neuen page Directories so initialisiert werden, dass der Bereich zwischen 3 und 4 GB auf die physikalischen Seiten zwischen 0 und 1 GB zeigen.

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

Exactly!

Wie wird festgestellt, dass es sich um einen PageFault handelt?

Alle Speicherzugriffe werden über die MMU abgewickelt, die im PD und im PT die physikalische Adresse der Seite raussucht. Wenn im PDE (page-dir-entry) schon das present-Bit 0 ist, dann ist die PT nicht im physikalischen Speicher vorhanden. Wenn die PT aber vorhanden ist, dann wird erst im PTE nachgeschaut, ob das present-Bit gesetzt ist. Für das Auslösen eines PageFaults ist es egal, ob im PDE oder im PTE das present-Bit 0 ist.

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

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

Swapping

Wo ist die Größe des Blockdevices, das wir zum swapen verwenden sollen einzustellen? Ist es möglich die Devicegröße eines Blockdevices in sweb abzufragen?

Dazu gibt es die beiden BDRequest Typen BD_GET_BLK_SIZE und BD_GET_NUM_BLOCKS. Wenn du diese Requests an das Device schickst und die Ergebnisse multiplizierst hast du die Groesse des Devices in Bytes.

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 PMn)

Kann die PageTable der ausgelagerten Seite auch ausgelagert sein? (bei Behandlung im PageFaultHandler)

Die PT auszulagern macht sowieso nur Sinn, wenn alle PageFrames dahinter auch ausgelagert sind (du greifst auf die PT mindestens genauso oft zu wie auf die dahinterliegenden PageFrames). Also ja, sie KANN ausgelagert sein, wenn ihr das Auslagern von PageTables implementiert habt. Dann müsst ihr halt PT UND PageFrame einlagern.

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.