ĐẠI HỌC BÁCH KHOA HÀ NỘI

TRƯỜNG ĐIỆN-ĐIỆN TỬ

ET4291E: OPERATING SYSTEM

Topic:
1.Advanced scheduler.
2.Argument passing.
Instructor: Assoc.Prof.Pham Van Tien
Class: 144074
Student Name: Nguyen Van Viet Quang
Student ID: 20213583
 CONTENTS

I.PROBLEM INTRODUCTION .....................................................

1.1. Advanced Scheduler ............................................
1.2. Argument Passing ................................................
II. Advanced Scheduler ..................................................
2.1. Design .................................................................
2.2. Implementation...................................................
2.3. Result ..................................................................
III. Argument Passing
3.1. Design .................................................................
3.2. Implementation ..................................................
3.3. Result…………………………………...................
I.Problem Introduction
Pintos
Pintos is a small, educational operating system developed for
teaching purposes at Stanford University. It provides students
with hands-on experience in understanding the structure and
functioning of operating systems.
1.1. Advanced Scheduler

The primary goal of this project is to implement a multilevel

feedback queue scheduler, drawing inspiration from the 4.4BSD
scheduler, to enhance the system's efficiency and reduce the
average response time for job execution. Unlike the priority
scheduler, the advanced scheduler eliminates the need for
priority donation.
The codebase enables the selection of a scheduling algorithm
during Pintos startup, with the default option set to the priority
scheduler. Activation of the -mlfqs kernel option switches to the
4.4BSD scheduler. Under this scheduler, threads no longer exert
control over their priorities, rendering thread_set_priority()
ineffective. Instead, thread_get_priority() reflects the priority set
by the scheduler.
It's crucial to note that the advanced scheduler is exclusive to
this project and isn't utilized in subsequent ones, maintaining a
focused and modular approach.
1.2 Argument Passing
This section summarizes important points of the convention
used for normal function calls on 64-bit x86-64
implementations of Unix
In src/example,you need to ‘make’ and copy link of echo.exe
Currently, in the Pintos source code, the process_execute()
function does not support passing parameters new progress. So I
perform additional parsing of the input file name and refactor
the Stack. Then call it in the process_execute() function and run
the command pintos -q run ‘echo x’ with echo is a program to
print parameters to the screen

II. Advanced Scheduler

2.1. Design
a. Data Structure and Function
*In the thread.h, add in struct thread:

- int nice: Determines how considerate or "nice" a thread should

be towards other threads
- fixed_t recent_cpu: Measures the amount of CPU time a thread
has received recently, providing insight into its recent CPU
activity.
* In thread.c: Add a variable load_avg, which estimates the
average number of threads ready to run over the past minute.

b. Algorithms Advanced Scheduler

Different from priority scheduling task, there is no priority
donation in the MLFQ scheduler, as the priority of threads are
not set by users, but calculated by the OS itself.
Every thread has a nice value between -20 and 20 directly
under its control. Each thread also has a priority, between 0
(PRI_MIN) through 63 (PRI_MAX), which is recalculated
using the following formula every fourth tick:

priority = PRI_MAX - (recent_cpu / 4) - (nice * 2)

recent_cpu measures the amount of CPU time a thread has
received "recently." On each timer tick, the running thread's
recent cpu is incremented by 1. Once per second, every thread's
recent cpu is updated this way:

recent_cpu = (2 * load_avg) / (2 * load_avg + 1) * recent_cpu

+ nice
load_avg estimates the average number of threads ready to run
over the past minute. It is initialized to 0 at boot and
recalculated once per second as follows:
load_avg = (59/60) * load_avg + (1/60) * ready_threads

where ready_threads is the number of threads that are either

running or ready to run at time of update (not including the idle
thread).
In simple terms, here, 64 queues are maintained, with each
queue corresponding to a priority ranging from PRI_MIN to
PRI_MAX. The current priority of a thread is calculated using
specific formulas. During system scheduling, threads are
selected for execution starting from the highest priority queue.
The thread's priority dynamically changes with the operation of
the operating system. This calculation involves floatingpoint
arithmetic, which Pintos itself does not implement. Therefore, it
is necessary for us to handle this aspect independently.
2.2 Implementation
Firstly,we implement the thread_set_nice() funtion

We set the niceness value for current thread,call the MLFQS to

update the current thread .This function will recalculate the
thread’s priority based on the new niceness value according to
the formula described in the system. We also have the
thread_get_nice() function to get the niceness value

Secondly, we compute the priority:

Thirdly ,we calculating recent_cpu:
we implement the function thread_get_recent_cpu() that returns 100
times the value of the current string, rounded to the nearest integer.
recent_cpu

Finally, we calculating load_avg by a function.

This function is called once per second to update the load_avg
and recent_cpu values for all threads in the system.
Additionally, The fixed-point number calculations are defined as
macros in fixed_point.h:

2.3 Result
This is the result after the finished make check process:
Thus, the mlfqs test cases have been passed successfully, the
advanced scheduler works well.
III. Argument Passing
3.1. Design
a. Data Structure and Function
*In the process.c, add:
void parse_filename(char *src, char *dest) : shortens a file
name from an input string
void construct_esp(char *file_name, void **esp) : constructs a
stack frame index for user program execution
* tid_t process_excute() (const char *file_name)
• Parse the string of file_name
• Forward first token as name of new process to
thread_create() function
* static void start_process() (void *file_name_)
• Parse file_name
• Save tokens on user stack of new process.
* char *strtok_r (char *s, const char *delimiters, char
**save_ptr) /* string.h */
• Receive a string (s) and delimiters and parse them by
delimiters
* Thread name
• Before: Entire command line is passed to thread_create()
• After modification: Forward only first token of command
line to first argument of thread_create()
 “echo x y z” → only use “echo” for name of
process

* start_process (void *file_name_) :

• Allocate interrupt frame.
• Load program and initialize interrupt frame and user stack.
• Setup arguments at the user stack.
• Jump to the user program through interrupt_exit
* struct intr_frame():
• It is in the kernel stack.
• It stores user process’ registers.
* Load the program
• Pass the program name to ‘load()’.
• “load()” find executable file, using name of file and load it
onto memory.

b. Algorithms Advanced Scheduler

The Pintos C library for user programs designates _start(),
in lib/user/entry.c, as the entry point for user programs. This
function is a wrapper around main() that
calls exit() if main() returns:
The kernel must put the arguments for the initial function on
the register before it allows the user program to begin
executing. The arguments are passed in the same way as the
normal calling convention.
Consider how to handle arguments for the following example
command: /bin/ls -l foo bar.
1. Break the command into words: /bin/ls, -l, foo, bar.
2. Place the words at the top of the stack. Order doesn't
matter, because they will be referenced through pointers.
3. Push the address of each string plus a null pointer sentinel,
on the stack, in right-to-left order. These are the elements
of argv. The null pointer sentinel ensures
that argv[argc] is a null pointer, as required by the C
standard. The order ensures that argv[0] is at the lowest
virtual address. Word-aligned accesses are faster than
unaligned accesses, so for best performance round the
stack pointer down to a multiple of 8 before the first push.
4. Point %rsi to argv (the address of argv[0]) and
set %rdi to argc.
5. Finally, push a fake "return address": although the entry
function will never return, its stack frame must have the
same structure as any other.
The table below shows the state of the stack and the relevant
registers right before the beginning of the user program. Note
that the stack grows down.
3.2. Implementation:

• Print the program’s stack by using hex_dump()(stdio.h)

• Print memory dump in hexadecimal form
• Check if arguments are correctluy pushed on user stack.

• The three final steps can be combined into a single

command:
3.2. Result:
This is the result after the finished run ‘echo x’

At the time of submission, I'm still having some trouble with the
hex_dump() function to print the stack value and I'll still try to
fix it.

Link github:

Advanced Schedule: https://github.com/vitwag/os_advance_schedule.git

Argument Passing: https://github.com/vitwag/os_agrument_passing.git