2018年4月23日 星期一

我回來了。


(中午休息阿比指我,殊不知另外四指指著自己 XD)

我回來了。


感謝大家願意等我回來。


這陣子花很多時間偷懶,花很多時間調適,因為安安來我們家當我們的寶貝,有時候小哭包一直哭一直哭,忍不住洩氣抱怨你到底要怎樣,也有時候半夜四點起來鬧,抱著走來走去泡牛奶躺在地墊玩,直到早上九點沿莉把我從深淵拯救出來,更有時候婆婆幫忙照顧安安,讓沿莉和我出來透風發呆。


可是想到自己可能比安安先走,又忍不住眼淚想哭。勞動法老師講課時告訴我們,他希望有生之年可以看到最低工資法過關,老師不是批評政府,而是期望自己長命百歲。這邊得到一個結論,盡量把身體弄健康點,就可以看久一點的沿莉和安安。


感謝賓賓體恤民心,願意開散步路線讓大家散散步。很努力跟上大家腳步(鑽芒草很像螞蟻在草地上那邊鑽來鑽去),很努力跟著大家聊天話題回憶什麼東西,很久沒出來走早已沒貨可以講(掩面),比較糟的行為是亂指路,大量預設散步等級的路在腦海,接著剔除路底太差的小路,然後發現沒路可走(被龍頭揪錯)。磺嘴山火山口是漂亮,可惜螞蟻看不到上帝視角,在冰島的時候很想繞大的火山口走一圈,結果到台灣磺嘴山的火山口,又嫌太累沒去走一圈,整個就是偷懶的人。


至少載三個人可以拿來說嘴。


下山送人回家,原本車上打算聽陳聰富講民總,結果只是聽著廣播累著發呆,我想感冒在家顧安安的沿莉應該更累。


感謝沿莉愛護安安,安安長大也會愛麻麻。

2018年4月13日 星期五

[Note] Some questions about threads & processes

1. Singleton pattern: https://en.wikipedia.org/wiki/Singleton_pattern

2. The difference between a process and a thread

Processes
  • Concept
    • A process is an instance of a program in execution.
    • Modern systems allow a single process to have multiple threads of execution, which execute concurrently.
  • Process Scheduling
    • The two main objectives of the process scheduling system are to keep the CPU busy at all times and to deliver "acceptable" response times for all programs, particularly for interactive ones.
    • The process scheduler must meet these objectives by implementing suitable policies for swapping processes in and out of the CPU.

(Quote from here)

Threads
  • Overview
    • A thread is a basic unit of CPU utilization, consisting of a program counter, a stack, and a set of registers, (and a thread ID.)
    • Traditional (heavyweight) processes have a single thread of control - There is one program counter, and one sequence of instructions that can be carried out at any given time.
  • Motivation
    • Threads are very useful in modern programming whenever a process has multiple tasks to perform independently of the others.
    • This is particularly true when one of the tasks may block, and it is desired to allow the other tasks to proceed without blocking. For example in a word processor, a background thread may check spelling and grammar while a foreground thread processes user input (keystrokes), while yet a third thread loads images from the hard drive, and a fourth does periodic automatic backups of the file being edited. 
    • Another example is a web server - Multiple threads allow for multiple requests to be satisfied simultaneously, without having to service requests sequentially or to fork off separate processes for every incoming request.
  • Benefits
    • Responsiveness - One thread may provide rapid response while other threads are blocked or slowed down doing intensive calculations.
    • Resource sharing - By default threads share common code, data, and other resources, which allows multiple tasks to be performed simultaneously in a single address space. 
    • Economy - Creating and managing threads is much faster than performing the same tasks for processes. 
    • Scalability, i.e. Utilization of multiprocessor architectures - A single threaded process can only run on one CPU, no matter how many may be available, whereas the execution of a multi-threaded application may be split amongst available processors.

Example: Chrome
  • Problem 
    • It's nearly impossible to build a rendering engine that never crashes or hangs. It's also nearly impossible to build a rendering engine that is perfectly secure. 
    • In some ways, the state of web browsers around 2006 was like that of the single-user, co-operatively multi-tasked operating systems of the past. As a misbehaving application in such an operating system could take down the entire system, so could a misbehaving web page in a web browser. All it took is one browser or plug-in bug to bring down the entire browser and all of the currently running tabs. 
    • Modern operating systems are more robust because they put applications into separate processes that are walled off from one another. A crash in one application generally does not impair other applications or the integrity of the operating system, and each user's access to other users' data is restricted.

3. The producer-consumer problem: race condition
  • In this condition a piece of code may or may not work correctly, depending on which of two simultaneous processes executes first, and more importantly if one of the processes gets interrupted such that the other process runs between important steps of the first process.
  • A specific example of a more general situation known as the critical section problem. 
  • A solution to the critical section problem must satisfy the following three conditions:
    • Mutual Exclusion - Only one process at a time can be executing in their critical section.
    • Progress - If no process is currently executing in their critical section, and one or more processes want to execute their critical section, then only the processes not in their remainder sections can participate in the decision, and the decision cannot be postponed indefinitely.
    • Bounded Waiting - There exists a limit as to how many other processes can get into their critical sections after a process requests entry into their critical section and before that request is granted.
  • Peterson's Solution
    • Peterson's Solution is a classic software-based solution to the critical section problem. It is unfortunately not guaranteed to work on modern hardware, due to vagaries of load and store operations.
  • Synchronization Hardware
    • To generalize the solution expressed above, each process when entering their critical section must set some sort of lock, to prevent other processes from entering their critical sections simultaneously, and must release the lock when exiting their critical section, to allow other processes to proceed. Obviously it must be possible to attain the lock only when no other process has already set a lock. 
  • Mutex Locks
    • The hardware solutions presented above are often difficult for ordinary programmers to access, particularly on multi-processor machines, and particularly because they are often platform-dependent.
    • Therefore most systems offer a software API equivalent called mutex locks or simply mutexes.
    • The terminology when using mutexes is to acquire a lock prior to entering a critical section, and to release it when exiting.
    • One problem with the implementation shown here is the busy loop used to block processes in the acquire phase. These types of locks are referred to as spinlocks, because the CPU just sits and spins while blocking the process. 
    • Spinlocks are wasteful of cpu cycles, and are a really bad idea on single-cpu single-threaded machines, because the spinlock blocks the entire computer, and doesn't allow any other process to release the lock.
    • On the other hand, spinlocks do not incur the overhead of a context switch, so they are effectively used on multi-threaded machines when it is expected that the lock will be released after a short time.
  • Semaphores
    • A more robust alternative to simple mutexes is to use semaphores, which are integer variables for which only two atomic operations are defined, the wait and signal operations.
    • Note that not only must the variable-changing steps (S-- and S++) be indivisible, it is also necessary that for the wait operation when the test proves false that there be no interruptions before S gets decremented.

4. Deadlocks
  • A set of processes is deadlocked when every process in the set is waiting for a resource that is currently allocated to another process in the set.
  • Necessary Conditions
    • Mutual Exclusion - At least one resource must be held in a non-sharable mode; If any other process requests this resource, then that process must wait for the resource to be released. 
    • Hold and Wait - A process must be simultaneously holding at least one resource and waiting for at least one resource that is currently being held by some other process. 
    • No preemption - Once a process is holding a resource, then that resource cannot be taken away from that process until the process voluntarily releases it. 
    • Circular Wait - A set of processes { P[0], P[1], P[2], ..., P[N] } must exist such that every P[i] is waiting for P[(i+1) % (N+1)]. 
  • Methods for Handling Deadlocks
    • Deadlock prevention or avoidance - Do not allow the system to get into a deadlocked state.
    • Deadlock detection and recovery - Abort a process or preempt some resources when deadlocks are detected.
    • Ignore the problem all together - If deadlocks only occur once a year or so, it may be better to simply let them happen and reboot as necessary than to incur the constant overhead and system performance penalties associated with deadlock prevention or detection.

5. Classical Synchronization Problems

References:

2018年4月7日 星期六

[Note] Competitive Programming Overview

Category:
  • Ad Hoc
    • Straightforward
    • Simulation
  • Complete Search
    • Iterative
    • Backtracking
  • Divide & Conquer
  • Greedy
    • Classic
    • Original
  • Dynamic Programming
    • Classic
      • Kadane's algorithm
    • Original
  • Graph
  • Mathematics
    • Factorial
    • Fibonacci Q-Matrix
  • String Processing
  • Computational Geometry
  • Otherwise

2018年3月31日 星期六

[Note #3][Algorithm] Kadane’s algorithm


Maximum subarray sum

Given an array of n numbers, our task is to calculate the maximum subarray sum, i.e., the largest possible sum of a sequence of consecutive values in the array.

1. Brute force: O(n^3) or O(n^2).

2. Divide and Conquer: O(n log(n)).

3. Kadane’s algorithm (Dynamic Programming): O(n)

int best = 0, sum = 0;
for (int k = 0; k < n; k++) {
    sum = max(array[k], sum + array[k]);
    best = max(best, sum);
}
cout << best << "\n";



[FWD] Book: Competitive Programming


First edition: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.457.3263&rep=rep1&type=pdf (The latest edition is the 3rd but not free in the Internet.)

Related book: Antti Laaksonen, Competitive Programmer’s Handbook. [PDF]