Yitao's Blog

System Calls(pending the challenge) In the lab, we will get deeper into OS than the previous one. We are about to implement the ‘bridge’ between user and kernel mode, then implement two specific syscall to be called by user’s program. Lab The two labs are symmetry overall, so I just describe how to do a system call. To make our own syscalls,we should know how the syscall works between user & kernel mode. 1234567 user function ↓ wrapped interface---------------- ...

Xv6 and Unix utilities In this lab, we gonna implement many interesting and useful programs like, sleep, pingpong, primes, find, and xargs . There are some points I want to emphasize, though this lab is not so hard. Before Start My experiment environment: 12VM: VMware workstationLinux ubuntu 20.04 I can not find corresponding software in apt-get when my kernel was at 16.04 or 18.04, so I have to update to 20.04. Lab The structure we should know before programming is that, there are kernel’s ...

Crash RecoveryLoggingTo achieve a atomic transaction, xv6 use logging to avoid data inconsistence if crash happens while writing. XV6’s syscall won’t write through the inode’s block, instead, it writes ops into log, after the transaction is committed, then xv6 itself writes the log into disk. Log designDisk has a continuous space for logging storage, and consists of a header block foe meta info and a bunch of block copy. header block records block index and block number. In xv6, just one transa ...

Lab9 – MultithreadingUser thread implementationIn this section, we will implement a user-level thread. Like many user-level thread libraries do, it should have its ownpc, reregister and stack. For each thread, lab has already written the storage area in the struct thread. But because we still needs to save / restore the register through thread_switch, we also need a struct thread_context to store register status. 123456789101112131415161718struct thread_context{ uint64 ra; uint64 sp; / ...

Lab8 file systemLarge filesImplement “doubly-indirect” block in the inode, to make each inode be able to contain 256*256+256+11 blocks. Recall the definition of inode and how direct and indirect block works. This lab is much easy to accomplish. Just follow the hints and modify the dinode and inode for the new double-indirect block. Symbolic linksThe following sentence refers to manual page in linux of symlink. man symlink symlink() creates a symbolic link named linkpath which contains the strin ...

Lab4Part2 –Backtracebacktrace is the method that prints the address of call stack. To implement backtrace, we should know some key points : In RISC-V, stack grows from high to low. fp points to the start of a function(highest address), then Return Address (offset by -8), then previous frame pointer address(offset by -16) We should print the address of Return Address(means the address of code) Stack size are 1 PGSIZE and aligned. So we just need to fetch the frame pointer by the follower as ...

484. Find PermutationDescription Solution Recall how to generate a next_permutation, the way we do to keep the permutation small is just reverse the left-most reverse pair. In this question, we just keep a ‘123456… n’ basic permutation then reverse the substr that contiguous ‘D’ point at. eg. Code 1234567891011121314151617181920212223class Solution {public: vector<int> findPermutation(string s) { int n = s.size() + 1; vector<int> res; for(int i ...

757. Set Intersection Size At Least TwoDescription Solution Refer to 452 452. Minimum Number of Arrows to Burst Balloons. These two questions are very similar. We need to greedily find the maximum non-overlapping intervals. And the template should always sort the intervals by endpoints and see if we could pick elements greedily to fit the requirement. Code 12345678910111213141516171819202122232425262728class Solution {public: int intersectionSizeTwo(vector<vector<int>>&a ...

668. Kth Smallest Number in Multiplication Table Description Solution Generally, k-th related problem could be solved by binary search to guess the right answer and verify. Once we enumerate a number, we could calculate its rank. Another important thing we should notice is that we calculate the elements number that less equal than the target one. Code 123456789101112131415161718192021222324class Solution {public: int findKthNumber(int m, int n, int k) { int l = 1, r = ...

1235. Maximum Profit in Job Scheduling Description Solution Time interval question. An simple intuition should be, if we find a best solution for a previous time, then we could use this information to calculate the later one with startTime[i] > endTime[i-1]. So we could use binary search to find the endTime suitable for current startTime. To use bs, we need sort by endTime. Code 1234567891011121314151617181920212223242526272829303132class Solution {public: int jobScheduling(vect ...

1627. Graph Connectivity With Threshold Description Solution Obviously we need to use UF set. The problem here is how to enumerate the gcd of two number. I firstly just iterate n^2 numbers pairs and try to find their common factors and got TLE. –> We could start from the factor and to enumerate its multiples. Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950class UF{ public: vector<int> uf, size; UF(int n):uf(n), size ...

1944. Number of Visible People in a Queue Description Solution Using monotone stack, look into preceding first number larger than current one. Code 123456789101112131415161718class Solution {public: vector<int> canSeePersonsCount(vector<int>& heights) { int n = heights.size(); vector<int> res(n, 0); stack<int> stk; for(int i = n-1; i >= 0; i--){ while(!stk.empty() && stk.top() < heights[i])&# ...

798. Smallest Rotation with Highest Score Description Solution Let’s first check how many times we need take to move ith element to nums[i] position where is the first index that gets point. Take nums = [2,3,1,4, 0] as example: 12345A[0] = 2 move to 2's index, k = 3 = (0 - A[0] + 5) % 5 A[1] = 3 move to 3's index, k = 3 = (1 - A[1] + 5) % 5A[2] = 1 move to 1's index, k = 1 = (2 - A[2] + 5) % 5A[3] = 4 move to 4's index, k = 4 = (3 - A[3] + 5) % 5A[4] = 0 move to 0' ...

808. Soup Servings Description Solution In this problem, because all soup are decresed in multiple 25, so we could divid N by 25 then do dp on each one step. dp[i] [j] -> the desired value with i ml and j ml soup. 1dp[i][j] = 0.25 * (dp[i-4][j] + dp[i-3][j-1] + dp[i-2][j-2] + dp[i-1][j-3]) And we note the corner case are: 123dp[i][j] = 0.5 (for i <= 0 and j <= 0)dp[i][j] = 1 (for i = 0, j >= 1)dp[i][j] = 0 (for i >= 1, j = 0) Code 12345678910111213141516171819202122class ...

2002. Maximum Product of the Length of Two Palindromic Subsequences Description Solution We could enumerate all the potential substring then check if they are palindromic by using state compression. Then we iterate the subset of the inverse state to check if two substring are compatible. Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344class Solution {public: int maxProduct(string s) { int n = s.size(); vector<bool> dp(1 & ...