remzi-arpacidusseau / ostep-homework Goto Github PK

Was going through threads-intro/loop.s.
This is what it looks like:

.main
.top
sub  $1,%dx
test $0,%dx     
jgte .top         
halt

If I run: ./x86.py -p loop.s -t 1 -i 100 -R dx -c, I get the following output:

dx          Thread 0         
    0   
   -1   1000 sub  $1,%dx
   -1   1001 test $0,%dx
   -1   1002 jgte .top
   -1   1003 halt

My doubt is the following:
If dx is initialised to 0.
By 1001 test $0, %dx, it becomes -1, and here the constant 0 is greater than -1.
So in 1002 jgte .top should send the process in a loop, shouldn't it?
Or am I missing something?

I execute the program with the following parameters:

disk.py -a 30 -S 10 -c

Here is the answer that the program returns:
Block: 30 Seek: 8 Rotate:337 Transfer: 30 Total: 375
TOTALS Seek: 8 Rotate:337 Transfer: 30 Total: 375

Obviously, the seek time should be 20 as the head goes from the outer to the inner track.

Try different options they return wrong seek times as well.

Run relocation.py with the following arguments:

• physical memory size: 8
• address space size: 4
• base register: 7
• limit register: 2

and it reports that the address space does not fit into physical memory.

$ ./relocation.py -s 1 -p 8 -a 4 -b 7 -l 2

ARG seed 1
ARG address space size 4
ARG phys mem size 8

Base-and-Bounds register information:

  Base   : 0x00000007 (decimal 7)
  Limit  : 2

Error: address space does not fit into physical memory with those base/bounds values.
Base + Limit: 9   Psize: 8

Run it with these arguments:

• physical memory size: 8
• address space size: 4
• base register: 6
• limit register: 2

and it does not report an error.

$ ./relocation.py -s 1 -p 8 -a 4 -b 6 -l 2

ARG seed 1
ARG address space size 4
ARG phys mem size 8

Base-and-Bounds register information:

  Base   : 0x00000006 (decimal 6)
  Limit  : 2

Virtual Address Trace
  VA  0: 0x00000000 (decimal:    0) --> PA or segmentation violation?
  VA  1: 0x00000003 (decimal:    3) --> PA or segmentation violation?
  VA  2: 0x00000003 (decimal:    3) --> PA or segmentation violation?
  VA  3: 0x00000001 (decimal:    1) --> PA or segmentation violation?
  VA  4: 0x00000001 (decimal:    1) --> PA or segmentation violation?

For each virtual address, either write down the physical address it translates to
OR write down that it is an out-of-bounds address (a segmentation violation). For
this problem, you should assume a simple virtual address space of a given size.

This is confusing. Is the address space size defined by the limit register or the value of --asize/-a (address space size CLI argument)? In the examples above, since the address space size is explicitly set to 4 with the -a argument, I would expect both to throw the same error. Both are too close to the end of physical memory to fit an address space size of 4.

• Now my code env on Win is
  • win 64
  • vs code
  • MinGw
• I can run the simulator in chapter 4 on the Win platform without any problems
• But now the following error occurs in Chapter 5
  
• I found out after searching that this is not a Win library.What I need to do if I want to run on win (so I don't need to configure linux again)
• Also I would like to ask how to know when certain libraries are not available on win (like this #include <sys/wait.h>). Thanks you.

In the Chapter8's homework,mlfq.py seems to be have a little bug.
When reaching the time of BOOST(the parameters set by -B),the job in the list should be all be improved to the queue which has the highest priority and the ticksLeft should be reset to the quantum which has the highest priority ,but in the origin mlfq.py it is reset to the allotment(the parameters set by -a) of the queue.This causes the job to be executed by the CPU for only one time slice after returning to the highest priority queue(because the allotment is initialized to 1).
Bug part starts at line 244 in mlfq.py
# change priority to high priority # reset number of ticks left for all jobs (just for lower jobs?) # add to highest run queue (if not doing I/O) for j in range(numJobs): # print('-> Boost %d (timeLeft %d)' % (j, job[j]['timeLeft'])) if job[j]['timeLeft'] > 0: # print('-> FinalBoost %d (timeLeft %d)' % (j, job[j]['timeLeft'])) job[j]['currPri'] = hiQueue #job[j]['ticksLeft'] = allotment[hiQueue] job[j]['ticksLeft'] = quantum[hiQueue] #revise here # print('BOOST END: QUEUES look like:', queue)

Hello, I read the chapter 9 cpu-sched-lottery page 2,

Here is an example output of a lottery scheduler’s winning tickets:
    63 85 70 39 76 17 29 41 36 39 10 99 68 83 63 62 43 0 49. 
    Here is the resulting schedule:
    A   A   A     A   A   A   A   A   A       A        A   A   A   A   A
      B         B                          B       B

I find the number of tickets is 19, not 20.
the description below the example use the number of tickets is 20. which is
"In our example above, B only get to run 4 our of 20 time slices(20%), instead of the desired 25% allocation."
the example may miss a ticket for A.

I attempted to do homework, task 4 from the chapter "Condition Variables":

Let’s look at some timings. How long do you think the following execution, with one producer, three consumers, a single-entry
shared buffer, and each consumer pausing at point c3 for a second, will take? ./main-two-cvs-while -p 1 -c 3 -m 1 -C 0,0,0,1,0,0,0:0,0,0,1,0,0,0:0,0,0,1,0,0,0 -l 10 -v -t

When I launch main-one-cv-while.c using this code, the program seems to fall into the deadlock:

NF P0 C0 C1 C2
0 [--- ] p0
0 [--- ] p1
1 [* 0 ] p4
1 [* 0 ] p5
1 [* 0 ] p6
1 [* 0 ] p0
1 [* 0 ] p1
1 [* 0 ] p2
1 [* 0 ] c0
1 [* 0 ] c1
0 [--- ] c4
0 [--- ] c5
0 [--- ] c6
0 [--- ] c0
0 [--- ] c0
0 [--- ] p3
1 [* 1 ] p4
1 [* 1 ] p5
1 [* 1 ] c0
1 [* 1 ] p6
1 [* 1 ] p0
1 [* 1 ] c1
0 [--- ] c4
0 [--- ] c5
0 [--- ] c6
0 [--- ] c0
0 [--- ] c1
0 [--- ] c2
0 [--- ] c1
0 [--- ] c2
0 [--- ] p1
1 [ 2 ] p4
1 [* 2 ] p5
1 [* 2 ] p6
1 [* 2 ] p0
1 [* 2 ] c1
0 [--- ] c4
0 [--- ] c5
0 [--- ] c6
0 [--- ] c3
0 [--- ] c2
0 [--- ] c0
0 [--- ] p1
1 [ 3 ] p4
1 [* 3 ] p5
1 [* 3 ] p6
1 [* 3 ] p0
1 [* 3 ] c3
0 [--- ] c4
0 [--- ] c5
0 [--- ] c6
0 [--- ] c0
0 [--- ] c1
0 [--- ] c2
0 [--- ] c3
0 [--- ] c2
0 [--- ] p1
1 [ 4 ] p4
1 [* 4 ] p5
1 [* 4 ] p6
1 [* 4 ] p0
1 [* 4 ] c1
0 [--- ] c4
0 [--- ] c5
0 [--- ] c6
0 [--- ] c0
0 [--- ] c3
0 [--- ] c2
0 [--- ] p1
1 [ 5 ] p4
1 [* 5 ] p5
1 [* 5 ] p6
1 [* 5 ] p0
1 [* 5 ] c3
0 [--- ] c4
0 [--- ] c5
0 [--- ] c6
0 [--- ] c0
0 [--- ] c1
0 [--- ] c2
0 [--- ] c3
0 [--- ] c2
0 [--- ] p1
1 [ 6 ] p4
1 [* 6 ] p5
1 [* 6 ] p6
1 [* 6 ] p0
1 [* 6 ] c1
0 [--- ] c4
0 [--- ] c5
0 [--- ] c6
0 [--- ] c0
0 [--- ] c3
0 [--- ] c2
0 [--- ] p1
1 [ 7 ] p4
1 [* 7 ] p5
1 [* 7 ] p6
1 [* 7 ] p0
1 [* 7 ] c3
0 [--- ] c4
0 [--- ] c5
0 [--- ] c6
0 [--- ] c0
0 [--- ] c1
0 [--- ] c2
0 [--- ] c3
0 [--- ] c2
0 [--- ] p1
1 [ 8 ] p4
1 [* 8 ] p5
1 [* 8 ] p6
1 [* 8 ] p0
1 [* 8 ] c1
0 [--- ] c4
0 [--- ] c5
0 [--- ] c6
0 [--- ] c0
0 [--- ] c3
0 [--- ] c2
0 [--- ] p1
1 [ 9 ] p4
1 [* 9 ] p5
1 [* 9 ] p6
1 [* 9 ] c3
0 [--- ] c4
0 [--- ] c5
0 [--- ] c6
0 [--- ] c0
0 [--- ] c1
0 [--- ] c2
0 [--- ] c3
0 [--- ] c2
1 [EOS ] [main: added end-of-stream marker]
1 [EOS ] c1
0 [--- ] c4
0 [--- ] c5
0 [--- ] c6
0 [--- ] c3
0 [--- ] c2
0 [--- ] c3
0 [*--- ] c2

It stucks on the last operation and doesn't finish.

for example
moocos-> python3 process-run.py -l 3:0 -L 5 -c -p
Time PID: 0 CPU IOs
1 RUN:io 1
2 WAITING 1
3 WAITING 1
4 WAITING 1
5 WAITING 1
6* RUN:io 1
7 WAITING 1
8 WAITING 1
9 WAITING 1
10 WAITING 1
11* RUN:io 1
12 WAITING 1
13 WAITING 1
14 WAITING 1
15 WAITING 1
16* DONE 1
Stats: Total Time 16
Stats: CPU Busy 4 (25.00%)
Stats: IO Busy 12 (75.00%)

why 16rows output 1 in CPU cols? The cpu Busy is not equal to 18.75%.

Okay, so, I am having some trouble understanding the trace. Here's the setup - 2 queues, 2 jobs - one CPU bound (no IO) with runtime 9 and another with IO frequency 2 (duration 1) and runtime 4. Quantum is 3 for each of the queues, allotment 1. We do Stay and Boost priorities every 5 seconds.

$ ./mlfq.py -n 2 -l 0,9,0:0,4,2 -q 3 -c -i 1 -S -B 5
Here is the list of inputs:
OPTIONS jobs 2
OPTIONS queues 2
OPTIONS allotments for queue  1 is   1
OPTIONS quantum length for queue  1 is   3
OPTIONS allotments for queue  0 is   1
OPTIONS quantum length for queue  0 is   3
OPTIONS boost 5
OPTIONS ioTime 1
OPTIONS stayAfterIO True
OPTIONS iobump False


For each job, three defining characteristics are given:
  startTime : at what time does the job enter the system
  runTime   : the total CPU time needed by the job to finish
  ioFreq    : every ioFreq time units, the job issues an I/O
              (the I/O takes ioTime units to complete)

Job List:
  Job  0: startTime   0 - runTime   9 - ioFreq   0
  Job  1: startTime   0 - runTime   4 - ioFreq   2


Execution Trace:

[ time 0 ] JOB BEGINS by JOB 0
[ time 0 ] JOB BEGINS by JOB 1
[ time 0 ] Run JOB 0 at PRIORITY 1 [ TICKS 2 ALLOT 1 TIME 8 (of 9) ]
[ time 1 ] Run JOB 0 at PRIORITY 1 [ TICKS 1 ALLOT 1 TIME 7 (of 9) ]
[ time 2 ] Run JOB 0 at PRIORITY 1 [ TICKS 0 ALLOT 1 TIME 6 (of 9) ]
[ time 3 ] Run JOB 1 at PRIORITY 1 [ TICKS 2 ALLOT 1 TIME 3 (of 4) ]
[ time 4 ] Run JOB 1 at PRIORITY 1 [ TICKS 1 ALLOT 1 TIME 2 (of 4) ]
[ time 5 ] IO_START by JOB 1
IO DONE
[ time 5 ] BOOST ( every 5 )
[ time 5 ] Run JOB 0 at PRIORITY 1 [ TICKS 0 ALLOT 1 TIME 5 (of 9) ]
[ time 6 ] IO_DONE by JOB 1
[ time 6 ] Run JOB 1 at PRIORITY 1 [ TICKS 0 ALLOT 1 TIME 1 (of 4) ]
[ time 7 ] Run JOB 0 at PRIORITY 0 [ TICKS 2 ALLOT 1 TIME 4 (of 9) ]
[ time 8 ] Run JOB 0 at PRIORITY 0 [ TICKS 1 ALLOT 1 TIME 3 (of 9) ]
[ time 9 ] Run JOB 0 at PRIORITY 0 [ TICKS 0 ALLOT 1 TIME 2 (of 9) ]
[ time 10 ] BOOST ( every 5 )
[ time 10 ] Run JOB 1 at PRIORITY 1 [ TICKS 0 ALLOT 1 TIME 0 (of 4) ]
[ time 11 ] FINISHED JOB 1
[ time 11 ] Run JOB 0 at PRIORITY 1 [ TICKS 0 ALLOT 1 TIME 1 (of 9) ]
[ time 12 ] Run JOB 0 at PRIORITY 0 [ TICKS 2 ALLOT 1 TIME 0 (of 9) ]
[ time 13 ] FINISHED JOB 0

Final statistics:
  Job  0: startTime   0 - response   0 - turnaround  13
  Job  1: startTime   0 - response   3 - turnaround  11

  Avg  1: startTime n/a - response 1.50 - turnaround 12.00

At time 5, why is TICKS 0? Since JOB 0 just got switched in, shouldn't it have the entire quantum? Same at time 6.

I am not clear about direct mapping... Based on the simulator output for the following run, it seems writing twice to the same block but on different pages invokes two block erases.

> ./ssd.py -T direct -s 2 -n 10 -C -S -F

ARG seed 2
ARG num_cmds 10
ARG op_percentages 40/50/10
ARG skew 
ARG skew_start 0
ARG read_fail 0
ARG cmd_list 
ARG ssd_type direct
ARG num_logical_pages 80
ARG num_blocks 12
ARG pages_per_block 10
ARG high_water_mark 10
ARG low_water_mark 8
ARG erase_time 1000
ARG program_time 40
ARG read_time 10
ARG show_gc False
ARG show_state False
ARG show_cmds True
ARG quiz_cmds False
ARG show_stats True
ARG compute False

FTL   (empty)
Block 0          1          2          3          4          5          6          7          8          9          10         11         
Page  0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 1111111111 1111111111 
      0000000000 1111111111 2222222222 3333333333 4444444444 5555555555 6666666666 7777777777 8888888888 9999999999 0000000000 1111111111 
      0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 
State iiiiiiiiii iiiiiiiiii iiiiiiiiii iiiiiiiiii iiiiiiiiii iiiiiiiiii iiiiiiiiii iiiiiiiiii iiiiiiiiii iiiiiiiiii iiiiiiiiii iiiiiiiiii 
Data                                                                                                                                      
Live                                                                                                                                      

cmd   0:: write(58, F) -> success
cmd   1:: write(46, 9) -> success
cmd   2:: write(31, I) -> success
cmd   3:: trim(31) -> success
cmd   4:: write(35, g) -> success
cmd   5:: read(46) -> 9
cmd   6:: read(35) -> g
cmd   7:: write(44, e) -> success
cmd   8:: read(58) -> F
cmd   9:: write(79, F) -> success

FTL    35: 35  44: 44  46: 46  58: 58  79: 79 
Block 0          1          2          3          4          5          6          7          8          9          10         11         
Page  0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 1111111111 1111111111 
      0000000000 1111111111 2222222222 3333333333 4444444444 5555555555 6666666666 7777777777 8888888888 9999999999 0000000000 1111111111 
      0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 
State iiiiiiiiii iiiiiiiiii iiiiiiiiii EvEEEvEEEE EEEEvEvEEE EEEEEEEEvE iiiiiiiiii EEEEEEEEEv iiiiiiiiii iiiiiiiiii iiiiiiiiii iiiiiiiiii 
Data                                    I   g         e 9            F                      F                                             
Live                                        +         + +            +                      +                                             

Physical Operations Per Block
Erases   0          0          0          2          2          1          0          1          0          0          0          0          Sum: 6
Writes   0          0          0          3          3          1          0          1          0          0          0          0          Sum: 8
Reads    0          0          0          2          2          1          0          0          0          0          0          0          Sum: 5

Logical Operation Sums
  Write count 6 (0 failed)
  Read count  3 (0 failed)
  Trim count  1 (0 failed)

Times
  Erase time 6000.00
  Write time 320.00
  Read time  50.00
  Total time 6370.00

In the above, w46:9, w44:e, should only require one erase, as page 44 is already erased (after w46:9) and therefore writeable without an erase

In order for the syscall and context switching measurement to be correct (or sufficiently so):

• must we disable cpu's frequency variation (affects "rdtsc")?
• must we utilize core affinity?
• must we isolate the core used to run the measurement on (so the OS does not run anything else on the core we'll use for the measurement) ?
• disable timer interrupt altogether so that a timer interrupt cannot occur during context switching? (according to the chapter, the OS might disable interrupts when servicing an interrupt. Can we assume that during measurement? Also is it even applicable to the case?)

Also what is an acceptable variance value for the measurement?

In the raid.py simulator, we tried the following: python raid.py -L 1 -c

One address to compute were 6183. With our understanding, you are supposed to compute the disc number with address % number_of_discs

Following addresses are located on other discs as computed:

4205 1
LOGICAL READ from addr:4205 size:4096
  read  [disk 2, offset 2102]
----> 4205 % 4 = 1

9097 1
LOGICAL READ from addr:9097 size:4096
  read  [disk 2, offset 4548]  
----> 9097 % 4 = 1

Are we calculating wrong?

From paging-linear-translate.py i got a Page Table as follows:

Page Table (from entry 0 down to the max size)
  [       0]  0x8000000c
  [       1]  0x00000000
  [       2]  0x00000000
  [       3]  0x80000006

After calculate the VPN is 3, the PFN is 0x80000006. But in README.md the PFN is 0x6. Does it wrong?

Are there any correct answers of the questions? I have some trouble dealing with them but don't know how. Thank you.

cpu-intro/process-run.py

By supplying a seed, I get no effect - i.e. no random jobs/processes seem to be generated.

Expected behavior: random processes/jobs created based on seed supplied.

I had a few questions about running these programs -

1. Will these scripts work on any OS or just linux?
2. Is it safe to run these scripts on my actual laptop or is there a chance that something will get messed up? As of right now I'm using a virtual machine.

./mlfq.py -l 0,150,0:100,50,5:100,50,5 -q 10 -n 3 -i 5 -S -B 50 -c

result:

...
[ time 50 ] BOOST ( every 50 )
[ time 50 ] Run JOB 0 at PRIORITY 2 [ TICKS 0 ALLOT 1 TIME 99 (of 150) ]
[ time 51 ] Run JOB 0 at PRIORITY 1 [ TICKS 9 ALLOT 1 TIME 98 (of 150) ]
...

After boost, only one run at PRIORITY 2?

• I'm trying to answer the homework in the book, but I always run into some questions (for example, my written answers don't match the computer answers). So I am wondering if there is a forum where I can discuss these questions? Please tell me, Thanks!
• ex. Question 1 of Homework 17th Free Space. Why the value of sz is 88(I think is 92). I don't know why and I want to figure it.
  

Ran main-two-cvs-while with the following arguments:
./main-two-cvs-while -l 5 -m 2 -p 1 -c 1 -v

1 producer, 1 consumer, buffer size of 2 and loops 5 times.

Every alternate run produces the following output:

Isn't the sequence of c0, p0, c1, c2, p1, p4 .. an incorrect locking mechanism?

Screenshot of the code:

Consumer acquires lock at c1, sleeps at the while loop at c2 and then we context switch to the producer, which seems to acquire the lock at p1? If consumer hasn't released the lock yet, how's this possible? It'd have made sense if the consumer had gotten to c3 (cond_wait - where it'd sleep and release the lock which the producer could have then acquired in p1)

Am I missing something obvious?

There seems to be a mistake when boosting jobs to high priority queue:
for j in range(numJobs):
# print('-> Boost %d (timeLeft %d)' % (j, job[j]['timeLeft']))
if job[j]['timeLeft'] > 0:
# print('-> FinalBoost %d (timeLeft %d)' % (j, job[j]['timeLeft']))
job[j]['currPri'] = hiQueue
job[j]['ticksLeft'] = allotment[hiQueue]

To my limited understanding, allotment[i] represents number of quantum you have in queue i, so here is a 'type mismatch' bug.
To make it right: job[j]['ticksLeft'] = quantum[hiQueue]

Or maybe I failed to fully understand the program... In that case, any insight/correction is welcomed.
If I'm right, hope it get fixed so everyone doing ex5 in ch8 has no need to come through it again.

The second example on the README (./segmentation.py -s 100 -a 16 -p 32) throws an error that stems from line 87, where the program checks if the physical memory is 2X larger than the address space.
Could the condition be at least 2X larger: psize < 2 * asize?

In the book, the homework for Chapter 41 uses -I as argument for ffs.py in order to change the size of the inode table (questions 6 and 7).

This is presumably a typo: the script ffs.py uses argument -i for the number of inodes per group, -I is used for spreading the inodes.

When I write code in "p4.c" like:

close(STDOUT_FILENO);
open("./info.output", O_CREAT | O_WRONLY | O_TRUNC, S_IRWXU);

I can't get the output of another programme which i want to execute in the subprocess with system call "execvp" from "info.output", but when i write the above code in another file (like "wc.c"), it recovers normal.
So, i want to know whether i write wrong code or the book with something wrong.

all code i write:
p2.c

#include "stdio.h"
#include "stdlib.h"
#include "unistd.h"
#include "string.h"
#include "sys/wait.h"
#include "fcntl.h"

int main(int argc, char **argv){
    printf("hello world (pid:%d)\n", (int)getpid());
    int rc = fork();
    if(rc < 0){
        fprintf(stderr, "fork failed\n");
        exit(1);
    }else if(rc == 0){
        printf("hello, I am child (pid:%d)\n", (int)getpid());
        //if i write them here, i can't get output from info.output
        //close(STDOUT_FILENO);
        //open("./info.output", O_CREAT | O_WRONLY | O_TRUNC, S_IRWXU);
        char *myargs[3];
        myargs[0] = strdup("./test");

        if(myargs[0] == NULL){
            fprintf(stderr, "malloc failed");
        }

        myargs[1] = strdup("--parameter");
        if(myargs[1] == NULL){
            fprintf(stderr, "malloc failed");
        }

        myargs[2] = NULL;
        execvp(myargs[0], myargs);
        printf("this statement shouldn't be executed");
    }else{
        //wait subprocess to finish, return pid of subprocess
        int wc = wait(NULL);
        printf("%d\n", wc);
        printf("hello, I am parent of %d (pid:%d)\n", rc, (int)getpid());
    }
    return 0;
}

test.c

#include "stdio.h"
#include "stdlib.h"
#include "unistd.h"
#include "string.h"
#include "sys/wait.h"
#include "fcntl.h"

int main(int argc, char **argv){
    if(argc == 1){
        fprintf(stderr, "need a argument but no parameter");
        exit(1);
    }
//when i write them here, it's normal
    close(STDOUT_FILENO);
    open("./info.output", O_CREAT | O_WRONLY | O_TRUNC, S_IRWXU);
    for(int i = 1; i < argc; i++){
        printf("%s\n", argv[i]);
    }
    return 0;
}