# Image和skimage读图片 import Image as img import os from matplotlib import pyplot as plot from skimage import io,transform img_file1 = img.open('./CXR_png/MCUCXR_0042_0.png') img_file2 = io.imread('./CXR_png/MCUCXR_0042_0.png')
from PIL import Image import matplotlib.pyplot as plt img=Image.open('d:/ex.jpg') gray=img.convert('L') plt.figure("beauty") plt.imshow(gray,cmap='gray') plt.axis('off') plt.title('The color image to gray image') plt.show()
file_num = len(sys.argv) - 2; quali = int(sys.argv[1]) file_list = sys.argv[2:] print(file_list) min_height=999999 sum_width = 0 img_list=[] for file_name in file_list: img = Image.open(file_name) img_list.append(img) if(img.size[1]<min_height): min_height = img.size[1] sum_width = sum_width + img.size[0] print("asdf") out_list=[] for file_name in file_list: img = Image.open(file_name) out = img.resize((img.size[0],min_height),Image.ANTIALIAS) #resize image with high-quality out.save(file_name)
target = Image.new('RGB',(sum_width,min_height)) left = 0 right = 0 for file_name in file_list: image = Image.open(file_name) right += image.size[0] target.paste(image,(left,0,right,min_height)) print("aaa") left += image.size[0] #right += image.size[1]
file_num = len(sys.argv) - 2 quali = int(sys.argv[1]) file_list = sys.argv[2:] print(file_list) min_width=999999 sum_height = 0 img_list=[] for file_name in file_list: img = Image.open(file_name) img_list.append(img) if(img.size[0]<min_width): min_width = img.size[0] sum_height = sum_height + img.size[1] print("asdf") out_list=[] for file_name in file_list: img = Image.open(file_name) out = img.resize((min_width,img.size[1]),Image.ANTIALIAS) #resize image with high-quality out.save(file_name)
target = Image.new('RGB',(min_width,sum_height)) left = 0 right = 0 for file_name in file_list: image = Image.open(file_name) right += image.size[1] target.paste(image,(0,left,min_width,right)) print("aaa") left += image.size[1] #right += image.size[1]
import matplotlib.image as mpimg from PIL import Image lena = mpimg.imread('lena.png') # 这里读入的数据是 float32 型的,范围是0-1 im = Image.fromarray(np.uinit8(lena*255)) im.show()
from PIL import Image import numpy as np import matplotlib.pyplot as plt img=np.array(Image.open('d:/ex.jpg'))
#随机生成5000个椒盐 rows,cols,dims=img.shape for i in range(5000): x=np.random.randint(0,rows) y=np.random.randint(0,cols) img[x,y,:]=255 plt.figure("beauty") plt.imshow(img) plt.axis('off') plt.show()
例2:将lena图像二值化,像素值大于128的变为1,否则变为0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
from PIL import Image import numpy as np import matplotlib.pyplot as plt img=np.array(Image.open('d:/pic/lena.jpg').convert('L'))
rows,cols=img.shape for i in range(rows): for j in range(cols): if (img[i,j]<=128): img[i,j]=0 else: img[i,j]=1 plt.figure("lena") plt.imshow(img,cmap='gray') plt.axis('off') plt.show()
''' Load the image files form the folder input: imgDir: the direction of the folder imgName:the name of the folder output: data:the data of the dataset label:the label of the datset ''' defload_Img(imgDir,imgFoldName): imgs = os.listdir(imgDir+imgFoldName) imgNum = len(imgs) data = np.empty((imgNum,1,12,12),dtype="float32") label = np.empty((imgNum,),dtype="uint8") for i inrange (imgNum): img = Image.open(imgDir+imgFoldName+"/"+imgs[i]) arr = np.asarray(img,dtype="float32") data[i,:,:,:] = arr label[i] = int(imgs[i].split('.')[0]) return data,label
NETCDF3_CLASSIC was the original netcdf binary format, and was limited to file sizes less than 2 Gb.
NETCDF3_64BIT_OFFSET was introduced in version 3.6.0 of the library, and extended the original binary format to allow for file sizes greater than 2 Gb.
NETCDF3_64BIT_DATA is a new format that requires version 4.4.0 of the C library - it extends the NETCDF3_64BIT_OFFSET binary format to allow for unsigned/64 bit integer data types and 64-bit dimension sizes.
NETCDF3_64BIT is an alias for NETCDF3_64BIT_OFFSET.
NETCDF4_CLASSIC files use the version 4 disk format (HDF5), but omits features not found in the version 3 API. They can be read by netCDF 3 clients only if they have been relinked against the netCDF 4 library. They can also be read by HDF5 clients. NETCDF4 files use the version 4 disk format (HDF5) and use the new features of the version 4 API. The netCDF4 module can read and write files in any of these formats. When creating a new file, the format may be specified using the format keyword in the Dataset constructor. The default format is NETCDF4. To see how a given file is formatted, you can examine the data_model attribute.
Closing the netCDF file is accomplished via the Dataset.close method of the Dataset instance.
ncdimensions = nc.dimensions for dim in nc.dimensions.values(): newncdim_sample = newnc.createDimension(dim.name, dim.size)
for var in nc.variables.values(): print(var) print(var.datatype) print(var.ncattrs()) print(var.dimensions) new_var = newnc.createVariable(var.name, var.datatype, var.dimensions, shuffle=False) for attr in var.ncattrs(): new_var.setncattr(attr, var.getncattr(attr)) newnc[var.name][:] = nc[var.name][:]
for attr in nc.ncattrs(): newnc.setncattr(attr,nc.getncattr(attr))
begin transaction update account set money= money - 100where name='A'; update account set money= money +100where name='B'; if Error then rollback else commit
要取的字段、索引的类型,和这两个也是有关系的。举个例子,对于user表,有name和phone的联合索引,select name from user where phone=12345678912 和 select * from user where phone=12345678912,前者要比后者的速度快,因为name可以在索引上直接拿到,不再需要读取这条记录了。
class Lock { int value = 0; } Lock::Acquire() { while(test_and_set(value)) ; // spin } Lock::Release() { value = 0; }
用TS指令把value读出来,向里边写入1。
如果锁被释放,那么TS指令读取0并将值设置为1
锁被设置为忙并且需要等待完成
如果锁处于忙状态,那么TS指令读取1并将指令设置为1
不改变锁的状态并且需要循环
无忙等待锁:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
class Lock { int value = 0; WaitQueue q; } Lock::Acquire() { while(test_and_set(value)){ add this TCP to wait queue schedule(); } } Lock::Release() { value = 0; remove one thread t from q wakeup(t) }
class Semaphore{ int sem; WaitQueue q; } Semaphore::P(){ sem --; if(sem<0){ Add this thread t to q; block(p) } } Semaphore::V(){ sem++; if(sem<=0){ remove a thread t from q; wakeup(t) } }
BounderBuffer::Deposit(c){ emptyBuffers->P(); mutex->P(); Add c to the buffer mutex->V(); fullBuffers->V();//生产者写了之后就释放一个资源 } BounderBuffer::Remove(c){ fullBuffers->P(); mutex->P(); Remove c from buffer mutex->V(); emptyBuffers->V();//消费者用了一个之后释放一个 }
Class Condition{ int numWaiting = 0; WaitQueue q; } Condition::Wait(lock){ numWaiting ++; Add this thread t to q; release(); schedule(); require(lock); } Condition::Signal(){ if(numWaiting > 0){ Remove a thread t from q; wakeup(t); numWaiting --; } }
class Semaphore{ int sem; WaitQueue q; } Semaphore::P(){ sem --; if(sem<0){ Add this thread t to q; block(t); } } Semaphore::V(){ sem++; if(sem<=0){ Remove a thread t from q; wakeup(t); } }
bootblock需要一些.o文件,makefile里的foreach有如下格式:$(foreach < var >,< list >,< text >)
这个函数的意思是,把参数< list >;中的单词逐一取出放到参数< var >所指定的变量中,然后再执行< text>;所包含的表达式。每一次< text >会返回一个字符串,循环过程中,< text >的所返回的每个字符串会以空格分隔,最后当整个循环结束时,< text >所返回的每个字符串所组成的整个字符串(以空格分隔)将会是foreach函数的返回值。
void print_stackframe(void) { /* (1) call read_ebp() to get the value of ebp. the type is (uint32_t); * (2) call read_eip() to get the value of eip. the type is (uint32_t); * (3) from 0 .. STACKFRAME_DEPTH * (3.1) printf value of ebp, eip * (3.2) (uint32_t)calling arguments [0..4] = the contents in address (uint32_t)ebp +2 [0..4] * (3.3) cprintf("\n"); * (3.4) call print_debuginfo(eip-1) to print the C calling function name and line number, etc. * (3.5) popup a calling stackframe * NOTICE: the calling funciton's return addr eip = ss:[ebp+4] * the calling funciton's ebp = ss:[ebp] */ uint32_t my_ebp = read_ebp(); uint32_t my_eip = read_eip();//读取当前的ebp和eip int i,j; for(i = 0; my_ebp!=0 && i< STACKFRAME_DEPTH; i++){ cprintf("%0x %0x\n",my_ebp,my_eip); for(j=0;j<4;j++){ cprintf("%0x\t",((uint32_t*)my_ebp+2)[j]); } cprintf("\n"); print_debuginfo(my_eip-1); my_ebp = ((uint32_t*)my_ebp)[0]; my_eip = ((uint32_t*)my_ebp)[1]; } }
SETGATE设置中断向量表将每个中断处理例程的入口设成vector[i]的值,然后在有中断时,找到中断向量表中这个中断的处理例程,都是跳到alltraps,__alltraps把寄存器(ds es fs gs)压栈,把esp压栈,这样假装构造一个trapframe然后调用trap,trap调用了trap_dispatch
cprintf("e820map:\n"); int i; for (i = 0; i < memmap->nr_map; i ++) { uint64_t begin = memmap->map[i].addr, end = begin + memmap->map[i].size; cprintf(" memory: %08llx, [%08llx, %08llx], type = %d.\n", memmap->map[i].size, begin, end - 1, memmap->map[i].type); if (memmap->map[i].type == E820_ARM) { if (maxpa < end && begin < KMEMSIZE) { maxpa = end; } } } if (maxpa > KMEMSIZE) { maxpa = KMEMSIZE; }
externchar end[];
npage = maxpa / PGSIZE; //起始物理内存地址位0,所以需要管理的页个数为npage,需要管理的所有页的大小位sizeof(struct Page)*npage pages = (struct Page *)ROUNDUP((void *)end, PGSIZE); // pages的地址,最末尾地址按照页大小取整。 for (i = 0; i < npage; i ++) { SetPageReserved(pages + i); } //当前的这些页设置为已占用的
for (i = 0; i < memmap->nr_map; i ++) { uint64_t begin = memmap->map[i].addr, end = begin + memmap->map[i].size; if (memmap->map[i].type == E820_ARM) { if (begin < freemem) { begin = freemem; } if (end > KMEMSIZE) { end = KMEMSIZE; } if (begin < end) { begin = ROUNDUP(begin, PGSIZE); end = ROUNDDOWN(end, PGSIZE); if (begin < end) { init_memmap(pa2page(begin), (end - begin) / PGSIZE); // 通过调用本函数进行空闲的标记 } } } } }
/* 将这个le转换成一个Page */ #define le2page(le, member) \ to_struct((le), struct Page, member) /* * * to_struct - get the struct from a ptr * @ptr: a struct pointer of member * @type: the type of the struct this is embedded in * @member: the name of the member within the struct * 一般用的时候传进来的type是Page类型的,ptr是这个(Page+双向链表的两个指针)块的双向链表指针的开始地址。offsetof算出了page_link在Page中的偏移值,ptr减去双向链表第一个指针的偏移量得到了这个Page的地址 */ #define to_struct(ptr, type, member) \ ((type *)((char *)(ptr) - offsetof(type, member)))
/* Return the offset of 'member' relative to the beginning of a struct type */ 0不代表具体地址,这个offsetof代表这个member在这个type中的偏移值 #define offsetof(type, member) \ ((size_t)(&((type *)0)->member))
A linear address 'la' has a three-part structure as follows: +--------10------+-------10-------+---------12----------+ | Page Directory | Page Table | Offset within Page | | Index | Index | | +----------------+----------------+---------------------+ \--- PDX(la) --/ \--- PTX(la) --/ \---- PGOFF(la) ----/ \----------- PPN(la) -----------/ The PDX, PTX, PGOFF, and PPN macros decompose linear addresses as shown. To construct a linear address la from PDX(la), PTX(la), and PGOFF(la), use PGADDR(PDX(la), PTX(la), PGOFF(la)).
//get_pte - get Page Table Entry and return the kernel virtual address of this Page Table Entry for la // - if the PT contians this Page Table Entry didn't exist, alloc a page for PT // parameter: // pgdir: the kernel virtual base address of PDT (页目录表的入口) // la: the linear address need to map (线性地址) // create: a logical value to decide if alloc a page for PT // return vaule: the kernel virtual address of this pte (返回这个页表项的虚拟地址) pte_t * get_pte(pde_t *pgdir, uintptr_t la, bool create) { /* * 使用KADDR()获得物理地址 * PDX(la) = 虚拟地址la在page directory entry 的 index * KADDR(pa) : takes a physical address and returns the corresponding kernel virtual address. * set_page_ref(page,1) : means the page be referenced by one time,这一页被引用了 * page2pa(page): get the physical address of memory which this (struct Page *) page manages * 得到这个页管理的内存的物理地址 * struct Page * alloc_page() : allocation a page * memset(void *s, char c, size_t n) : sets the first n bytes of the memory area pointed by s * to the specified value c. * DEFINEs: * PTE_P 0x001 // page table/directory entry flags bit : Present * PTE_W 0x002 // page table/directory entry flags bit : Writeable * PTE_U 0x004 // page table/directory entry flags bit : User can access */
pde_t *pdep = &pgdir[PDX(la)]; // (1) find page directory entry structPage *page; if (!(*pdep & PTE_P) ) { // (2) check if entry is not present if (!create || (page = alloc_page()) == NULL) { returnNULL; } // (3) check if creating is needed, then alloc page for page table // CAUTION: this page is used for page table, not for common data page set_page_ref(page, 1); // (4) set page reference uintptr_t pa = page2pa(page); // (5) get linear address of page memset(KADDR(pa),0,PGSIZE); // (6) clear page content using memset *pdep = pa | PTE_U | PTE_W | PTE_P;// (7) set page directory entry's permission } return &((pte_t *)KADDR(PDE_ADDR(*pdep)))[PTX(la)]; // (8) return page table entry
//page_remove_pte - free an Page sturct which is related linear address la // - and clean(invalidate) pte which is related linear address la //note: PT is changed, so the TLB need to be invalidate static inline void page_remove_pte(pde_t *pgdir, uintptr_t la, pte_t *ptep) { /* LAB2 EXERCISE 3: YOUR CODE * * Please check if ptep is valid, and tlb must be manually updated if mapping is updated * * Maybe you want help comment, BELOW comments can help you finish the code * * Some Useful MACROs and DEFINEs, you can use them in below implementation. * MACROs or Functions: * struct Page *page pte2page(*ptep): get the according page from the value of a ptep * free_page : free a page * page_ref_dec(page) : decrease page->ref. NOTICE: ff page->ref == 0 , then this page should be free. * tlb_invalidate(pde_t *pgdir, uintptr_t la) : Invalidate a TLB entry, but only if the page tables being * edited are the ones currently in use by the processor. * DEFINEs: * PTE_P 0x001 // page table/directory entry flags bit : Present */ #if 0 if (0) { //(1) check if this page table entry is present struct Page *page = NULL; //(2) find corresponding page to pte //(3) decrease page reference //(4) and free this page when page reference reachs 0 //(5) clear second page table entry //(6) flush tlb } #endif if (*ptep & PTE_P) { // 确保传进来的二级页表时可用的 struct Page *page = pte2page(*ptep);// 获取页表项对应的物理页的Page结构 if (page_ref_dec(page) == 0) { // page_ref_dec被用于page->ref自减1, // 如果返回值是0,那么就说明不存在任何虚拟页指向该物理页,释放该物理页 free_page(page); } *ptep = 0; // 将PTE的映射关系清空 tlb_invalidate(pgdir, la); // 刷新TLB,确保TLB的缓存中不会有错误的映射关系 } }
structswap_manager { constchar *name; /* swap manager 全局初始化 */ int (*init) (void); /* 对mm_struct中的数据进行初始化 */ int (*init_mm) (struct mm_struct *mm); /* 时钟中断处理 */ int (*tick_event) (struct mm_struct *mm); /* Called when map a swappable page into the mm_struct */ int (*map_swappable) (struct mm_struct *mm, uintptr_t addr, struct Page *page, int swap_in); /* When a page is marked as shared, this routine is called to delete the addr entry from the swap manager */ int (*set_unswappable) (struct mm_struct *mm, uintptr_t addr); /* Try to swap out a page, return then victim */ int (*swap_out_victim) (struct mm_struct *mm, struct Page *ptr_page, int in_tick); /* check the page relpacement algorithm */ int (*check_swap)(void); };
do_pgfault - 处理缺页中断的中断处理例程 interrupt handler to process the page fault execption @mm : the control struct for a set of vma using the same PDT @error_code : the error code recorded in trapframe->tf_err which is setted by x86 hardware @addr : the addr which causes a memory access exception, (the contents of the CR2 register)
assert(entry != NULL && head != NULL); /*LAB3 EXERCISE 2: YOUR CODE*/ // link the most recent arrival page at the back of the pra_list_head qeueue // 将当前指定的物理页插入到链表的末尾 list_add(head, entry); return0; }
struct proc_struct { enum proc_state state; // Process state int pid; // Process ID int runs; // the running times of Proces uintptr_t kstack; // Process kernel stack volatile bool need_resched; // need to be rescheduled to release CPU? struct proc_struct *parent; // the parent process struct mm_struct *mm; // Process's memory management field struct context context; // Switch here to run process struct trapframe *tf; // Trap frame for current interrupt uintptr_t cr3; // the base addr of Page Directroy Table(PDT) uint32_t flags; // Process flag char name[PROC_NAME_LEN + 1]; // Process name list_entry_t list_link; // Process link list list_entry_t hash_link; // Process hash list };
其次,内核栈位于内核地址空间,并且是不共享的(每个线程都拥有自己的内核栈),因此不受到 mm 的管理,当进程退出的时候,内核能够根据 kstack 的值快速定位栈的位置并进行回收。uCore 的这种内核栈的设计借鉴的是 linux 的方法(但由于内存管理实现的差异,它实现的远不如 linux 的灵活),它使得每个线程的内核栈在不同的位置,这样从某种程度上方便调试,但同时也使得内核对栈溢出变得十分不敏感,因为一旦发生溢出,它极可能污染内核中其它的数据使得内核崩溃。如果能够通过页表,将所有进程的内核栈映射到固定的地址上去,能够避免这种问题,但又会使得进程切换过程中对栈的修改变得相当繁琐。
.globl __trapret __trapret: # restore registers from stack popal # restore %ds and %es popl %es popl %ds # get rid of the trap number and error code addl $0x8, %esp iret
.globl forkrets forkrets: # set stack to this new process trapframe movl 4(%esp), %esp 把esp指向当前进程的中断帧,esp指向了current->tf.tf_eip jmp __trapret
static struct proc_struct * alloc_proc(void) { struct proc_struct *proc = kmalloc(sizeof(struct proc_struct)); if (proc != NULL) { //LAB4:EXERCISE1 YOUR CODE /* * below fields in proc_struct need to be initialized * enum proc_state state; // Process state * int pid; // Process ID * int runs; // the running times of Proces * uintptr_t kstack; // Process kernel stack * volatile bool need_resched; // bool value: need to be rescheduled to release CPU? * struct proc_struct *parent; // the parent process * struct mm_struct *mm; // Process's memory management field * struct context context; // Switch here to run process * struct trapframe *tf; // Trap frame for current interrupt * uintptr_t cr3; // CR3 register: the base addr of Page Directroy Table(PDT) * uint32_t flags; // Process flag * char name[PROC_NAME_LEN + 1]; // Process name */ proc->state = PROC_UNINIT; proc->pid = -1; proc->cr3 = boot_cr3; proc->runs = 0; proc->kstack = 0; proc->need_resched = 0; proc->parent = NULL; proc->mm = NULL; memset(&proc->context, 0, sizeof(struct context)); proc->tf = NULL; proc->flags = 0; memset(proc->name, 0, PROC_NAME_LEN); } return proc; }
/* do_fork - parent process for a new child process * @clone_flags: used to guide how to clone the child process * @stack: the parent's user stack pointer. if stack==0, It means to fork a kernel thread. * @tf: the trapframe info, which will be copied to child process's proc->tf */ int do_fork(uint32_t clone_flags, uintptr_tstack, struct trapframe *tf) { int ret = -E_NO_FREE_PROC; structproc_struct *proc; if (nr_process >= MAX_PROCESS) { goto fork_out; } ret = -E_NO_MEM; //LAB4:EXERCISE2 YOUR CODE /* * Some Useful MACROs, Functions and DEFINEs, you can use them in below implementation. * MACROs or Functions: * alloc_proc: create a proc struct and init fields (lab4:exercise1) * 创建进程并初始化 * setup_kstack: alloc pages with size KSTACKPAGE as process kernel stack * 创建页,大小为KSTACKPAGE,并作为进程的内核栈 * copy_mm: process "proc" duplicate OR share process "current"'s mm according clone_flags * if clone_flags & CLONE_VM, then "share" ; else "duplicate" * 进程复制memory manager,根据clone_flag不同决定不同操作 * copy_thread: setup the trapframe on the process's kernel stack top and * setup the kernel entry point and stack of process * 在进程内核栈顶建立trapframe * hash_proc: add proc into proc hash_list * 添加进程到hash_list中 * get_pid: alloc a unique pid for process * 为进程分配一个独特的pid * wakeup_proc: set proc->state = PROC_RUNNABLE * VARIABLES: * proc_list: the process set's list * nr_process: the number of process set */
// 1. call alloc_proc to allocate a proc_struct // 为要创建的新的线程分配线程控制块的空间 proc = alloc_proc(); if(proc == NULL) goto fork_out; // 判断是否分配到内存空间 // 2. call setup_kstack to allocate a kernel stack for child process // 为新的线程设置栈,在本实验中,每个线程的栈的大小初始均为2个Page, 即8KB int status = setup_kstack(proc); if(status != 0) goto fork_out; // 3. call copy_mm to dup OR share mm according clone_flag // 对虚拟内存空间进行拷贝,由于在本实验中,内核线程之间共享一个虚拟内存空间,因此实际上该函数不需要进行任何操作 status = copy_mm(clone_flags, proc); if(status != 0) goto fork_out; // 4. call copy_thread to setup tf & context in proc_struct // 在新创建的内核线程的栈上面设置伪造好的中端帧,便于后文中利用iret命令将控制权转移给新的线程 copy_thread(proc, stack, tf); // 5. insert proc_struct into hash_list && proc_list // 为新的线程创建pid proc->pid = get_pid(); hash_proc(proc); // 将线程放入使用hash组织的链表中,便于加速以后对某个指定的线程的查找 nr_process ++; // 将全局线程的数目加1 list_add(&proc_list, &proc->list_link); // 将线程加入到所有线程的链表中,便于进行调度 // 6. call wakeup_proc to make the new child process RUNNABLE // 唤醒该线程,即将该线程的状态设置为可以运行 wakeup_proc(proc); // 7. set ret vaule using child proc's pid // 返回新线程的pid ret = proc->pid; fork_out:
// proc_run - make process "proc" running on cpu // NOTE: before call switch_to, should load base addr of "proc"'s new PDT voidproc_run(struct proc_struct *proc) { // 判断需要运行的线程是否是正在运行的线程 if (proc != current) { bool intr_flag; structproc_struct *prev = current, *next = proc; //如果不是的话,获取到切换前后的两个线程 local_intr_save(intr_flag); // 关闭中断 { current = proc; load_esp0(next->kstack + KSTACKSIZE); lcr3(next->cr3); // 设置了TSS和cr3,相当于是切换了页表和栈 switch_to(&(prev->context), &(next->context)); // switch_to恢复要运行的线程的上下文,然后由于恢复的上下文中已经将返回地址(copy_thread函数中完成)修改成了forkret函数的地址(如果这个线程是第一运行的话,否则就是切换到这个线程被切换出来的地址),也就是会跳转到这个函数,最后进一步跳转到了__trapsret函数,调用iret最终将控制权切换到新的线程; } local_intr_restore(intr_flag); // 使能中断 } }
forkret函数:
1 2 3 4 5 6 7
// forkret -- the first kernel entry point of a new thread/process // NOTE: the addr of forkret is setted in copy_thread function // after switch_to, the current proc will execute here. staticvoid forkret(void) { forkrets(current->tf); }
// proc_init - set up the first kernel thread idleproc "idle" by itself and // - create the second kernel thread init_main void proc_init(void) { int i;
list_init(&proc_list); for (i = 0; i < HASH_LIST_SIZE; i ++) { list_init(hash_list + i); }
static inline int syscall(int num, ...) { va_list ap; va_start(ap, num); uint32_t a[MAX_ARGS]; int i, ret; for (i = 0; i < MAX_ARGS; i ++) { a[i] = va_arg(ap, uint32_t); } va_end(ap);
在本实验中,与进程相关的各个系统调用属性如下所示: |系统调用名 | 含义 | 具体完成服务的函数 | |——|——|——| |SYS_exit | process exit | do_exit | |SYS_fork | create child process, dup mm | do_fork—>wakeup_proc | |SYS_wait | wait child process | do_wait | |SYS_exec | after fork, process execute a new program | load a program and refresh the mm | |SYS_yield | process flag itself need resecheduling | proc->need_sched=1, then scheduler will rescheule this process | |SYS_kill | kill process | do_kill—>proc->flags |= PF_EXITING, —>wakeup_proc—>do_wait—>do_exit | |SYS_getpid | get the process’s pid | |
/* below here defined by x86 hardware */ uintptr_t tf_eip; uint16_t tf_cs; uint16_t tf_padding3; uint32_t tf_eflags; /* below here only when crossing rings */ uintptr_t tf_esp; uint16_t tf_ss; uint16_t tf_padding4;
/* load_icode - load the content of binary program(ELF format) as the new content of current process * @binary: the memory addr of the content of binary program * @size: the size of the content of binary program * 读取一个二进制elf文件并为其设置执行场景,并执行 */ staticint load_icode(unsignedchar *binary, size_t size) { if (current->mm != NULL) { panic("load_icode: current->mm must be empty.\n"); }
int ret = -E_NO_MEM; structmm_struct *mm; //(1) create a new mm for current process if ((mm = mm_create()) == NULL) { goto bad_mm; } //(2) create a new PDT, and mm->pgdir= kernel virtual addr of PDT if (setup_pgdir(mm) != 0) { goto bad_pgdir_cleanup_mm; } //(3) copy TEXT/DATA section, build BSS parts in binary to memory space of process structPage *page; //(3.1) get the file header of the bianry program (ELF format) // 将二进制串转成描述elf的结构体 structelfhdr *elf = (struct elfhdr *)binary; //(3.2) get the entry of the program section headers of the bianry program (ELF format) // 获取elf头的起始地址 structproghdr *ph = (struct proghdr *)(binary + elf->e_phoff); // 代码段的头 //(3.3) This program is valid? // 第一个实验中说了elf的这个域是ELF_MAGIC if (elf->e_magic != ELF_MAGIC) { ret = -E_INVAL_ELF; goto bad_elf_cleanup_pgdir; }
uint32_t vm_flags, perm; structproghdr *ph_end = ph + elf->e_phnum; for (; ph < ph_end; ph ++) { //(3.4) find every program section headers // 每一个程序段 if (ph->p_type != ELF_PT_LOAD) { //程序段头里的这个程序段的类型,如可加载的代码、数据、动态链接信息等 continue ; } if (ph->p_filesz > ph->p_memsz) { ret = -E_INVAL_ELF; goto bad_cleanup_mmap; } if (ph->p_filesz == 0) { // 这个段的大小 continue ; } //(3.5) call mm_map fun to setup the new vma ( ph->p_va, ph->p_memsz) vm_flags = 0, perm = PTE_U; if (ph->p_flags & ELF_PF_X) vm_flags |= VM_EXEC; if (ph->p_flags & ELF_PF_W) vm_flags |= VM_WRITE; if (ph->p_flags & ELF_PF_R) vm_flags |= VM_READ; // 可读、可写、可执行?
//(3.6) alloc memory, and copy the contents of every program section (from, from+end) to process's memory (la, la+end) end = ph->p_va + ph->p_filesz; //(3.6.1) copy TEXT/DATA section of bianry program // 分配页 while (start < end) { if ((page = pgdir_alloc_page(mm->pgdir, la, perm)) == NULL) { goto bad_cleanup_mmap; } off = start - la, size = PGSIZE - off, la += PGSIZE; if (end < la) { size -= la - end; } memcpy(page2kva(page) + off, from, size); start += size, from += size; }
//(3.6.2) build BSS section of binary program end = ph->p_va + ph->p_memsz; if (start < la) { /* ph->p_memsz == ph->p_filesz */ if (start == end) { continue ; } off = start + PGSIZE - la, size = PGSIZE - off; if (end < la) { size -= la - end; } memset(page2kva(page) + off, 0, size); start += size; assert((end < la && start == end) || (end >= la && start == la)); } while (start < end) { if ((page = pgdir_alloc_page(mm->pgdir, la, perm)) == NULL) { goto bad_cleanup_mmap; } off = start - la, size = PGSIZE - off, la += PGSIZE; if (end < la) { size -= la - end; } memset(page2kva(page) + off, 0, size); start += size; } } //(4) build user stack memory vm_flags = VM_READ | VM_WRITE | VM_STACK; if ((ret = mm_map(mm, USTACKTOP - USTACKSIZE, USTACKSIZE, vm_flags, NULL)) != 0) { goto bad_cleanup_mmap; } assert(pgdir_alloc_page(mm->pgdir, USTACKTOP-PGSIZE , PTE_USER) != NULL); assert(pgdir_alloc_page(mm->pgdir, USTACKTOP-2*PGSIZE , PTE_USER) != NULL); assert(pgdir_alloc_page(mm->pgdir, USTACKTOP-3*PGSIZE , PTE_USER) != NULL); assert(pgdir_alloc_page(mm->pgdir, USTACKTOP-4*PGSIZE , PTE_USER) != NULL);
//(5) set current process's mm, sr3, and set CR3 reg = physical addr of Page Directory mm_count_inc(mm); // mm的count加1,计算有多少进程同时使用这个mm current->mm = mm; // 当前进程的mm是这个mm current->cr3 = PADDR(mm->pgdir); // 虚拟地址转换成物理地址 lcr3(PADDR(mm->pgdir));
//(6) setup trapframe for user environment structtrapframe *tf = current->tf; memset(tf, 0, sizeof(struct trapframe)); /* LAB5:EXERCISE1 YOUR CODE * should set tf_cs,tf_ds,tf_es,tf_ss,tf_esp,tf_eip,tf_eflags * NOTICE: If we set trapframe correctly, then the user level process can return to USER MODE from kernel. S o * tf_cs should be USER_CS segment (see memlayout.h) * tf_ds=tf_es=tf_ss should be USER_DS segment * tf_esp should be the top addr of user stack (USTACKTOP) * tf_eip should be the entry point of this binary program (elf->e_entry) * tf_eflags should be set to enable computer to produce Interrupt */ tf->tf_cs = USER_CS; tf->tf_ds = tf->tf_es = tf->tf_ss = USER_DS; tf->tf_esp = USTACKTOP; tf->tf_eip = elf->e_entry; tf->tf_eflags = 0x00000002 | FL_IF; // to enable interrupt //网上这里有的是这么写的,不知道为啥,我觉得应该只要FL_IF就够了,可能是我考虑不周 /* #define FL_IF 0x00000200 // Interrupt Flag tf->tf_eflags = FL_IF; */ ret = 0; out: return ret; bad_cleanup_mmap: exit_mmap(mm); bad_elf_cleanup_pgdir: put_pgdir(mm); bad_pgdir_cleanup_mm: mm_destroy(mm); bad_mm: goto out; }
case IRQ_OFFSET + IRQ_TIMER: ticks++; if(ticks>=TICK_NUM){ assert(current != NULL); current->need_resched = 1; //print_ticks(); ticks=0; } /* LAB5 YOUR CODE */ /* you should upate you lab1 code (just add ONE or TWO lines of code): * Every TICK_NUM cycle, you should set current process's current->need_resched = 1 */ -
// set_links - set the relation links of process staticvoid set_links(struct proc_struct *proc) { list_add(&proc_list, &(proc->list_link)); proc->yptr = NULL; if ((proc->optr = proc->parent->cptr) != NULL) { proc->optr->yptr = proc; } proc->parent->cptr = proc; nr_process ++; }
//LAB5 YOUR CODE : (update LAB4 steps) /* Some Functions * set_links: set the relation links of process. ALSO SEE: remove_links: lean the relation links of process * ------------------- * update step 1: set child proc's parent to current process, make sure current process's wait_state is 0 * update step 5: insert proc_struct into hash_list && proc_list, set the relation links of process */ // 1. call alloc_proc to allocate a proc_struct proc = alloc_proc(); if(proc == NULL) goto fork_out; // 2. call setup_kstack to allocate a kernel stack for child process proc->parent = current; assert(current->wait_state == 0);
int status = setup_kstack(proc); if(status != 0) goto bad_fork_cleanup_kstack; // 3. call copy_mm to dup OR share mm according clone_flag status = copy_mm(clone_flags, proc); if(status != 0) goto bad_fork_cleanup_proc; // 4. call copy_thread to setup tf & context in proc_struct copy_thread(proc, stack, tf); // 5. insert proc_struct into hash_list && proc_list proc->pid = get_pid(); hash_proc(proc); set_links(proc);
// delete thses two lines !!! //nr_process ++; //list_add(&proc_list, &proc->list_link); // delete thses two lines !!!
// 6. call wakeup_proc to make the new child process RUNNABLE wakeup_proc(proc); // 7. set ret vaule using child proc's pid ret = proc->pid;
/* copy_range - copy content of memory (start, end) of one process A to another process B * @to: the addr of process B's Page Directory * @from: the addr of process A's Page Directory * @share: flags to indicate to dup OR share. We just use dup method, so it didn't be used. * * CALL GRAPH: copy_mm-->dup_mmap-->copy_range */ int copy_range(pde_t *to, pde_t *from, uintptr_t start, uintptr_t end, bool share) { assert(start % PGSIZE == 0 && end % PGSIZE == 0); assert(USER_ACCESS(start, end)); // copy content by page unit. do { //call get_pte to find process A's pte according to the addr start pte_t *ptep = get_pte(from, start, 0), *nptep; if (ptep == NULL) { start = ROUNDDOWN(start + PTSIZE, PTSIZE); continue ; } //call get_pte to find process B's pte according to the addr start. If pte is NULL, just alloc a PT if (*ptep & PTE_P) { if ((nptep = get_pte(to, start, 1)) == NULL) { return -E_NO_MEM; } uint32_t perm = (*ptep & PTE_USER); //get page from ptep struct Page *page = pte2page(*ptep); // alloc a page for process B struct Page *npage=alloc_page(); assert(page!=NULL); assert(npage!=NULL); int ret=0; /* LAB5:EXERCISE2 YOUR CODE * replicate content of page to npage, build the map of phy addr of nage with the linear addr start * * Some Useful MACROs and DEFINEs, you can use them in below implementation. * MACROs or Functions: * page2kva(struct Page *page): return the kernel vritual addr of memory which page managed (SEE pmm. h) * page_insert: build the map of phy addr of an Page with the linear addr la * memcpy: typical memory copy function * * (1) find src_kvaddr: the kernel virtual address of page * (2) find dst_kvaddr: the kernel virtual address of npage * (3) memory copy from src_kvaddr to dst_kvaddr, size is PGSIZE * (4) build the map of phy addr of nage with the linear addr start */ char *src_kvaddr = page2kva(page); //找到父进程需要复制的物理页在内核地址空间中的虚拟地址,这是由于这个函数执行的时候使用的时内核的地址空间 char *dst_kvaddr = page2kva(npage); // 找到子进程需要被填充的物理页的内核虚拟地址 memcpy(dst_kvaddr, src_kvaddr, PGSIZE); // 将父进程的物理页的内容复制到子进程中去 page_insert(to, npage, start, perm); // 建立子进程的物理页与虚拟页的映射关系 assert(ret == 0); } start += PGSIZE; } while (start != 0 && start < end); return 0; }
structproc_struct { enumproc_statestate;// Process state int pid; // Process ID int runs; // the running times of Proces uintptr_t kstack; // Process kernel stack volatilebool need_resched; // bool value: need to be rescheduled to release CPU? structproc_struct *parent;// the parent process structmm_struct *mm;// Process's memory management field structcontextcontext;// Switch here to run process structtrapframe *tf;// Trap frame for current interrupt uintptr_t cr3; // CR3 register: the base addr of Page Directroy Table(PDT) uint32_t flags; // Process flag char name[PROC_NAME_LEN + 1]; // Process name list_entry_t list_link; // Process link list list_entry_t hash_link; // Process hash list };
// The introduction of scheduling classes is borrrowed from Linux, and makes the // core scheduler quite extensible. These classes (the scheduler modules) encapsulate // the scheduling policies. structsched_class { // the name of sched_class constchar *name; // 初始化运行队列 void (*init)(struct run_queue *rq);
// put the proc into runqueue, and this function must be called with rq_lock // 进程放入运行队列 void (*enqueue)(struct run_queue *rq, struct proc_struct *proc);
// get the proc out runqueue, and this function must be called with rq_lock // 从队列中取出 void (*dequeue)(struct run_queue *rq, struct proc_struct *proc);
// choose the next runnable task // 选择下一个可运行的任务 structproc_struct *(*pick_next)(structrun_queue *rq);
// dealer of the time-tick // 处理tick中断 void (*proc_tick)(struct run_queue *rq, struct proc_struct *proc);
/* for SMP support in the future * load_balance * void (*load_balance)(struct rq* rq); * get some proc from this rq, used in load_balance, * return value is the num of gotten proc * int (*get_proc)(struct rq* rq, struct proc* procs_moved[]); */ };
struct proc_struct { enum proc_state state; // Process state int pid; // Process ID int runs; // the running times of Proces uintptr_t kstack; // Process kernel stack volatile bool need_resched; // bool value: need to be rescheduled to release CPU? struct proc_struct *parent; // the parent process struct mm_struct *mm; // Process's memory management field struct context context; // Switch here to run process struct trapframe *tf; // Trap frame for current interrupt uintptr_t cr3; // CR3 register: the base addr of Page Directroy Table(PDT) uint32_t flags; // Process flag char name[PROC_NAME_LEN + 1]; // Process name list_entry_t list_link; // Process link list list_entry_t hash_link; // Process hash list int exit_code; // exit code (be sent to parent proc) uint32_t wait_state; // waiting state struct proc_struct *cptr, *yptr, *optr; // relations between processes struct run_queue *rq; // running queue contains Process list_entry_t run_link; // the entry linked in run queue // 该进程的调度链表结构,该结构内部的连接组成了 运行队列 列表
int time_slice; // time slice for occupying the CPU // 进程剩余的时间片 skew_heap_entry_t lab6_run_pool; // FOR LAB6 ONLY: the entry in the run pool //在优先队列中用到的
uint32_t lab6_stride; // FOR LAB6 ONLY: the current stride of the process // 步进值
uint32_t lab6_priority; // FOR LAB6 ONLY: the priority of process, set by lab6_set_priority(uint32_t) // 优先级
//LAB4:EXERCISE1 YOUR CODE /* * below fields in proc_struct need to be initialized * enum proc_state state; // Process state * int pid; // Process ID * int runs; // the running times of Proces * uintptr_t kstack; // Process kernel stack * volatile bool need_resched; // bool value: need to be rescheduled to release CPU? * struct proc_struct *parent; // the parent process * struct mm_struct *mm; // Process's memory management field * struct context context; // Switch here to run process * struct trapframe *tf; // Trap frame for current interrupt * uintptr_t cr3; // CR3 register: the base addr of Page Directroy Table(PDT) * uint32_t flags; // Process flag * char name[PROC_NAME_LEN + 1]; // Process name */ proc->state = PROC_UNINIT; proc->pid = -1; proc->cr3 = boot_cr3;
//LAB5 YOUR CODE : (update LAB4 steps) /* * below fields(add in LAB5) in proc_struct need to be initialized * uint32_t wait_state; // waiting state * struct proc_struct *cptr, *yptr, *optr; // relations between processes */ proc->wait_state = 0; proc->cptr = proc->optr = proc->yptr = NULL; //LAB6 YOUR CODE : (update LAB5 steps) /* * below fields(add in LAB6) in proc_struct need to be initialized * struct run_queue *rq; // running queue contains Process * list_entry_t run_link; // the entry linked in run queue * int time_slice; // time slice for occupying the CPU * skew_heap_entry_t lab6_run_pool; // FOR LAB6 ONLY: the entry in the run pool * uint32_t lab6_stride; // FOR LAB6 ONLY: the current stride of the process * uint32_t lab6_priority; // FOR LAB6 ONLY: the priority of process, set by lab6_set_priority(uint32_t) */ proc->rq = NULL; memset(&proc->run_link, 0, sizeof(list_entry_t)); proc->time_slice = 0; memset(&proc->lab6_run_pool,0,sizeof(skew_heap_entry_t)); proc->lab6_stride=0; proc->lab6_priority=1;
/* * stride_init initializes the run-queue rq with correct assignment for * member variables, including: * * - run_list: should be a empty list after initialization. * - lab6_run_pool: NULL * - proc_num: 0 * - max_time_slice: no need here, the variable would be assigned by the caller. * * hint: see libs/list.h for routines of the list structures. */ staticvoid stride_init(struct run_queue *rq) { /* LAB6: YOUR CODE * (1) init the ready process list: rq->run_list * (2) init the run pool: rq->lab6_run_pool * (3) set number of process: rq->proc_num to 0 */ list_init(&rq->run_list); rq->lab6_run_pool = NULL; rq->proc_num = 0; }
/* * stride_enqueue inserts the process ``proc'' into the run-queue * ``rq''. The procedure should verify/initialize the relevant members * of ``proc'', and then put the ``lab6_run_pool'' node into the * queue(since we use priority queue here). The procedure should also * update the meta date in ``rq'' structure. * * proc->time_slice denotes the time slices allocation for the * process, which should set to rq->max_time_slice. * * hint: see libs/skew_heap.h for routines of the priority * queue structures. */ staticvoid stride_enqueue(struct run_queue *rq, struct proc_struct *proc) { /* LAB6: YOUR CODE * (1) insert the proc into rq correctly * NOTICE: you can use skew_heap or list. Important functions * skew_heap_insert: insert a entry into skew_heap * list_add_before: insert a entry into the last of list * (2) recalculate proc->time_slice * (3) set proc->rq pointer to rq * (4) increase rq->proc_num */ rq->lab6_run_pool = skew_heap_insert(rq->lab6_run_pool, &proc->lab6_run_pool, proc_stride_comp_f); // 做插入操作,把这个进程插到run_pool里。 if(proc->time_slice == 0 || proc->time_slice > rq->max_time_slice) { proc->time_slice = rq->max_time_slice; } // 如果这个进程的时间片不符合要求,就把它初始化成最大值。 proc->rq = rq; rq->proc_num ++; //run_queue里的进程数++ }
做删除操作,把这个进程从run_pool里删除,并且将run_queue里的进程数减一。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
/* * stride_dequeue removes the process ``proc'' from the run-queue * ``rq'', the operation would be finished by the skew_heap_remove * operations. Remember to update the ``rq'' structure. * * hint: see libs/skew_heap.h for routines of the priority * queue structures. */ staticvoid stride_dequeue(struct run_queue *rq, struct proc_struct *proc) { /* LAB6: YOUR CODE * (1) remove the proc from rq correctly * NOTICE: you can use skew_heap or list. Important functions * skew_heap_remove: remove a entry from skew_heap * list_del_init: remove a entry from the list */ rq->lab6_run_pool = skew_heap_remove(rq->lab6_run_pool, &proc->lab6_run_pool, proc_stride_comp_f); rq->proc_num --; }
/* * stride_pick_next pick the element from the ``run-queue'', with the * minimum value of stride, and returns the corresponding process * pointer. The process pointer would be calculated by macro le2proc, * see kern/process/proc.h for definition. Return NULL if * there is no process in the queue. * * When one proc structure is selected, remember to update the stride * property of the proc. (stride += BIG_STRIDE / priority) * * hint: see libs/skew_heap.h for routines of the priority * queue structures. */ staticstruct proc_struct * stride_pick_next(struct run_queue *rq) { /* LAB6: YOUR CODE * (1) get a proc_struct pointer p with the minimum value of stride (1.1) If using skew_heap, we can use le2proc get the p from rq->lab6_run_poll (1.2) If using list, we have to search list to find the p with minimum stride value * (2) update p;s stride value: p->lab6_stride * (3) return p */ if (rq->lab6_run_pool == NULL) returnNULL; structproc_struct *p = le2proc(rq->lab6_run_pool, lab6_run_pool); p->lab6_stride += BIG_STRIDE/p->lab6_priority; return p; }
/* * stride_proc_tick works with the tick event of current process. You * should check whether the time slices for current process is * exhausted and update the proc struct ``proc''. proc->time_slice * denotes the time slices left for current * process. proc->need_resched is the flag variable for process * switching. */ staticvoid stride_proc_tick(struct run_queue *rq, struct proc_struct *proc) { /* LAB6: YOUR CODE */ if (proc->time_slice > 0) { proc->time_slice --; } if (proc->time_slice == 0) { proc->need_resched = 1; } }
structsemaphore { int count; queueType queue; }; voidsemWait(semaphore s) { s.count--; if (s.count < 0) { /* place this process in s.queue */; /* block this process */; } } voidsemSignal(semaphore s) { s.count++; if (s.count<= 0) { /* remove a process P from s.queue */; /* place process P on ready list */; } }
typedefstructmonitor{ semaphore_t mutex; // the mutex lock for going into the routines in monitor, should be initialized to 1 // the next semaphore is used to // (1) procs which call cond_signal funciton should DOWN next sema after UP cv.sema // OR (2) procs which call cond_wait funciton should UP next sema before DOWN cv.sema semaphore_t next; int next_count; // the number of of sleeped procs which cond_signal funciton condvar_t *cv; // the condvars in monitor } monitor_t;
typedefstructcondvar{ semaphore_t sem; // the sem semaphore is used to down the waiting proc, and the signaling proc should up the waiting proc int count; // the number of waiters on condvar monitor_t * owner; // the owner(monitor) of this condvar } condvar_t;
function_in_monitor (…) { sem.wait(monitor.mutex); //----------------------------- the real body of function; //----------------------------- if(monitor.next_count > 0) sem_signal(monitor.next); else sem_signal(monitor.mutex); }
monitor mt { ----------------variable------------------ semaphore mutex; semaphore next; int next_count; condvar {int count, sempahore sem} cv[N]; other variables in mt; }
实现如下:
1 2 3 4 5 6 7 8 9 10 11 12 13
typedefstructcondvar{ semaphore_t sem; // the sem semaphore is used to down the waiting proc, // and the signaling proc should up the waiting proc int count; // the number of waiters on condvar monitor_t * owner; // the owner(monitor) of this condvar } condvar_t;
typedefstructmonitor{ semaphore_t mutex; // the mutex lock for going into the routines in monitor, should be initialized to 1 semaphore_t next; // the next semaphore is used to down the signaling proc itself, // and the other OR wakeuped waiting proc should wake up the sleeped signaling proc. int next_count; // the number of of sleeped signaling proc condvar_t *cv; // the condvars in monitor } monitor_t;
--------routines in monitor--------------- routineA_in_mt () { wait(mt.mutex); ... real body of routineA ... if(next_count>0) signal(mt.next); else signal(mt.mutex); }
void phi_take_forks_condvar(int i) { //--------into routine in monitor-------------- // LAB7 EXERCISE1: YOUR CODE // I am hungry // try to get fork //--------leave routine in monitor-------------- down(&(mtp->mutex)); state_condvar[i]=HUNGRY; if(state_condvar[(i+4)%5]!=EATING && state_condvar[(i+1)%5]!=EATING){ state_condvar[i]=EATING; } else { cprintf("phi_take_forks_condvar: %d didn’t get fork and will wait\n", i); cond_wait(mtp->cv + i); }
void phi_put_forks_condvar(int i) { //--------into routine in monitor-------------- // LAB7 EXERCISE1: YOUR CODE // I ate over // test left and right neighbors //--------leave routine in monitor-------------- down(&(mtp->mutex)); state_condvar[i] = THINKING; cprintf("phi_put_forks_condvar: %d finished eating\n", i); phi_test_condvar((i + N - 1) % N); phi_test_condvar((i + 1) % N); if(mtp->next_count>0) up(&(mtp->next)); else up(&(mtp->mutex)); }
/* * sfs_bmap_load_nolock - according to the DIR's inode and the logical index of block in inode, find the NO. of disk block. * @sfs: sfs file system * @sin: sfs inode in memory * @index: the logical index of disk block in inode * @ino_store:the NO. of disk block */ staticint sfs_bmap_load_nolock(struct sfs_fs *sfs, struct sfs_inode *sin, uint32_t index, uint32_t *ino_store) { structsfs_disk_inode *din =sin->din; assert(index <= din->blocks); int ret; uint32_t ino; bool create = (index == din->blocks); if ((ret = sfs_bmap_get_nolock(sfs, sin, index, create, &ino)) != 0) { return ret; } assert(sfs_block_inuse(sfs, ino)); if (create) { din->blocks ++; } if (ino_store != NULL) { *ino_store = ino; } return0; }
/* * sfs_bmap_get_nolock - according sfs_inode and index of block, find the NO. of disk block * no lock protect * @sfs: sfs file system * @sin: sfs inode in memory * @index: the index of block in inode * @create: BOOL, if the block isn't allocated, if create = 1 the alloc a block, otherwise just do nothing * @ino_store: 0 OR the index of already inused block or new allocated block. */ staticint sfs_bmap_get_nolock(struct sfs_fs *sfs, struct sfs_inode *sin, uint32_t index, bool create, uint32_t *ino_store) { structsfs_disk_inode *din =sin->din; int ret; uint32_t ent, ino; // the index of disk block is in the fist SFS_NDIRECT direct blocks if (index < SFS_NDIRECT) { if ((ino = din->direct[index]) == 0 && create) { if ((ret = sfs_block_alloc(sfs, &ino)) != 0) { return ret; } din->direct[index] = ino; sin->dirty = 1; } goto out; } // the index of disk block is in the indirect blocks. index -= SFS_NDIRECT; if (index < SFS_BLK_NENTRY) { ent = din->indirect; if ((ret = sfs_bmap_get_sub_nolock(sfs, &ent, index, create, &ino)) != 0) { return ret; } if (ent != din->indirect) { assert(din->indirect == 0); din->indirect = ent; sin->dirty = 1; } goto out; } else { panic ("sfs_bmap_get_nolock - index out of range"); } out: assert(ino == 0 || sfs_block_inuse(sfs, ino)); *ino_store = ino; return0; }
/* * vfs_mount - Mount a filesystem. Once we've found the device, call MOUNTFUNC to * set up the filesystem and hand back a struct fs. * * The DATA argument is passed through unchanged to MOUNTFUNC. */ int vfs_mount(constchar *devname, int (*mountfunc)(struct device *dev, struct fs **fs_store)) { int ret; lock_vdev_list(); // 信号量操作 vfs_dev_t *vdev; if ((ret = find_mount(devname, &vdev)) != 0) { // 找一个同名设备 goto out; } if (vdev->fs != NULL) { ret = -E_BUSY; // 如果这个设备已经被挂载到一个文件系统上了,就不能被再挂载 goto out; } assert(vdev->devname != NULL && vdev->mountable);
//LAB8:EXERCISE1 YOUR CODE //HINT: call sfs_bmap_load_nolock, sfs_rbuf, sfs_rblock,etc. // read different kind of blocks in file /* * (1) If offset isn't aligned with the first block, Rd/Wr some content from offset to the end of the first block * NOTICE: useful function: sfs_bmap_load_nolock, sfs_buf_op * Rd/Wr size = (nblks != 0) ? (SFS_BLKSIZE - blkoff) : (endpos - offset) * (2) Rd/Wr aligned blocks * NOTICE: useful function: sfs_bmap_load_nolock, sfs_block_op * (3) If end position isn't aligned with the last block, Rd/Wr some content from begin to the (endpos % SFS_BLKSIZE) of the last block * NOTICE: useful function: sfs_bmap_load_nolock, sfs_buf_op */ if (offset % SFS_BLKSIZE != 0 || endpos / SFS_BLKSIZE == offset / SFS_BLKSIZE){ blkoff = offset % SFS_BLKSIZE; size = (nblks != 0) ? (SFS_BLKSIZE - blkoff) : (endpos - offset); if ((ret = sfs_bmap_load_nolock(sfs, sin, blkno, &ino)) != 0) goto out; if ((ret = sfs_buf_op(sfs, buf, size, ino, blkoff)) != 0) goto out; alen += size; buf += size; } // 处理如果不是从块的开头开始写的情况,如果偏移量%块大小不是0则是从块内部开始写的。如果nblks是0的话说明只有一个块里的一部分需要写。先把这个写了。
改写proc.c中的load_icode函数和其他相关函数,实现基于文件系统的执行程序机制。首先是在do_execve中进行文件名和命令行参数的复制,执行sysfie_open打开相关文件,fd是已经打开的这个文件。执行: make qemu。如果能看看到sh用户程序的执行界面,则基本成功了。如果在sh用户界面上可 以执行”ls”,”hello”等其他放置在sfs文件系统中的其他执行程序,则可以认为本实验基本成功。
staticint load_icode(int fd, int argc, char **kargv) { /* LAB8:EXERCISE2 YOUR CODE HINT:how to load the file with handler fd in to process's memory? how to setup argc/argv? * MACROs or Functions: * mm_create - create a mm * setup_pgdir - setup pgdir in mm * load_icode_read - read raw data content of program file * mm_map - build new vma * pgdir_alloc_page - allocate new memory for TEXT/DATA/BSS/stack parts * lcr3 - update Page Directory Addr Register -- CR3 * * (1) create a new mm for current process * (2) create a new PDT, and mm->pgdir= kernel virtual addr of PDT * (3) copy TEXT/DATA/BSS parts in binary to memory space of process * (3.1) read raw data content in file and resolve elfhdr * (3.2) read raw data content in file and resolve proghdr based on info in elfhdr * (3.3) call mm_map to build vma related to TEXT/DATA * (3.4) callpgdir_alloc_page to allocate page for TEXT/DATA, read contents in file * and copy them into the new allocated pages * (3.5) callpgdir_alloc_page to allocate pages for BSS, memset zero in these pages * (4) call mm_map to setup user stack, and put parameters into user stack * (5) setup current process's mm, cr3, reset pgidr (using lcr3 MARCO) * (6) setup uargc and uargv in user stacks * (7) setup trapframe for user environment * (8) if up steps failed, you should cleanup the env. */ if (current->mm != NULL) { panic("load_icode: current->mm must be empty.\n"); }
int ret = -E_NO_MEM; structmm_struct *mm; //(1) create a new mm for current process if ((mm = mm_create()) == NULL) { goto bad_mm; } //(2) create a new PDT, and mm->pgdir= kernel virtual addr of PDT if (setup_pgdir(mm) != 0) { goto bad_pgdir_cleanup_mm; } //(3) copy TEXT/DATA section, build BSS parts in binary to memory space of process structPage *page; //(3.1) get the file header of the bianry program (ELF format) structelfhdrelf; off_t offset = 0;
/* LAB5:EXERCISE1 YOUR CODE * should set tf_cs,tf_ds,tf_es,tf_ss,tf_esp,tf_eip,tf_eflags * NOTICE: If we set trapframe correctly, then the user level process can return to USER MODE from kernel. So * tf_cs should be USER_CS segment (see memlayout.h) * tf_ds=tf_es=tf_ss should be USER_DS segment * tf_esp should be the top addr of user stack (USTACKTOP) * tf_eip should be the entry point of this binary program (elf->e_entry) * tf_eflags should be set to enable computer to produce Interrupt */ structtrapframe *tf = current->tf; memset(tf, 0, sizeof(struct trapframe)); tf->tf_cs = USER_CS; tf->tf_ds = tf->tf_es = tf->tf_ss = USER_DS; tf->tf_esp = stacktop; tf->tf_eip = elf.e_entry; tf->tf_eflags = 0x2 | FL_IF; // to enable interrupt ret = 0; out: return ret; bad_cleanup_mmap: exit_mmap(mm); bad_elf_cleanup_pgdir: put_pgdir(mm); bad_pgdir_cleanup_mm: mm_destroy(mm); bad_mm: goto out; }
func main() { const ( a = iota //0 b //1 c //2 d = "ha" //独立值,iota += 1 e //"ha" iota += 1 f = 100 //iota +=1 g //100 iota +=1 h = iota //7,恢复计数 i //8 ) fmt.Println(a,b,c,d,e,f,g,h,i) }
intStream := make(chan int) go func() { defer close(intStream) for i:= 1; i <= 5; i ++ { intStream <- i } }() for integer := range intStream { fmt.Printf("%v ",integer) }
for { // 要不就无限循环,要不就使用range循环 select { //使用channel作业 } }
向channel发送迭代变量
1 2 3 4 5 6 7
for _, s := range []string{"a", "b", "c"} { select { case <- done: return case stringStream <- s: } }
循环等待停止
创建循环,无限直至停止。
1 2 3 4 5 6 7 8
for { select { case <- done: return default: } // 非抢占式任务 }
防止goroutine泄露
main goroutine可能会在其生命周期内将其他的goroutine设置为自旋,导致内存利用率下降。减轻这种情况的方法是在父goroutine和子goroutine之间建立一个信号,让父goroutine向其子goroutine发出信号通知。父goroutine将该channel发送给子goroutine,然后在想要取消子goroutine时关闭该channel。
var or func(channels ...<-chan interface{}) <-chan interface{} or = func(channels ...<-chan interface{}) <-chan interface{} { switch len(channels) { case 0: return nil case 1: return channels[0] }
orDone := make(chan interface{}) go func() { defer close() switch len(channels): case 2: select{ case <-channels[0]: case <-channels[1]: case <-channels[1]: case <-channels[2]: } }() } }
addedStream := make(chan int) go func() { defer close(addedStream) for i := range intStream { select { case <-done: return case addedStream <- i + additive: } } }() return addedStream }
m := make(map[interface{}] int) m[foo(1)] = 1 m[bar(1)] = 1
fmt.Printf("%v", m)
输出为:
1
map[1:1, 2:2]
虽然基础值是相同的,但是科通通过不同的类型信息在map中区分它们。
Go语言并发之道第5章
异常传递
我们需要对传入的异常信息进行传递和处理,如:
1 2 3 4 5 6 7 8 9
func PostReport(id string) error { result, err := lowlevel.DoWork() if err != nil{ if _, ok := err.(lowlevel.Error); ok { err = WrapErr(err, "cannot post report with id %q", id) } return err } }
if err != nil { msg := "There was an unexpected issue; please report this as a bug." if _, ok := err.(IntermediateErr); ok { msg = err.Error() } handleError(1, err, msg) } }
for { select { // 处理心跳,如果没有消息时,至少timeout/2后会从心跳channel发出一条消息 case _, ok := <-heartbeat: if ok == false { return } fmt.Println("pulse") case r, ok := <-results: if ok == false { return } fmt.Printf("result %v\n", r.Second()) case <-time.After(timeout): return } } }
for i := 0; i < 10; i++ { select { case heartbeatStream <- struct{}{}: default: } select { case <-done: return case workStream <- rand.Intn(10): } } // 这里为心跳设置了单独的select块,将发送result和发送心跳分开,如果接收者没有准备好接受结果,作为替代它将收到一个心跳,而代表当前结果的值将会丢失。 // 为了防止没人接收心跳,增加了default,因为我们的heart channel创建时有一个缓冲区,所以如果有人正在监听暗示没有及时收到第一个心跳,接收者也可以收到心跳。 }()
return heartbeatStream, workStream }
done := make(chan interface{}) defer close(done)
heartbeat, results := doWork(done)
for { select { case _, ok := <-heartbeat: if ok == false { return } else { fmt.Println("pulse") } case r, ok := <-results: if ok == false { return } else { fmt.Printf("result %v\n", r) } } } }
func main() { doWork := func( done <-chan interface{}, id int, wg *sync.WaitGroup, result chan<- int, ) { started := time.Now() defer wg.Done()
simulatedLoadTime := time.Duration(1+rand.Intn(5)) * time.Second select { case <-done: case <-time.After(simulatedLoadTime): } select { case <-done: case result <- id: }
took := time.Since(started) if took < simulatedLoadTime { took = simulatedLoadTime } fmt.Printf("%v took %v.\n", id, took) }
done := make(chan interface{}) result := make(chan int)
var wg sync.WaitGroup wg.Add(10)
for i := 0; i < 10; i++ { go doWork(done, i, &wg, result) }
firstReturned := <-result close(done)
wg.Wait()
fmt.Printf("Received an answer from #%v.\n", firstReturned) }
func main() { var fib func(n int) <-chan int fib = func(n int) <-chan int { result := make(chan int) go func() { defer close(result) if n <= 2 { result <- 1 return } result <- <-fib(n-1) + <-fib(n-2) }() return result }
func main() { var data int go func() { data++ }() if data == 0 { fmt.Printf("the value is %d.\n", data) } }
执行go run -race test19.go
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
the value is 0. ================== WARNING: DATA RACE Write at 0x00c0000200c8 by goroutine 6: main.main.func1() /home/yuhao/tool/go/test/test19.go:8 +0x4e
Previous read at 0x00c0000200c8 by main goroutine: main.main() /home/yuhao/tool/go/test/test19.go:10 +0x88
Goroutine 6 (running) created at: main.main() /home/yuhao/tool/go/test/test19.go:7 +0x7a ================== Found 1 data race(s) exit status 66
所谓元编程就是编写直接生成或操纵程序的程序,C++ 模板给 C++ 语言提供了元编程的能力,模板使 C++ 编程变得异常灵活,能实现很多高级动态语言才有的特性(语法上可能比较丑陋,一些历史原因见下文)。普通用户对 C++ 模板的使用可能不是很频繁,大致限于泛型编程,但一些系统级的代码,尤其是对通用性、性能要求极高的基础库(如 STL、Boost)几乎不可避免的都大量地使用 C++ 模板,一个稍有规模的大量使用模板的程序,不可避免的要涉及元编程(如类型计算)。本文就是要剖析 C++ 模板元编程的机制。
template<typename T, int i> classcp00; // 用于模板型模板参数 // 通例 template<typename T1, typename T2, int i, template<typename, int> classCP> classTMP; // 完全特例化 template<> classTMP<int, float, 2, cp00>; // 第一个参数有const修饰 template<typename T1, typename T2, int i, template<typename, int> classCP> classTMP<const T1, T2, i, CP>; // 第一二个参数为cp00的实例且满足一定关系,第四个参数为cp00 template<typename T, int i> classTMP<cp00<T, i>, cp00<T, i+10>, i, cp00>; // 编译错误!,第四个参数类型和通例类型不一致 //template<template<int i> CP> //class TMP<int, float, 10, CP>;
关于模板特例化:
在定义模板特例之前必须已经有模板通例(primary template)的声明;
模板特例并不要求一定与通例有相同的接口,但为了方便使用(体会特例的语义)一般都相同;
匹配规则,在模板实例化时如果有模板通例、特例加起来多个模板版本可以匹配,则依据如下规则:对版本AB,如果 A 的模板参数取值集合是B的真子集,则优先匹配 A,如果 AB 的模板参数取值集合是“交叉”关系(AB 交集不为空,且不为包含关系),则发生编译错误,对于函数模板,用函数重载分辨(overload resolution)规则和上述规则结合并优先匹配非模板函数。
sh-4.2# g++ -std=c++11 -o main *.cpp main.cpp:7:28: error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum) instantiating 'class aTMP<-890>' enum { ret = N==0 ? 1 : N * aTMP<N-1>::ret }; ^ main.cpp:7:28: recursively required from 'class aTMP<9>' main.cpp:7:28: required from 'class aTMP<10>' main.cpp:11:23: required from here main.cpp:7:28: error: incomplete type 'aTMP<-890>' used in nested name specifier
global f() member f(): 99 member f(): 22 global f()
C++11 关于模板的新特性:
“>>” 根据上下文自动识别正确语义;
函数模板参数默认值;
变长模板参数(扩展 sizeof…() 获取参数个数);
模板别名(扩展 using 关键字);
外部模板实例(拓展 extern 关键字),弃用 export template。
在本文中,如无特别声明将不使用 C++11 的特性(除了 “>>”)。
模板元编程概述
如果对 C++ 模板不熟悉(光熟悉语法还不算熟悉),可以先跳过本节,往下看完例子再回来。
C++ 模板最初是为实现泛型编程设计的,但人们发现模板的能力远远不止于那些设计的功能。一个重要的理论结论就是:C++ 模板是图灵完备的(Turing-complete),其证明过程请见文献[8](就是用 C++ 模板模拟图灵机),理论上说 C++ 模板可以执行任何计算任务,但实际上因为模板是编译期计算,其能力受到具体编译器实现的限制(如递归嵌套深度,C++11 要求至少 1024,C++98 要求至少 17)。C++ 模板元编程是“意外”功能,而不是设计的功能,这也是 C++ 模板元编程语法丑陋的根源。
C++ 模板是图灵完备的,这使得 C++ 成为两层次语言(two-level languages,中文暂且这么翻译,文献[9]),其中,执行编译计算的代码称为静态代码(static code),执行运行期计算的代码称为动态代码(dynamic code),C++ 的静态代码由模板实现(预处理的宏也算是能进行部分静态计算吧,也就是能进行部分元编程,称为宏元编程,见 Boost 元编程库即 BCCL,文献[16]和文献[1] 10.4)。
具体来说 C++ 模板可以做以下事情:编译期数值计算、类型计算、代码计算(如循环展开),其中数值计算实际不太有意义,而类型计算和代码计算可以使得代码更加通用,更加易用,性能更好(也更难阅读,更难调试,有时也会有代码膨胀问题)。编译期计算在编译过程中的位置请见下图(取自文献[10]),可以看到关键是模板的机制在编译具体代码(模板实例)前执行:
sh-4.2# g++ -std=c++11 -fpermissive -o main *.cpp main.cpp: In member function 'void Prime_print<2>::f()': main.cpp:17:33: warning: invalid conversion from 'int' to 'void*' [-fpermissive] void f() { D<2> d = prim ? 1 : 0; } ^ main.cpp:2:28: warning: initializing argument 1 of 'D<i>::D(void*) [with int i = 2]' [-fpermissive] template<int i> struct D { D(void*); operator int(); }; ^ main.cpp: In instantiation of 'void Prime_print<i>::f() [with int i = 7]': main.cpp:13:36: recursively required from 'void Prime_print<i>::f() [with int i = 9]' main.cpp:13:36: required from 'void Prime_print<i>::f() [with int i = 10]' main.cpp:25:27: required from here main.cpp:13:33: warning: invalid conversion from 'int' to 'void*' [-fpermissive] void f() { D<i> d = prim ? 1 : 0; a.f(); } ^ main.cpp:2:28: warning: initializing argument 1 of 'D<i>::D(void*) [with int i = 7]' [-fpermissive] template<int i> struct D { D(void*); operator int(); }; ^ main.cpp: In instantiation of 'void Prime_print<i>::f() [with int i = 5]': main.cpp:13:36: recursively required from 'void Prime_print<i>::f() [with int i = 9]' main.cpp:13:36: required from 'void Prime_print<i>::f() [with int i = 10]' main.cpp:25:27: required from here main.cpp:13:33: warning: invalid conversion from 'int' to 'void*' [-fpermissive] void f() { D<i> d = prim ? 1 : 0; a.f(); } ^ main.cpp:2:28: warning: initializing argument 1 of 'D<i>::D(void*) [with int i = 5]' [-fpermissive] template<int i> struct D { D(void*); operator int(); }; ^ main.cpp: In instantiation of 'void Prime_print<i>::f() [with int i = 3]': main.cpp:13:36: recursively required from 'void Prime_print<i>::f() [with int i = 9]' main.cpp:13:36: required from 'void Prime_print<i>::f() [with int i = 10]' main.cpp:25:27: required from here main.cpp:13:33: warning: invalid conversion from 'int' to 'void*' [-fpermissive] void f() { D<i> d = prim ? 1 : 0; a.f(); } ^ main.cpp:2:28: warning: initializing argument 1 of 'D<i>::D(void*) [with int i = 3]' [-fpermissive] template<int i> struct D { D(void*); operator int(); };
上面例子已经实现了存储类型的元容器,和元容器上的查找算法,但还有一个小问题,就是它不能处理模板,编译器对模板的操纵能力远不如对类型的操纵能力强(提示:类模板实例是类型),我们可以一种间接方式实现存储“模板元素”,即用模板的一个代表实例(如全用 int 为参数的实例)来代表这个模板,这样对任意模板实例,只需判断其模板的代表实例是否在容器中即可,这需要进行类型过滤:对任意模板的实例将其替换为指定模板参数的代表实例,类型过滤实例代码如:
Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST. Assume a BST is defined as follows:
For example:
1 2 3 4 5 6 7
Given BST [1,null,2,2], 1 \ 2 / 2 return [2].
Note: If a tree has more than one mode, you can return them in any order.
classSolution { public: voidinorder(TreeNode* root, unordered_map<int, int>& m, int& mx){ if(root == NULL) return; inorder(root->left, m, mx); mx = max(mx, ++m[root->val]); inorder(root->right, m, mx); } vector<int> findMode(TreeNode* root){ vector<int> res; unordered_map<int, int> m; int mx = -1; inorder(root, m, mx); for(unordered_map<int, int>::iterator p = m.begin(); p != m.end(); p ++) { if(p->second == mx) res.push_back(p->first); } return res; } };
Leetcode502. IPO
Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.
You are given several projects. For each project i, it has a pure profit Pi and a minimum capital of Ci is needed to start the corresponding project. Initially, you have W capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital.
To sum up, pick a list of at most k distinct projects from given projects to maximize your final capital, and output your final maximized capital.
Explanation: Since your initial capital is 0, you can only start the project indexed 0. After finishing it you will obtain profit 1 and your capital becomes 1. With capital 1, you can either start the project indexed 1 or the project indexed 2. Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital. Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.
Note:
You may assume all numbers in the input are non-negative integers.
The length of Profits array and Capital array will not exceed 50,000.
The answer is guaranteed to fit in a 32-bit signed integer.
classSolution { public: intfindMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital){ priority_queue<pair<int, int>> maxH; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minH; for (int i = 0; i < Capital.size(); ++i) { minH.push({Capital[i], Profits[i]}); } for (int i = 0; i < k; ++i) { while (!minH.empty() && minH.top().first <= W) { auto t = minH.top(); minH.pop(); maxH.push({t.second, t.first}); } if (maxH.empty()) break; W += maxH.top().first; maxH.pop(); } return W; } };
Leetcode503. Next Greater Element II
Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn’t exist, output -1 for this number.
Example 1:
1 2 3 4 5
Input: [1,2,1] Output: [2,-1,2] Explanation: The first 1's next greater number is 2; The number 2 can't find next greater number; The second 1's next greater number needs to search circularly, which is also 2.
Given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: “Gold Medal”, “Silver Medal” and “Bronze Medal”.
Example 1:
1 2 3
Input: [5, 4, 3, 2, 1] Output: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"] Explanation: The first three athletes got the top three highest scores, so they got "Gold Medal", "Silver Medal" and "Bronze Medal". For the left two athletes, you just need to output their relative ranks according to their scores.
classSolution { public: boolcheckPerfectNumber(int num){ int sum = 0; if(num == 0) returnfalse; for(int i = 1; i <= num/2; i ++) { if(num%i == 0) sum += i; } return sum == num; } };
Leetcode508. Most Frequent Subtree Sum
Given the root of a binary tree, return the most frequent subtree sum. If there is a tie, return all the values with the highest frequency in any order.
The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself).
Example 1:
1 2
Input: root = [5,2,-3] Output: [2,-3,4]
Example 2:
1 2
Input: root = [5,2,-5] Output: [2]
这道题给了我们一个二叉树,让我们求出现频率最高的子树之和,求树的结点和并不是很难,就是遍历所有结点累加起来即可。那么这道题的暴力解法就是遍历每个结点,对于每个结点都看作子树的根结点,然后再遍历子树所有结点求和,这样也许可以通过 OJ,但是绝对不是最好的方法。我们想下子树有何特点,必须是要有叶结点,单独的一个叶结点也可以当作是子树,那么子树是从下往上构建的,这种特点很适合使用后序遍历,我们使用一个 HashMap 来建立子树和跟其出现频率的映射,用一个变量 cnt 来记录当前最多的次数,递归函数返回的是以当前结点为根结点的子树结点值之和,然后在递归函数中,我们先对当前结点的左右子结点调用递归函数,然后加上当前结点值,然后更新对应的 HashMap 中的值,然后看此时 HashMap 中的值是否大于等于 cnt,大于的话首先要清空 res,等于的话不用,然后将 sum 值加入结果 res 中即可,参见代码如下:
classSolution { public: vector<int> findFrequentTreeSum(TreeNode* root){ vector<int> res; int cnt = 0; unordered_map<int, int> map; dfs(root, map, res, cnt); return res; } intdfs(TreeNode* root, unordered_map<int, int> &map, vector<int>& res, int &cnt){ if (root == NULL) return0; int left = dfs(root->left, map, res, cnt); int right = dfs(root->right, map, res, cnt); int sum = left + right + root->val; map[sum] ++;
if (map[sum] >= cnt) { if (map[sum] > cnt) res.clear(); cnt = map[sum]; res.push_back(sum); } return sum; } };
Leetcode509. Fibonacci Number
The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), for N > 1. Given N, calculate F(N).
classSolution { public: intlongestPalindromeSubseq(string s){ int n = s.size(); vector<vector<int>> memo(n, vector<int>(n, -1)); returnhelper(s, 0, n - 1, memo); } inthelper(string& s, int i, int j, vector<vector<int>>& memo){ if (memo[i][j] != -1) return memo[i][j]; if (i > j) return0; if (i == j) return1; if (s[i] == s[j]) { memo[i][j] = helper(s, i + 1, j - 1, memo) + 2; } else { memo[i][j] = max(helper(s, i + 1, j, memo), helper(s, i, j - 1, memo)); } return memo[i][j]; } };
Leetcode518. Coin Change 2
You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.
Note: You can assume that
0 <= amount <= 5000
1 <= coin <= 5000
the number of coins is less than 500
the answer is guaranteed to fit into signed 32-bit integer
Example 1:
1 2 3 4 5 6 7
Input: amount = 5, coins = [1, 2, 5] Output: 4 Explanation: there are four ways to make up the amount: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
Example 2:
1 2 3
Input: amount = 3, coins = [2] Output: 0 Explanation: the amount of 3 cannot be made up just with coins of 2.
classSolution { public: intchange(int amount, vector<int>& coins){ if (amount == 0) return1; if (coins.empty()) return0; map<pair<int, int>, int> memo; returnhelper(amount, coins, 0, memo); } inthelper(int amount, vector<int>& coins, int idx, map<pair<int, int>, int>& memo){ if (amount == 0) return1; elseif (idx >= coins.size()) return0; elseif (idx == coins.size() - 1) return amount % coins[idx] == 0; if (memo.count({amount, idx})) return memo[{amount, idx}]; int val = coins[idx], res = 0; for (int i = 0; i * val <= amount; ++i) { int rem = amount - i * val; res += helper(rem, coins, idx + 1, memo); } return memo[{amount, idx}] = res; } };
Leetcode519. Random Flip Matrix
You are given the number of rows n_rows and number of columns n_cols of a 2D binary matrix where all values are initially 0. Write a function flip which chooses a 0 value uniformly at random, changes it to 1, and then returns the position [row.id, col.id] of that value. Also, write a function reset which sets all values back to 0. Try to minimize the number of calls to system’s Math.random() and optimize the time and space complexity.
Note:
1 <= n_rows, n_cols <= 10000
0 <= row.id < n_rows and 0 <= col.id < n_cols
flip will not be called when the matrix has no 0 values left.
the total number of calls to flip and reset will not exceed 1000.
Input: ["Solution","flip","flip","reset","flip"] [[1,2],[],[],[],[]] Output: [null,[0,0],[0,1],null,[0,0]] Explanation of Input Syntax: The input is two lists: the subroutines called and their arguments. Solution's constructor has two arguments, n_rows and n_cols. flip and resethave no arguments. Arguments are always wrapped with a list, even if there aren't any.
classSolution { public: boolisbig(char c){ if(c >= 'A' && c <= 'Z') returntrue; returnfalse; } booldetectCapitalUse(string word){ int flag = false; if(isbig(word[0])) flag = isbig(word[1]); else flag = false; for(int i = 1; i < word.length(); i ++) if(flag != isbig(word[i])) returnfalse; returntrue; } };
Leetcode521. Longest Uncommon Subsequence I
Given two strings, you need to find the longest uncommon subsequence of this two strings. The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be any subsequence of the other string.
A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements. Trivially, any string is a subsequence of itself and an empty string is a subsequence of any string.
The input will be two strings, and the output needs to be the length of the longest uncommon subsequence. If the longest uncommon subsequence doesn’t exist, return -1.
Example 1:
1 2 3 4 5 6
Input: a = "aba", b = "cdc" Output: 3 Explanation: The longest uncommon subsequence is "aba", because "aba" is a subsequence of "aba", but not a subsequence of the other string "cdc". Note that "cdc" can be also a longest uncommon subsequence.
classSolution { public: intfindLUSlength(string a, string b){ return a == b ? -1 : max(a.length(), b.length()); } };
Leetcode522. Longest Uncommon Subsequence II 题解
Given a list of strings, you need to find the longest uncommon subsequence among them. The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be any subsequence of the other strings.
A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements. Trivially, any string is a subsequence of itself and an empty string is a subsequence of any string.
The input will be a list of strings, and the output needs to be the length of the longest uncommon subsequence. If the longest uncommon subsequence doesn’t exist, return -1.
Example 1:
1 2 3 4 5
Input: "aba", "cdc", "eae" Output: 3 Note: All the given strings' lengths will not exceed 10. The length of the given list will be in the range of [2, 50].
classSolution { public: intfindLUSlength(vector<string>& strs){ int len = strs.size(); int res = -1; for (int i = 0; i < len; i ++) { int j = 0; for (j = 0; j < len; j ++) { if (i == j) continue; if (issubstr(strs[j], strs[i])) break; } if (j == len) res = max(res, (int)(strs[i].length())); } return res; } intissubstr(string& str1, string& str2){ int p1 = 0, p2 = 0; int len1 = str1.length(), len2 = str2.length(); while(p1 < len1) { if (p2 >= len2) break; if (str1[p1] == str2[p2]) p2 ++; p1 ++; } return p2 == len2; } };
Leetcode523. Continuous Subarray Sum
Given an integer array nums and an integer k, return true if nums has a continuous subarray of size at least two whose elements sum up to a multiple of k, or false otherwise.
An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.
Example 1:
1 2 3
Input: nums = [23,2,4,6,7], k = 6 Output: true Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.
Example 2:
1 2 3 4
Input: nums = [23,2,6,4,7], k = 6 Output: true Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42. 42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.
classSolution { public: boolcheckSubarraySum(vector<int>& nums, int k){ int n = nums.size(), sum = 0, pre = 0; unordered_set<int> st; for (int i = 0; i < n; ++i) { sum += nums[i]; int t = (k == 0) ? sum : (sum % k); if (st.count(t)) returntrue; st.insert(pre); pre = t; } returnfalse; } };
既然 HashSet 可以做,一般来说用 HashMap 也可以做,这里我们建立余数和当前位置之间的映射,由于有了位置信息,就不需要 pre 变量了,之前用保存的坐标和当前位置i比较判断就可以了,参见代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classSolution { public: boolcheckSubarraySum(vector<int>& nums, int k){ int n = nums.size(), sum = 0; unordered_map<int, int> m{{0,-1}}; for (int i = 0; i < n; ++i) { sum += nums[i]; int t = (k == 0) ? sum : (sum % k); if (m.count(t)) { if (i - m[t] > 1) returntrue; } else m[t] = i; } returnfalse; } };
Leetcode524. Longest Word in Dictionary through Deleting
Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.
Example 1:
1 2
Input: s = "abpcplea", d = ["ale","apple","monkey","plea"] Output: "apple"
Example 2:
1 2
Input: s = "abpcplea", d = ["a","b","c"] Output: "a"
Note:
All the strings in the input will only contain lower-case letters.
The size of the dictionary won’t exceed 1,000.
The length of all the strings in the input won’t exceed 1,000.
classSolution { public: intfindMaxLength(vector<int>& nums){ map<int, int> m{{0, -1}}; int sum = 0, res = 0; for (int i = 0;i < nums.size(); i ++) { if (nums[i] == 1) sum ++; else sum --; if (m.count(sum)) res = max(res, i-m[sum]); else m[sum] = i; } return res; } };
Leetcode526. Beautiful Arrangement
Suppose you have n integers labeled 1 through n. A permutation of those n integers perm (1-indexed) is considered a beautiful arrangement if for every i (1 <= i <= n), either of the following is true:
perm[i] is divisible by i.
i is divisible by perm[i].
Given an integer n, return the number of the beautiful arrangements that you can construct.
Example 1:
1 2 3 4 5 6 7 8 9
Input: n = 2 Output: 2 Explanation: The first beautiful arrangement is [1,2]: - perm[1] = 1 is divisible by i = 1 - perm[2] = 2 is divisible by i = 2 The second beautiful arrangement is [2,1]: - perm[1] = 2 is divisible by i = 1 - i = 2 is divisible by perm[2] = 1
classSolution { public: intcountArrangement(int n){ int res = 0; vector<bool> visited(n, false); dfs(n, 1, visited, res); return res; } voiddfs(int n, int cur, vector<bool> visited, int& res){ if (cur > n) { res ++; return ; } for (int i = 1; i <= n; i ++) { if (visited[i-1] || (i%cur != 0 && cur%i != 0)) continue; visited[i-1] = true; dfs(n, cur+1, visited, res); visited[i-1] = false; } } };
Leetcode528. Random Pick with Weight
Given an array w of positive integers, where w[i] describes the weight of index i, write a function pickIndex which randomly picks an index in proportion to its weight.
Explanation of Input Syntax: The input is two lists: the subroutines called and their arguments. Solution‘s constructor has one argument, the array w. pickIndex has no arguments. Arguments are always wrapped with a list, even if there aren’t any.
classSolution { public: vector<int> cumulative; int sum; Solution(vector<int>& w) { cumulative.resize(w.size(), w[0]); sum = w[0]; for (int i = 1; i < w.size(); i ++) { cumulative[i] = cumulative[i-1] + w[i]; sum += w[i]; } } intpickIndex(){ int x = rand() % sum; int left = 0, right = cumulative.size()-1, mid; while(left < right) { mid = left + (right-left) / 2; if (cumulative[mid] <= x) left = mid + 1; else right = mid; } return right; } };
Leetcode529. Minesweeper
Let’s play the minesweeper game (Wikipedia, online game)!
You are given an m x n char matrix board representing the game board where:
‘M’ represents an unrevealed mine,
‘E’ represents an unrevealed empty square,
‘B’ represents a revealed blank square that has no adjacent mines (i.e., above, below, left, right, and all 4 diagonals),
digit (‘1’ to ‘8’) represents how many mines are adjacent to this revealed square, and
‘X’ represents a revealed mine.
You are also given an integer array click where click = [clickr, clickc] represents the next click position among all the unrevealed squares (‘M’ or ‘E’).
Return the board after revealing this position according to the following rules:
If a mine ‘M’ is revealed, then the game is over. You should change it to ‘X’.
If an empty square ‘E’ with no adjacent mines is revealed, then change it to a revealed blank ‘B’ and all of its adjacent unrevealed squares should be revealed recursively.
If an empty square ‘E’ with at least one adjacent mine is revealed, then change it to a digit (‘1’ to ‘8’) representing the number of adjacent mines.
Return the board when no more squares will be revealed.
classSolution { public: vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) { if (board.empty() || board[0].empty()) return {}; int m = board.size(), n = board[0].size(), row = click[0], col = click[1], cnt = 0; if (board[row][col] == 'M') { board[row][col] = 'X'; } else { for (int i = -1; i < 2; ++i) { for (int j = -1; j < 2; ++j) { int x = row + i, y = col + j; if (x < 0 || x >= m || y < 0 || y >= n) continue; if (board[x][y] == 'M') ++cnt; } } if (cnt > 0) { board[row][col] = cnt + '0'; } else { board[row][col] = 'B'; for (int i = -1; i < 2; ++i) { for (int j = -1; j < 2; ++j) { int x = row + i, y = col + j; if (x < 0 || x >= m || y < 0 || y >= n) continue; if (board[x][y] == 'E') { vector<int> nextPos{x, y}; updateBoard(board, nextPos); } } } } } return board; } };
classSolution { public: voidinorder(TreeNode* root, int &pre, int &res){ if(root == NULL) return; inorder(root->left, pre, res); if(pre != -1) res = min(abs(pre-root->val), res); pre = root->val; inorder(root->right, pre, res); } intgetMinimumDifference(TreeNode* root){ int res = INT_MAX, pre = -1; inorder(root, pre, res); return res; } };
Leetcode532. K-diff Pairs in an Array
Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.
Example 1:
1 2 3 4
Input: [3, 1, 4, 1, 5], k = 2 Output: 2 Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5). Although we have two 1s in the input, we should only return the number of unique pairs.
Example 2:
1 2 3
Input:[1, 2, 3, 4, 5], k = 1 Output: 4 Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).
Example 3:
1 2 3
Input: [1, 3, 1, 5, 4], k = 0 Output: 1 Explanation: There is one 0-diff pair in the array, (1, 1).
这道题给了我们一个含有重复数字的无序数组,还有一个整数k,让找出有多少对不重复的数对 (i, j) 使得i和j的差刚好为k。由于k有可能为0,而只有含有至少两个相同的数字才能形成数对,那么就是说需要统计数组中每个数字的个数。可以建立每个数字和其出现次数之间的映射,然后遍历 HashMap 中的数字,如果k为0且该数字出现的次数大于1,则结果 res 自增1;如果k不为0,且用当前数字加上k后得到的新数字也在数组中存在,则结果 res 自增1。
Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.
classSolution { public: map<string, int> map1; map<int, string> map2; string s="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"; // Encodes a URL to a shortened URL. string encode(string longUrl){ map<string,int>::iterator key = map1.find(longUrl); if(key==map1.end()) { map1.insert(map<string, int>::value_type (longUrl,map1.size()+1)); map2.insert(map<int, string>::value_type (map2.size()+1,longUrl)); } int n=map2.size(); string result; // n is the number of longUrl while(n>0){ printf("(%d) ",n); int r = n%62; n /= 62; result.append(1,s[r]); } //printf("%s\n",result); return result; }
// Decodes a shortened URL to its original URL. string decode(string shortUrl){ int length = shortUrl.size(); int val=0; for(int i=0;i<length;i++){ val = val*62+s.find(shortUrl[i]); } return map2.find(val)->second; } };
// Your Solution object will be instantiated and called as such: // Solution solution; // solution.decode(solution.encode(url));
string alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"; unordered_map<string, string> map; string key = getRandom(); string getRandom(){ string s; for (int i = 0; i < 6 ; i++) { s += alphabet[rand() % 61]; } return s; } // Encodes a URL to a shortened URL. string encode(string longUrl){ while(map.count(key)) { key = getRandom(); } map.insert(make_pair(key, longUrl)); return"http://tinyurl.com/" + key; } // Decodes a shortened URL to its original URL. string decode(string shortUrl){ return map.at(shortUrl.replace(0,shortUrl.size()-6,"")); } };
Leetcode537. Complex Number Multiplication
Given two strings representing two complex numbers. You need to return a string representing their multiplication. Note i2 = -1 according to the definition.
Example 1:
1 2 3
Input: "1+1i", "1+1i" Output: "0+2i" Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.
Example 2:
1 2 3
Input: "1+-1i", "1+-1i" Output: "0+-2i" Explanation: (1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i, and you need convert it to the form of 0+-2i.
Note:
The input strings will not have extra blank.
The input strings will be given in the form of a+bi, where the integer a and b will both belong to the range of [-100, 100]. - And the output should be also in this form.
Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.
Example:
1 2 3 4 5 6 7 8 9
Input: The root of a Binary Search Tree like this: 5 / \ 2 13
Output: The root of a Greater Tree like this: 18 / \ 20 13
classSolution { public: intgettime(string& timePoint){ return ((timePoint[0]-'0')*10 + timePoint[1]-'0')*60 + (timePoint[3]-'0')*10 + timePoint[4]-'0'; } intfindMinDifference(vector<string>& timePoints){ int n = timePoints.size(), res = INT_MAX, tmp; vector<int> times; for (int i = 0; i < n; i ++) times.push_back(gettime(timePoints[i])); sort(times.begin(), times.end());
for (int i = 0; i < n; i ++) { tmp = times[(i+1)%n] - times[i]; if (i == n-1) tmp += 24*60; res = min(res, tmp); } return res; } };
Leetcode540. Single Element in a Sorted Array
Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.
Example 1:
1 2
Input: [1,1,2,3,3,4,4,8,8] Output: 2
Example 2:
1 2
Input: [3,3,7,7,10,11,11] Output: 10
Note: Your solution should run in O(log n) time and O(1) space.
classSolution { public: intsingleNonDuplicate(vector<int>& nums){ int left = 0, right = nums.size() - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] == nums[mid ^ 1]) left = mid + 1; else right = mid; } return nums[left]; } };
Leetcode541. Reverse String II
Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original.
classSolution { public: string reverseStr(string s, int k){ int len = s.length(); if(len == 0) return""; string sb = ""; int index = 0; while (index < len){ string tmp = ""; for (int i = index; i < k + index && i < len; i++) { tmp += s[i]; } index += k; reverse(tmp.begin(), tmp.end()); sb = sb + tmp; for (int i = index; i < k + index && i < len; i++){ sb += s[i]; } index += k; } return sb; } };
Leetcode542. 01 Matrix
Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.
classSolution { public: vector<vector<int>> updateMatrix(vector<vector<int>>& mat) { int m = mat.size(), n = mat[0].size(); vector<vector<int>> dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; queue<pair<int, int>> q; for (int i = 0; i < m; i ++) for (int j = 0; j < n; j ++) if (mat[i][j] == 0) q.push({i, j}); else mat[i][j] = INT_MAX; while(!q.empty()) { pair<int, int> t = q.front(); q.pop(); for (int i = 0; i < 4; i ++) { int x = t.first + dir[i][0]; int y = t.second + dir[i][1]; if (x < 0 || x >= m || y < 0 || y >= n || mat[x][y] <= mat[t.first][t.second]) continue; mat[x][y] = mat[t.first][t.second] + 1; q.push({x, y}); } } return mat; } };
Leetcode543. Diameter of Binary Tree
Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
Example:
1 2 3 4 5 6 7
Given a binary tree 1 / \ 2 3 / \ 4 5 Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
classSolution { public: intdfs(TreeNode* root, int &maxx){ if(root == NULL) return0; int left = dfs(root->left, maxx); int right = dfs(root->right, maxx); maxx = max(right+left, maxx); returnmax(right, left) + 1; } intdiameterOfBinaryTree(TreeNode* root){ if(root == NULL) return0; int maxx = -1; dfs(root, maxx); return maxx; } };
Leetcode547. Number of Provinces
There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.
A province is a group of directly or indirectly connected cities and no other cities outside of the group.
You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.
classSolution { public: intfindCircleNum(vector<vector<int>>& isConnected){ if (isConnected.size() == 0) return0; int res = 0, n = isConnected.size(); vector<int> visited(n, 0); for (int i = 0; i < n; i ++) { if (visited[i]) continue; helper(isConnected, i, n, visited); res ++; } return res; } voidhelper(vector<vector<int>>& isConnected, int i, int n, vector<int>& visited){ visited[i] = true; for (int ii = 0; ii < n; ii ++) if (isConnected[i][ii] && !visited[ii]) helper(isConnected, ii, n, visited); } };
Leetcode551. Student Attendance Record I
You are given a string representing an attendance record for a student. The record only contains the following three characters:
‘A’ : Absent.
‘L’ : Late.
‘P’ : Present. A student could be rewarded if his attendance record doesn’t contain more than one ‘A’ (absent) or more than two continuous ‘L’ (late).
You need to return whether the student could be rewarded according to his attendance record.
You are given an integer array nums. The adjacent integers in nums will perform the float division.
For example, for nums = [2,3,4], we will evaluate the expression “2/3/4”. However, you can add any number of parenthesis at any position to change the priority of operations. You want to add these parentheses such the value of the expression after the evaluation is maximum.
Return the corresponding expression that has the maximum value in string format.
Note: your expression should not contain redundant parenthesis.
Example 1:
1 2 3 4 5 6 7 8 9 10
Input: nums = [1000,100,10,2] Output: "1000/(100/10/2)" Explanation: 1000/(100/10/2) = 1000/((100/10)/2) = 200 However, the bold parenthesis in "1000/((100/10)/2)" are redundant, since they don't influence the operation priority. So you should return "1000/(100/10/2)". Other cases: 1000/(100/10)/2 = 50 1000/(100/(10/2)) = 50 1000/100/10/2 = 0.5 1000/100/(10/2) = 2
那么我们如何加括号使得其值最大呢,那么就是将x2后面的除数都变成乘数,比如只有三个数字的情况 a / b / c,如果我们在后两个数上加上括号 a / (b / c),实际上就是a / b * c。而且b永远只能当除数,a也永远只能当被除数。同理,x1只能当被除数,x2只能当除数,但是x3之后的数,只要我们都将其变为乘数,那么得到的值肯定是最大的,所以就只有一种加括号的方式,即:
classSolution { public: string optimalDivision(vector<int>& nums){ if (nums.size() == 0) return""; int len = nums.size(); string res = ""; res += to_string(nums[0]); for (int i = 1; i < len; i ++) { if (i != 1 || len == 2) res += ("/" + to_string(nums[i])); else res += ("/(" + to_string(nums[i])); } if (len > 2) res += ")"; return res; } };
Leetcode554. Brick Wall
There is a brick wall in front of you. The wall is rectangular and has several rows of bricks. The bricks have the same height but different width. You want to draw a vertical line from the top to the bottom and cross the leastbricks.
The brick wall is represented by a list of rows. Each row is a list of integers representing the width of each brick in this row from left to right.
If your line go through the edge of a brick, then the brick is not considered as crossed. You need to find out how to draw the line to cross the least bricks and return the number of crossed bricks.
You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks.
The width sum of bricks in different rows are the same and won’t exceed INT_MAX.
The number of bricks in each row is in range [1,10,000]. The height of wall is in range [1,10,000]. Total number of bricks of the wall won’t exceed 20,000.
这道题给了我们一个砖头墙壁,上面由不同的长度的砖头组成,让选个地方从上往下把墙劈开,使得被劈开的砖头个数最少,前提是不能从墙壁的两边劈,这样没有什么意义。这里使用一个 HashMap 来建立每一个断点的长度和其出现频率之间的映射,这样只要从断点频率出现最多的地方劈墙,损坏的板砖一定最少。遍历砖墙的每一层,新建一个变量 sum,然后从第一块转头遍历到倒数第二块,将当前转头长度累加到 sum 上,这样每次得到的 sum 就是断点的长度,将其在 HashMap 中的映射值自增1,并且每次都更新下最大的映射值到变量 mx,这样最终 mx 就是出现次数最多的断点值,在这里劈开,绝对损伤的转头数量最少,参见代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
classSolution { public: intleastBricks(vector<vector<int>>& wall){ map<int, int> m; int res = 0; for (int i = 0; i < wall.size(); i ++) { int sum = 0; for (int j = 0; j < wall[i].size()-1; j ++) { sum += wall[i][j]; m[sum] ++; res = max(res, m[sum]); } } for (auto it = m.begin(); it != m.end(); it ++) res = max(res, it->second); return wall.size() - res; } };
Leetcode556. Next Greater Element III
Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive 32-bit integer exists, you need to return -1.
classSolution { public: staticboolcomp(int &a, int &b){ return a > b; } intnextGreaterElement(int n){ vector<int> nums; while(n > 0) { nums.push_back(n%10); n /= 10; } int len = nums.size(); int j, i = len-1; for (i = 0; i < len-1; i ++) if (nums[i] > nums[i+1]) break; if (i == len-1) return-1; i ++; for (j = 0; j < len-1; j ++) if (nums[j] > nums[i]) break; int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; sort(nums.begin(), nums.begin()+i, comp); longint res = 0; for (i = len-1; i >= 0; i --) { res = res * 10 + nums[i]; if (res > INT_MAX) return-1; } return res; } };
Leetcode557. Reverse Words in a String III
Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
Example 1: Input: “Let’s take LeetCode contest” Output: “s’teL ekat edoCteeL tsetnoc” Note: In the string, each word is separated by single space and there will not be any extra space in the string.
string reverseWords(string s){ size_t front = 0; for(int i = 0; i <= s.length(); ++i){ if(i == s.length() || s[i] == ' '){ reverse(&s[front], &s[i]); front = i + 1; } } return s;
用python一行就可以搞定
1
return" ".join([i[::-1] for i in s.split()])
Leetcode558. Quad Tree Intersection
A quadtree is a tree data in which each internal node has exactly four children: topLeft, topRight, bottomLeft and bottomRight. Quad trees are often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions.
We want to store True/False information in our quad tree. The quad tree is used to represent a N * N boolean grid. For each node, it will be subdivided into four children nodes until the values in the region it represents are all the same. Each node has another two boolean attributes : isLeaf and val. isLeafis true if and only if the node is a leaf node. The val attribute for a leaf node contains the value of the region it represents.
For example, below are two quad trees A and B:
A:
1 2 3 4 5 6 7 8 9 10 11 12 13
+-------+-------+ T: true | | | F: false | T | T | | | | +-------+-------+ | | | | F | F | | | | +-------+-------+ topLeft: T topRight: T bottomLeft: F bottomRight: F
B:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
+-------+---+---+ | | F | F | | T +---+---+ | | T | T | +-------+---+---+ | | | | T | F | | | | +-------+-------+ topLeft: T topRight: topLeft: F topRight: F bottomLeft: T bottomRight: T bottomLeft: T bottomRight: F
Your task is to implement a function that will take two quadtrees and return a quadtree that represents the logical OR (or union) of the two trees.
1 2 3 4 5 6 7 8 9 10
A: B: C (A or B): +-------+-------+ +-------+---+---+ +-------+-------+ | | | | | F | F | | | | | T | T | | T +---+---+ | T | T | | | | | | T | T | | | | +-------+-------+ +-------+---+---+ +-------+-------+ | | | | | | | | | | F | F | | T | F | | T | F | | | | | | | | | | +-------+-------+ +-------+-------+ +-------+-------+
Note:
Both A and B represent grids of size N * N.
N is guaranteed to be a power of 2.
If you want to know more about the quad tree, you can refer to its wiki.
The logic OR operation is defined as this: “A or B” is true if A is true, or if B is true, or if both A and B are true.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
For example, given a 3-ary tree:
We should return its max depth, which is 3.
Note:
The depth of the tree is at most 1000. The total number of nodes is at most 5000.
多叉树最大深度
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
classSolution { public: intmaxDepth(Node* root){ if(root == NULL) return0; if(root->children.size() == 0) return1; int maxx = -1; for(int i = 0; i < root->children.size(); i ++){ int temp = maxDepth(root->children[i]); if(maxx < temp) maxx = temp; } return maxx+1; } };
Leetcode560. Subarray Sum Equals K
Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
Example 1:
1 2
Input:nums = [1,1,1], k = 2 Output: 2
Note:
The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].
这道题给了我们一个数组,让求和为k的连续子数组的个数,博主最开始看到这道题想着肯定要建立累加和数组啊,然后遍历累加和数组的每个数字,首先看其是否为k,是的话结果 res 自增1,然后再加个往前的循环,这样可以快速求出所有的子数组之和,看是否为k,参见代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
classSolution { public: intsubarraySum(vector<int>& nums, int k){ int res = 0, n = nums.size(); vector<int> sums = nums; for (int i = 1; i < n; ++i) { sums[i] = sums[i - 1] + nums[i]; } for (int i = 0; i < n; ++i) { if (sums[i] == k) ++res; for (int j = i - 1; j >= 0; --j) { if (sums[i] - sums[j] == k) ++res; } } return res; } };
用一个 HashMap 来建立连续子数组之和跟其出现次数之间的映射,初始化要加入 {0,1} 这对映射,这是为啥呢,因为解题思路是遍历数组中的数字,用 sum 来记录到当前位置的累加和,建立 HashMap 的目的是为了可以快速的查找 sum-k 是否存在,即是否有连续子数组的和为 sum-k,如果存在的话,那么和为k的子数组一定也存在,这样当 sum 刚好为k的时候,那么数组从起始到当前位置的这段子数组的和就是k,满足题意,如果 HashMap 中事先没有 m[0] 项的话,这个符合题意的结果就无法累加到结果 res 中,这就是初始化的用途。上面讲解的内容顺带着也把 for 循环中的内容解释了,这里就不多阐述了,有疑问的童鞋请在评论区留言哈,参见代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13
classSolution { public: intsubarraySum(vector<int>& nums, int k){ int res = 0, sum = 0, n = nums.size(); unordered_map<int, int> m{{0, 1}}; for (int i = 0; i < n; ++i) { sum += nums[i]; res += m[sum - k]; ++m[sum]; } return res; } };
Leetcode561. Array Partition I
Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.
Example 1:
1 2
Input: [1,4,3,2] Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4). Note: n is a positive integer, which is in the range of [1, 10000]. All the integers in the array will be in the range of [-10000, 10000].
Given a binary tree, return the tilt of the whole tree.
The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. Null node has tilt 0.
The tilt of the whole tree is defined as the sum of all nodes’ tilt.
Example:
1 2 3 4 5 6 7 8 9 10
Input: 1 / \ 2 3 Output: 1 Explanation: Tilt of node 2 : 0 Tilt of node 3 : 0 Tilt of node 1 : |2-3| = 1 Tilt of binary tree : 0 + 0 + 1 = 1
classSolution { public: intdfs(TreeNode* root, int& ans){ if(root == NULL) return0; int left, right; left = dfs(root->left, ans); right = dfs(root->right, ans); int tilt = abs(left - right); ans += tilt; return left + right + root->val; } intfindTilt(TreeNode* root){ int ans = 0; dfs(root, ans); return ans; } };
Leetcode565. Array Nesting
A zero-indexed array A of length N contains all integers from 0 to N-1. Find and return the longest length of set S, where S[i] = {A[i], A[A[i]], A[A[A[i]]], … } subjected to the rule below.
Suppose the first element in S starts with the selection of element A[i] of index = i, the next element in S should be A[A[i]], and then A[A[A[i]]]… By that analogy, we stop adding right before a duplicate element occurs in S.
classSolution { public: intarrayNesting(vector<int>& nums){ int len = nums.size(); vector<bool> visited(len, false); int res = 0; for (int i = 0; i < len; i ++) { if (visited[i]) continue; res = max(res, helper(nums, i, visited)); } return res; } inthelper(vector<int>& nums, int start, vector<bool> &visited){ int len = nums.size(); int res = 0; while(start < len && !visited[start]) { visited[start] = true; res ++; start = nums[start]; } return res; } };
Leetcode566. Reshape the Matrix
In MATLAB, there is a very useful function called ‘reshape’, which can reshape a matrix into a new one with different size but keep its original data.
You’re given a matrix represented by a two-dimensional array, and two positive integers r and c representing the row number and column number of the wanted reshaped matrix, respectively.
The reshaped matrix need to be filled with all the elements of the original matrix in the same row-traversing order as they were.
If the ‘reshape’ operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.
Example 1:
1 2 3 4 5 6 7 8 9
Input: nums = [[1,2], [3,4]] r = 1, c = 4 Output: [[1,2,3,4]] Explanation: The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.
Example 2:
1 2 3 4 5 6 7 8 9 10
Input: nums = [[1,2], [3,4]] r = 2, c = 4 Output: [[1,2], [3,4]] Explanation: There is no way to reshape a 2 * 2 matrix to a 2 * 4 matrix. So output the original matrix.
classSolution { public: vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) { int m = nums.size(), n = nums[0].size(); if(m*n != r*c) return nums; vector<vector<int>> res(r, vector<int>(c, 0)); int ii = 0, jj = 0; for(int i = 0; i < m; i ++) for(int j = 0; j < n; j ++) { res[ii][jj] = nums[i][j]; if(jj == c - 1) { ii ++; jj = 0; } else jj ++; } return res; } };
Leetcode567. Permutation in String
Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string.
Example 1:
1 2 3
Input:s1 = "ab" s2 = "eidbaooo" Output:True Explanation: s2 contains one permutation of s1 ("ba").
Example 2:
1 2
Input:s1= "ab" s2 = "eidboaoo" Output: False
Note:
The input strings only contain lower case letters.
The length of both given strings is in range [1, 10,000].
classSolution { public: boolcheckInclusion(string s1, string s2){ int len1 = s1.length(), len2 = s2.length(); if (len1 > len2) returnfalse; unordered_map<char, int>::iterator it; unordered_map<char, int> m1, m2; for (int i = 0; i < len1; i ++) { m1[s1[i]] ++; m2[s2[i]] ++; } for (int i = len1; i < len2; i ++) { for (it = m1.begin(); it != m1.end(); it ++) { if (it->second != m2[it->first]) break; } if (it == m1.end()) returntrue; m2[s2[i-len1]] --; m2[s2[i]] ++; } for (it = m1.begin(); it != m1.end(); it ++) { if (it->second != m2[it->first]) break; } if (it == m1.end()) returntrue; returnfalse; } };
Leetcode572. Subtree of Another Tree
Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.
Example 1:
1 2 3 4 5 6 7 8 9 10 11
Given tree s: 3 / \ 4 5 / \ 1 2 Given tree t: 4 / \ 1 2 Return true, because t has the same structure and node values with a subtree of s.
Example 2:
1 2 3 4 5 6 7 8 9 10 11 12 13
Given tree s: 3 / \ 4 5 / \ 1 2 / 0 Given tree t: 4 / \ 1 2 Return false.
Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribute these candies equally in number to brother and sister. Return the maximum number of kinds of candies the sister could gain.
Example 1:
1 2 3 4 5 6
Input: candies = [1,1,2,2,3,3] Output: 3 Explanation: There are three different kinds of candies (1, 2 and 3), and two candies for each kind. Optimal distribution: The sister has candies [1,2,3] and the brother has candies [1,2,3], too. The sister has three different kinds of candies.
Example 2:
1 2 3 4
Input: candies = [1,1,2,3] Output: 2 Explanation: For example, the sister has candies [2,3] and the brother has candies [1,1]. The sister has two different kinds of candies, the brother has only one kind of candies.
classSolution { public: intdistributeCandies(vector<int>& candies){ int len = candies.size(); int unique = 0; sort(candies.begin(), candies.end()); for(int i = 0; i < len; i ++) if(i == 0 || candies[i] != candies[i-1]) unique ++; returnmin(unique, len/2); } };
LeetCode576. Out of Boundary Paths
There is an m by n grid with a ball. Given the start coordinate (i,j) of the ball, you can move the ball to adjacent cell or cross the grid boundary in four directions (up, down, left, right). However, you can at most move N times. Find out the number of paths to move the ball out of grid boundary. The answer may be very large, return it after mod 109 + 7.
Example 1:
1 2
Input:m = 2, n = 2, N = 2, i = 0, j = 0 Output: 6
Example 2:
1 2
Input:m = 1, n = 3, N = 3, i = 0, j = 1 Output: 12
Note:
Once you move the ball out of boundary, you cannot move it back.
The length and height of the grid is in range [1,50].
Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.
You need to find the shortest such subarray and output its length.
Example 1:
1 2 3
Input: [2, 6, 4, 8, 10, 9, 15] Output: 5 Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
Given two words word1 and word2 , find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.
Example 1:
1 2 3
Input: "sea", "eat" Output: 2 Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
Note:
The length of given words won’t exceed 500.
Characters in given words can only be lower-case letters.
Given a string expression representing an expression of fraction addition and subtraction, return the calculation result in string format.
The final result should be an irreducible fraction. If your final result is an integer, say 2, you need to change it to the format of a fraction that has a denominator 1. So in this case, 2 should be converted to 2/1.
classSolution { public: intfun(int m, int n){ if (m < 0) m = -m; if (n < 0) n = -n; if (m < n) { int tmp = m; m = n; n = tmp; } int rem; while(n > 0){ rem = m % n; m = n; n = rem; } return m; } intget_num(string e, int &i, int len){ int tmp = 0, flag = 1; if (e[i] == '-') { flag = -1; i ++; } elseif (e[i] == '+' || e[i] == '/') i ++; while(i < len && '0' <= e[i] && e[i] <= '9') { tmp = tmp*10 + e[i] - '0'; i ++; } return tmp*flag; } string fractionAddition(string expression){ int len = expression.length(), i = 0; vector<int> res; while(i < len) { if (res.size() == 0) { res.push_back(get_num(expression, i, len)); res.push_back(get_num(expression, i, len)); } else { int res0 = get_num(expression, i, len); int res1 = get_num(expression, i, len); res0 = res0 * res[1]; res[0] = res[0] * res1 + res0; res[1] = res[1] * res1; } }
if (res[0] == 0) return"0/1"; else { int t = fun(res[0], res[1]); res[0] /= t; res[1] /= t; returnto_string(res[0]) + "/" + to_string(res[1]); } return""; } };
Leetcode593. Valid Square
Given the coordinates of four points in 2D space p1, p2, p3 and p4, return true if the four points construct a square.
The coordinate of a point pi is represented as [xi, yi]. The input is not given in any order.
A valid square has four equal sides with positive length and four equal angles (90-degree angles).
classSolution { public: boolvalidSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4){ unordered_map<int, int> m; vector<vector<int>> v{p1, p2, p3, p4}; for (int i = 0; i < 4; ++i) { for (int j = i + 1; j < 4; ++j) { int x1 = v[i][0], y1 = v[i][1], x2 = v[j][0], y2 = v[j][1]; int dist = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2); if (dist == 0) returnfalse; ++m[dist]; } } return m.size() == 2; } };
Leetcode594. Longest Harmonious Subsequence
We define a harmounious array as an array where the difference between its maximum value and its minimum value is exactly 1. Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible subsequences.
Example 1:
1 2 3
Input: [1,3,2,2,5,2,3,7] Output: 5 Explanation: The longest harmonious subsequence is [3,2,2,2,3].
classSolution { public: intfindLHS(vector<int>& nums){ int res = 0; unordered_map<int, int> mp; for(int i = 0; i < nums.size(); i ++) mp[nums[i]] ++; for(auto i = mp.begin(); i != mp.end(); i ++) { if(mp.count(i->first+1)) res = max(res, i->second + mp[i->first+1]); } return res; } };
Leetcode595. Big Countries
We define a harmonious array is an array where the difference between its maximum value and its minimum value is exactly 1.
Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible subsequences.
Example 1:
1 2 3
Input: [1,3,2,2,5,2,3,7] Output: 5 Explanation: The longest harmonious subsequence is [3,2,2,2,3].
这道题给了我们一个数组,让我们找出最长的和谐子序列,关于和谐子序列就是序列中数组的最大最小差值均为1。由于这里只是让我们求长度,并不需要返回具体的子序列。所以我们可以对数组进行排序,那么实际上我们只要找出来相差为1的两个数的总共出现个数就是一个和谐子序列的长度了。明白了这一点,我们就可以建立一个数字和其出现次数之间的映射,利用 TreeMap 的自动排序的特性,那么我们遍历 TreeMap 的时候就是从小往大开始遍历,我们从第二个映射对开始遍历,每次跟其前面的映射对比较,如果二者的数字刚好差1,那么就把二个数字的出现的次数相加并更新结果 res 即可,参见代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
classSolution { public: intfindLHS(vector<int>& nums){ if (nums.empty()) return0; int res = 0; map<int, int> m; for (int num : nums) ++m[num]; for (auto it = next(m.begin()); it != m.end(); ++it) { auto pre = prev(it); if (it->first == pre->first + 1) { res = max(res, it->second + pre->second); } } return res; } };
Leetcode596. Classes More Than 5 Students
There is a table courses with columns: student and class Please list out all classes which have more than or equal to 5 students. For example, the table:
1 2 3 4 5 6 7 8 9 10 11 12 13
+---------+------------+ | student | class | +---------+------------+ | A | Math | | B | English | | C | Math | | D | Biology | | E | Math | | F | Computer | | G | Math | | H | Math | | I | Math | +---------+------------+
Should output:
1 2 3 4 5
+---------+ | class | +---------+ | Math | +---------+
1 2 3
SELECT class FROM courses GROUPBY class HAVINGCOUNT(DISTINCT(student)) >=5
Leetcode598. Range Addition II
Given an m * n matrix M initialized with all 0’s and several update operations.
Operations are represented by a 2D array, and each operation is represented by an array with two positive integers a and b, which means M[i][j] should be added by one for all 0 <= i < a and 0 <= j < b.
You need to count and return the number of maximum integers in the matrix after performing all the operations.
classSolution { public: intmaxCount(int m, int n, vector<vector<int>>& ops){ if(ops.size() == 0) return m * n; int res = 0; int min1 = 99999, min2 = 99999; for(int i = 0; i < ops.size(); i ++) { if(min1 > ops[i][0]) min1 = ops[i][0]; if(min2 > ops[i][1]) min2 = ops[i][1]; } return min1 * min2; } };
Leetcode599. Minimum Index Sum of Two Lists
Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants represented by strings.
You need to help them find out their common interest with the least list index sum. If there is a choice tie between answers, output all of them with no order requirement. You could assume there always exists an answer.
Example 1:
1 2 3 4 5
Input: ["Shogun", "Tapioca Express", "Burger King", "KFC"] ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"] Output: ["Shogun"] Explanation: The only restaurant they both like is "Shogun".
Example 2:
1 2 3 4 5
Input: ["Shogun", "Tapioca Express", "Burger King", "KFC"] ["KFC", "Shogun", "Burger King"] Output: ["Shogun"] Explanation: The restaurant they both like and have the least index sum is "Shogun" with index sum 1 (0+1).
classSolution { public: vector<string> findRestaurant(vector<string>& list1, vector<string>& list2){ unordered_map<string, int> mp; vector<string> ans; int res = 9999999; for(int i = 0; i < list1.size(); i ++) mp[list1[i]] = i; for(int i = 0; i < list2.size(); i ++) { auto temp = mp.find(list2[i]); if(temp != mp.end()) if(res >= i + temp->second) { if(res > i + temp->second) { ans.clear(); res = i + temp->second; } ans.push_back(temp->first); } } return ans; } };
Leetcode600. Non-negative Integers without Consecutive Ones
Given a positive integer n, find the number of non-negative integers less than or equal to n, whose binary representations do NOT contain consecutive ones.
Example 1:
1 2 3 4 5 6 7 8 9 10 11
Input: 5 Output: 5 Explanation: Here are the non-negative integers <= 5 with their corresponding binary representations: 0 : 0 1 : 1 2 : 10 3 : 11 4 : 100 5 : 101 Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule.
声明一个全局(外部)变量。当用extern声明一个全局变量的时候,首先应明确一点:extern的作用范围是整个工程,也就是说当我们在.h文件中写了extern int a;链接的时候链接器会去其他的.c文件中找有没有int a的定义,如果没有,链接报错;当extern int a;写在.c文件中时,链接器会在这个.c文件该声明语句之后找有没有int a的定义,然后去其他的.cpp文件中找,如果都找不到,链接报错。值得注意的一点:当extern语句出现在头文件中时,不要将声明和定义在一条语句中给出,也就是不要在头文件中写类似于这样的语句:extern int a = 1;,这种写法,在gcc编译时会给出一个警告:warning: 'a' initialized and declared 'extern',
所有一般(提倡)的做法是:只在头文件中通过extern给出全局变量的声明(即external int a; 而不要写成external int a = 1;),并在源文件中给出定义(并且只能定义一次)
#include<stdio.h> #include<stdlib.h> #include<string.h> intmain() { char* s1 = "http://c.biancheng.net/cpp/u/biaozhunku/"; char* s2 = "c is good"; int n = strcspn(s1,s2); printf("The first char both in s1 and s2 is :%c\n",s1[n]); printf("The position in s1 is: %d\n",n); system("pause"); return0; }
int *p;:首先从P处开始,先与*结合,所以说明P是一个指针,然后再与int 结合,说明指针所指向的内容的类型为int 型.所以P是一个返回整型数据的指针
int p[3];:首先从P处开始,先与[]结合,说明P是一个数组,然后与int 结合,说明数组里的元素是整型的,所以P是一个由整型数据组成的数组
int *p[3];:首先从P处开始,先与[]结合,因为其优先级比*高,所以P是一个数组,然后再与*结合,说明数组里的元素是指针类型,然后再与int 结合,说明指针所指向的内容的类型是整型的,所以P是一个由返回整型数据的指针所组成的数组
int (*p)[3];:首先从P处开始,先与*结合,说明P是一个指针,然后再与[]结合(与”()”这步可以忽略,只是为了改变优先级),说明指针所指向的内容是一个数组,然后再与int 结合,说明数组里的元素是整型的.所以P是一个指向由整型数据组成的数组的指针
int **p;:首先从P开始,先与*结合,说是P是一个指针,然后再与*结合,说明指针所指向的元素是指针,然后再与int 结合,说明该指针所指向的元素是整型数据.由于二级指针以及更高级的指针极少用在复杂的类型中,所以后面更复杂的类型我们就不考虑多级指针了,最多只考虑一级指针
int p(int);:从P处起,先与()结合,说明P是一个函数,然后进入()里分析,说明该函数有一个整型变量的参数,然后再与外面的int 结合,说明函数的返回值是一个整型数据
int (*p)(int);:从P处开始,先与指针结合,说明P是一个指针,然后与()结合,说明指针指向的是一个函数,然后再与()里的int 结合,说明函数有一个int 型的参数,再与最外层的int 结合,说明函数的返回类型是整型,所以P是一个指向有一个整型参数且返回类型为整型的函数的指针
int *(*p(int))[3];:可以先跳过,不看这个类型,过于复杂从P开始,先与()结合,说明P是一个函数,然后进入()里面,与int 结合,说明函数有一个整型变量参数,然后再与外面的*结合,说明函数返回的是一个指针,,然后到最外面一层,先与[]结合,说明返回的指针指向的是一个数组,然后再与*结合,说明数组里的元素是指针,然后再与int 结合,说明指针指向的内容是整型数据.所以P是一个参数为一个整数据且返回一个指向由整型指针变量组成的数组的指针变量的函数.
...... # system call handler stub ENTRY(system_call) RING0_INT_FRAME # can't unwind into user space anyway pushl %eax # save orig_eax CFI_ADJUST_CFA_OFFSET 4 SAVE_ALL GET_THREAD_INFO(%ebp) # system call tracing in operation / emulation testl $_TIF_WORK_SYSCALL_ENTRY,TI_flags(%ebp) jnz syscall_trace_entry cmpl $(nr_syscalls), %eax jae syscall_badsys syscall_call: call *sys_call_table(,%eax,4) //此处执行相应的系统调用 movl %eax,PT_EAX(%esp) # store the return value syscall_exit: LOCKDEP_SYS_EXIT DISABLE_INTERRUPTS(CLBR_ANY) # make sure we don't miss an interrupt # setting need_resched or sigpending # between sampling and the iret TRACE_IRQS_OFF movl TI_flags(%ebp), %ecx testl $_TIF_ALLWORK_MASK, %ecx # current->work jne syscall_exit_work ......
/** * sys_getpid - return the thread group id of the current process * * Note, despite the name, this returns the tgid not the pid. The tgid and * the pid are identical unless CLONE_THREAD was specified on clone() in * which case the tgid is the same in all threads of the same group. * * This is SMP safe as current->tgid does not change. */ SYSCALL_DEFINE0(getpid) { return task_tgid_vnr(current); }
staticinlineint __must_check request_irq(unsignedint irq, irq_handler_t handler, unsignedlong flags, constchar *name, void *dev) { return request_threaded_irq(irq, handler, NULL, flags, name, dev); } intrequest_threaded_irq(unsignedint irq, irq_handler_t handler, irq_handler_t thread_fn, unsignedlong irqflags, constchar *devname, void *dev_id) { structirqaction *action; structirq_desc *desc; int retval; /* * handle_IRQ_event() always ignores IRQF_DISABLED except for * the _first_ irqaction (sigh). That can cause oopsing, but * the behavior is classified as "will not fix" so we need to * start nudging drivers away from using that idiom. */ if ((irqflags & (IRQF_SHARED|IRQF_DISABLED)) == (IRQF_SHARED|IRQF_DISABLED)) { pr_warning("IRQ %d/%s: IRQF_DISABLED is not guaranteed on shared IRQs\n", irq, devname); } #ifdef CONFIG_LOCKDEP /* * Lockdep wants atomic interrupt handlers: */ irqflags |= IRQF_DISABLED; #endif /* * Sanity-check: shared interrupts must pass in a real dev-ID, * otherwise we'll have trouble later trying to figure out * which interrupt is which (messes up the interrupt freeing * logic etc). */ if ((irqflags & IRQF_SHARED) && !dev_id) return -EINVAL; desc = irq_to_desc(irq); if (!desc) return -EINVAL; if (desc->status & IRQ_NOREQUEST) return -EINVAL; if (!handler) { if (!thread_fn) return -EINVAL; handler = irq_default_primary_handler; } //分配一个irqaction action = kzalloc(sizeof(struct irqaction), GFP_KERNEL); if (!action) return -ENOMEM; action->handler = handler; action->thread_fn = thread_fn; action->flags = irqflags; action->name = devname; action->dev_id = dev_id; chip_bus_lock(irq, desc); //将创建并初始化完在的action加入desc retval = __setup_irq(irq, desc, action); chip_bus_sync_unlock(irq, desc); if (retval) kfree(action); #ifdef CONFIG_DEBUG_SHIRQ if (irqflags & IRQF_SHARED) { /* * It's a shared IRQ -- the driver ought to be prepared for it * to happen immediately, so let's make sure.... * We disable the irq to make sure that a 'real' IRQ doesn't * run in parallel with our fake. */ unsignedlong flags; disable_irq(irq); local_irq_save(flags); handler(irq, dev_id); local_irq_restore(flags); enable_irq(irq); } #endif return retval; }
/* * A very tiny interrupt handler. It runs with IRQF_DISABLED set, * but there is possibility of conflicting with the set_rtc_mmss() * call (the rtc irq and the timer irq can easily run at the same * time in two different CPUs). So we need to serialize * accesses to the chip with the rtc_lock spinlock that each * architecture should implement in the timer code. * (See ./arch/XXXX/kernel/time.c for the set_rtc_mmss() function.) */ staticirqreturn_trtc_interrupt(int irq, void *dev_id) { /* * Can be an alarm interrupt, update complete interrupt, * or a periodic interrupt. We store the status in the * low byte and the number of interrupts received since * the last read in the remainder of rtc_irq_data. */ spin_lock(&rtc_lock); //保证`rtc_irq_data`不被`SMP`机器上其他处理器同时访问 rtc_irq_data += 0x100; rtc_irq_data &= ~0xff; if (is_hpet_enabled()) { /* * In this case it is HPET RTC interrupt handler * calling us, with the interrupt information * passed as arg1, instead of irq. */ rtc_irq_data |= (unsignedlong)irq & 0xF0; } else { rtc_irq_data |= (CMOS_READ(RTC_INTR_FLAGS) & 0xF0); } if (rtc_status & RTC_TIMER_ON) mod_timer(&rtc_irq_timer, jiffies + HZ/rtc_freq + 2*HZ/100); spin_unlock(&rtc_lock); /* Now do the rest of the actions */ spin_lock(&rtc_task_lock); //避免`rtc_callback`出现系统情况,RTC`驱动允许注册一个回调函数在每个`RTC`中断到来时执行。 if (rtc_callback) rtc_callback->func(rtc_callback->private_data); spin_unlock(&rtc_task_lock); wake_up_interruptible(&rtc_wait); kill_fasync(&rtc_async_queue, SIGIO, POLL_IN); return IRQ_HANDLED; }
/** * handle_IRQ_event - irq action chain handler * @irq: the interrupt number * @action: the interrupt action chain for this irq * * Handles the action chain of an irq event */ irqreturn_thandle_IRQ_event(unsignedint irq, struct irqaction *action) { irqreturn_t ret, retval = IRQ_NONE; unsignedint status = 0; //如果没有设置`IRQF_DISABLED,将CPU中断打开,应该尽量避免中断关闭情况,本地中断关闭情况下会导致中断丢失。 if (!(action->flags & IRQF_DISABLED)) local_irq_enable_in_hardirq(); do { //遍历运行中断处理程序 trace_irq_handler_entry(irq, action); ret = action->handler(irq, action->dev_id); trace_irq_handler_exit(irq, action, ret); switch (ret) { case IRQ_WAKE_THREAD: /* * Set result to handled so the spurious check * does not trigger. */ ret = IRQ_HANDLED; /* * Catch drivers which return WAKE_THREAD but * did not set up a thread function */ if (unlikely(!action->thread_fn)) { warn_no_thread(irq, action); break; } /* * Wake up the handler thread for this * action. In case the thread crashed and was * killed we just pretend that we handled the * interrupt. The hardirq handler above has * disabled the device interrupt, so no irq * storm is lurking. */ if (likely(!test_bit(IRQTF_DIED, &action->thread_flags))) { set_bit(IRQTF_RUNTHREAD, &action->thread_flags); wake_up_process(action->thread); } /* Fall through to add to randomness */ case IRQ_HANDLED: status |= action->flags; break; default: break; } retval |= ret; action = action->next; } while (action); if (status & IRQF_SAMPLE_RANDOM) add_interrupt_randomness(irq); local_irq_disable();//关中断 return retval; }
/* PLEASE, avoid to allocate new softirqs, if you need not _really_ high frequency threaded job scheduling. For almost all the purposes tasklets are more than enough. F.e. all serial device BHs et al. should be converted to tasklets, not to softirqs. */ enum { HI_SOFTIRQ=0, TIMER_SOFTIRQ, NET_TX_SOFTIRQ, NET_RX_SOFTIRQ, BLOCK_SOFTIRQ, BLOCK_IOPOLL_SOFTIRQ, TASKLET_SOFTIRQ, SCHED_SOFTIRQ, HRTIMER_SOFTIRQ, RCU_SOFTIRQ, /* Preferable RCU should always be the last softirq */ NR_SOFTIRQS };
第二步,编写tasklet处理程序。tasklet处理函数类型是void tasklet_handler(unsigned long data)。因为是靠软中断实现,所以tasklet不能休眠,也就是说不能在tasklet中使用信号量或者其他什么阻塞式的函数。由于tasklet运行时允许响应中断,所以必须做好预防工作,如果新加入的tasklet和中断处理程序之间共享了某些数据额的话。两个相同的tasklet绝不能同时执行,如果新加入的tasklet和其他的tasklet或者软中断共享了数据,就必须要进行适当地锁保护。
staticirqreturn_ttimer_interrupt(int irq, void *dev_id) { /* Keep nmi watchdog up to date */ inc_irq_stat(irq0_irqs); /* Optimized out for !IO_APIC and x86_64 */ if (timer_ack) { /* * Subtle, when I/O APICs are used we have to ack timer IRQ * manually to deassert NMI lines for the watchdog if run * on an 82489DX-based system. */ spin_lock(&i8259A_lock); outb(0x0c, PIC_MASTER_OCW3); /* Ack the IRQ; AEOI will end it automatically. */ inb(PIC_MASTER_POLL); spin_unlock(&i8259A_lock); } //在此处调用体系无关的时钟处理例程 global_clock_event->event_handler(global_clock_event); /* MCA bus quirk: Acknowledge irq0 by setting bit 7 in port 0x61 */ if (MCA_bus) outb_p(inb_p(0x61)| 0x80, 0x61); return IRQ_HANDLED; }
voidupdate_process_times(int user_tick) { structtask_struct *p = current; int cpu = smp_processor_id(); /* Note: this timer irq context must be accounted for as well. */ account_process_tick(p, user_tick); run_local_timers(); rcu_check_callbacks(cpu, user_tick); printk_tick(); scheduler_tick(); run_posix_cpu_timers(p); }
signedlong __sched schedule_timeout(signedlong timeout) { structtimer_listtimer; unsignedlong expire; switch (timeout) { case MAX_SCHEDULE_TIMEOUT: /* * These two special cases are useful to be comfortable * in the caller. Nothing more. We could take * MAX_SCHEDULE_TIMEOUT from one of the negative value * but I' d like to return a valid offset (>=0) to allow * the caller to do everything it want with the retval. */ schedule(); goto out; default: /* * Another bit of PARANOID. Note that the retval will be * 0 since no piece of kernel is supposed to do a check * for a negative retval of schedule_timeout() (since it * should never happens anyway). You just have the printk() * that will tell you if something is gone wrong and where. */ if (timeout < 0) { printk(KERN_ERR "schedule_timeout: wrong timeout " "value %lx\n", timeout); dump_stack(); current->state = TASK_RUNNING; goto out; } } expire = timeout + jiffies; //下一行代码设置了超时执行函数`process_timeout()。 setup_timer_on_stack(&timer, process_timeout, (unsignedlong)current); __mod_timer(&timer, expire, false, TIMER_NOT_PINNED); //激活定时器 schedule(); //调度其他新任务 del_singleshot_timer_sync(&timer); /* Remove the timer from the object tracker */ destroy_timer_on_stack(&timer); timeout = expire - jiffies; out: return timeout < 0 ? 0 : timeout; } 当定时器超时时,process_timeout()函数被调用: staticvoidprocess_timeout(unsignedlong __data) { wake_up_process((struct task_struct *)__data); }
进程其实就是程序的执行时的实例,是处于执行期的程序。在Linux内核中,进程列表被存放在一个双向循环链表中,链表中每一项都是类型为task_struct的结构,该结构称作进程描述符,进程描述符包含一个具体进程的所有信息,这个结构就是我们在操作系统中所说的PCB(Process Control Block)。该结构定义于<include/linux/sched.h>文件中:
structtask_struct { volatilelong state; /* -1 unrunnable, 0 runnable, >0 stopped */ void *stack; atomic_t usage; unsignedint flags; /* per process flags, defined below */ unsignedint ptrace; int lock_depth; /* BKL lock depth */ ...... int prio, static_prio, normal_prio; unsignedint rt_priority; conststructsched_class *sched_class; structsched_entityse; structsched_rt_entityrt; ...... structtask_struct *parent;/* recipient of SIGCHLD, wait4() reports */ structlist_headchildren;/* list of my children */ structlist_headsibling;/* linkage in my parent's children list */ ...... };
intsys_fork(struct pt_regs *regs) { returndo_fork(SIGCHLD, regs->sp, regs, 0, NULL, NULL); } longdo_fork(unsignedlong clone_flags, unsignedlong stack_start, struct pt_regs *regs, unsignedlong stack_size, int __user *parent_tidptr, int __user *child_tidptr) { structtask_struct *p; int trace = 0; long nr; ...... p = copy_process(clone_flags, stack_start, regs, stack_size, child_tidptr, NULL, trace); ...... return nr; } staticstructtask_struct *copy_process(unsignedlong clone_flags, unsignedlong stack_start, struct pt_regs *regs, unsignedlong stack_size, int __user *child_tidptr, struct pid *pid, int trace) { int retval; structtask_struct *p; int cgroup_callbacks_done = 0; if ((clone_flags & (CLONE_NEWNS|CLONE_FS)) == (CLONE_NEWNS|CLONE_FS)) returnERR_PTR(-EINVAL); /* * Thread groups must share signals as well, and detached threads * can only be started up within the thread group. */ if ((clone_flags & CLONE_THREAD) && !(clone_flags & CLONE_SIGHAND)) returnERR_PTR(-EINVAL); /* * Shared signal handlers imply shared VM. By way of the above, * thread groups also imply shared VM. Blocking this case allows * for various simplifications in other code. */ if ((clone_flags & CLONE_SIGHAND) && !(clone_flags & CLONE_VM)) returnERR_PTR(-EINVAL); /* * Siblings of global init remain as zombies on exit since they are * not reaped by their parent (swapper). To solve this and to avoid * multi-rooted process trees, prevent global and container-inits * from creating siblings. */ if ((clone_flags & CLONE_PARENT) && current->signal->flags & SIGNAL_UNKILLABLE) returnERR_PTR(-EINVAL); retval = security_task_create(clone_flags); if (retval) goto fork_out; retval = -ENOMEM; p = dup_task_struct(current); if (!p) goto fork_out; ftrace_graph_init_task(p); rt_mutex_init_task(p); #ifdef CONFIG_PROVE_LOCKING DEBUG_LOCKS_WARN_ON(!p->hardirqs_enabled); DEBUG_LOCKS_WARN_ON(!p->softirqs_enabled); #endif retval = -EAGAIN; if (atomic_read(&p->real_cred->user->processes) >= p->signal->rlim[RLIMIT_NPROC].rlim_cur) { if (!capable(CAP_SYS_ADMIN) && !capable(CAP_SYS_RESOURCE) && p->real_cred->user != INIT_USER) goto bad_fork_free; } retval = copy_creds(p, clone_flags); if (retval < 0) goto bad_fork_free; /* * If multiple threads are within copy_process(), then this check * triggers too late. This doesn't hurt, the check is only there * to stop root fork bombs. */ retval = -EAGAIN; if (nr_threads >= max_threads) goto bad_fork_cleanup_count; if (!try_module_get(task_thread_info(p)->exec_domain->module)) goto bad_fork_cleanup_count; p->did_exec = 0; delayacct_tsk_init(p); /* Must remain after dup_task_struct() */ copy_flags(clone_flags, p); INIT_LIST_HEAD(&p->children); INIT_LIST_HEAD(&p->sibling); rcu_copy_process(p); p->vfork_done = NULL; spin_lock_init(&p->alloc_lock); init_sigpending(&p->pending); p->utime = cputime_zero; p->stime = cputime_zero; p->gtime = cputime_zero; p->utimescaled = cputime_zero; p->stimescaled = cputime_zero; p->prev_utime = cputime_zero; p->prev_stime = cputime_zero; p->default_timer_slack_ns = current->timer_slack_ns; task_io_accounting_init(&p->ioac); acct_clear_integrals(p); posix_cpu_timers_init(p); p->lock_depth = -1; /* -1 = no lock */ do_posix_clock_monotonic_gettime(&p->start_time); p->real_start_time = p->start_time; monotonic_to_bootbased(&p->real_start_time); p->io_context = NULL; p->audit_context = NULL; cgroup_fork(p); #ifdef CONFIG_NUMA p->mempolicy = mpol_dup(p->mempolicy); if (IS_ERR(p->mempolicy)) { retval = PTR_ERR(p->mempolicy); p->mempolicy = NULL; goto bad_fork_cleanup_cgroup; } mpol_fix_fork_child_flag(p); #endif #ifdef CONFIG_TRACE_IRQFLAGS p->irq_events = 0; #ifdef __ARCH_WANT_INTERRUPTS_ON_CTXSW p->hardirqs_enabled = 1; #else p->hardirqs_enabled = 0; #endif p->hardirq_enable_ip = 0; p->hardirq_enable_event = 0; p->hardirq_disable_ip = _THIS_IP_; p->hardirq_disable_event = 0; p->softirqs_enabled = 1; p->softirq_enable_ip = _THIS_IP_; p->softirq_enable_event = 0; p->softirq_disable_ip = 0; p->softirq_disable_event = 0; p->hardirq_context = 0; p->softirq_context = 0; #endif #ifdef CONFIG_LOCKDEP p->lockdep_depth = 0; /* no locks held yet */ p->curr_chain_key = 0; p->lockdep_recursion = 0; #endif #ifdef CONFIG_DEBUG_MUTEXES p->blocked_on = NULL; /* not blocked yet */ #endif p->bts = NULL; p->stack_start = stack_start; /* Perform scheduler related setup. Assign this task to a CPU. */ sched_fork(p, clone_flags); retval = perf_event_init_task(p); if (retval) goto bad_fork_cleanup_policy; if ((retval = audit_alloc(p))) goto bad_fork_cleanup_policy; /* copy all the process information */ if ((retval = copy_semundo(clone_flags, p))) goto bad_fork_cleanup_audit; if ((retval = copy_files(clone_flags, p))) goto bad_fork_cleanup_semundo; if ((retval = copy_fs(clone_flags, p))) goto bad_fork_cleanup_files; if ((retval = copy_sighand(clone_flags, p))) goto bad_fork_cleanup_fs; if ((retval = copy_signal(clone_flags, p))) goto bad_fork_cleanup_sighand; if ((retval = copy_mm(clone_flags, p))) goto bad_fork_cleanup_signal; if ((retval = copy_namespaces(clone_flags, p))) goto bad_fork_cleanup_mm; if ((retval = copy_io(clone_flags, p))) goto bad_fork_cleanup_namespaces; retval = copy_thread(clone_flags, stack_start, stack_size, p, regs); if (retval) goto bad_fork_cleanup_io; if (pid != &init_struct_pid) { retval = -ENOMEM; pid = alloc_pid(p->nsproxy->pid_ns); if (!pid) goto bad_fork_cleanup_io; if (clone_flags & CLONE_NEWPID) { retval = pid_ns_prepare_proc(p->nsproxy->pid_ns); if (retval < 0) goto bad_fork_free_pid; } } p->pid = pid_nr(pid); p->tgid = p->pid; if (clone_flags & CLONE_THREAD) p->tgid = current->tgid; if (current->nsproxy != p->nsproxy) { retval = ns_cgroup_clone(p, pid); if (retval) goto bad_fork_free_pid; } p->set_child_tid = (clone_flags & CLONE_CHILD_SETTID) ? child_tidptr : NULL; /* * Clear TID on mm_release()? */ p->clear_child_tid = (clone_flags & CLONE_CHILD_CLEARTID) ? child_tidptr: NULL; #ifdef CONFIG_FUTEX p->robust_list = NULL; #ifdef CONFIG_COMPAT p->compat_robust_list = NULL; #endif INIT_LIST_HEAD(&p->pi_state_list); p->pi_state_cache = NULL; #endif /* * sigaltstack should be cleared when sharing the same VM */ if ((clone_flags & (CLONE_VM|CLONE_VFORK)) == CLONE_VM) p->sas_ss_sp = p->sas_ss_size = 0; /* * Syscall tracing should be turned off in the child regardless * of CLONE_PTRACE. */ clear_tsk_thread_flag(p, TIF_SYSCALL_TRACE); #ifdef TIF_SYSCALL_EMU clear_tsk_thread_flag(p, TIF_SYSCALL_EMU); #endif clear_all_latency_tracing(p); /* ok, now we should be set up.. */ p->exit_signal = (clone_flags & CLONE_THREAD) ? -1 : (clone_flags & CSIGNAL); p->pdeath_signal = 0; p->exit_state = 0; /* * Ok, make it visible to the rest of the system. * We dont wake it up yet. */ p->group_leader = p; INIT_LIST_HEAD(&p->thread_group); /* Now that the task is set up, run cgroup callbacks if * necessary. We need to run them before the task is visible * on the tasklist. */ cgroup_fork_callbacks(p); cgroup_callbacks_done = 1; /* Need tasklist lock for parent etc handling! */ write_lock_irq(&tasklist_lock); /* * The task hasn't been attached yet, so its cpus_allowed mask will * not be changed, nor will its assigned CPU. * * The cpus_allowed mask of the parent may have changed after it was * copied first time - so re-copy it here, then check the child's CPU * to ensure it is on a valid CPU (and if not, just force it back to * parent's CPU). This avoids alot of nasty races. */ p->cpus_allowed = current->cpus_allowed; p->rt.nr_cpus_allowed = current->rt.nr_cpus_allowed; if (unlikely(!cpu_isset(task_cpu(p), p->cpus_allowed) || !cpu_online(task_cpu(p)))) set_task_cpu(p, smp_processor_id()); /* CLONE_PARENT re-uses the old parent */ if (clone_flags & (CLONE_PARENT|CLONE_THREAD)) { p->real_parent = current->real_parent; p->parent_exec_id = current->parent_exec_id; } else { p->real_parent = current; p->parent_exec_id = current->self_exec_id; } spin_lock(¤t->sighand->siglock); /* * Process group and session signals need to be delivered to just the * parent before the fork or both the parent and the child after the * fork. Restart if a signal comes in before we add the new process to * it's process group. * A fatal signal pending means that current will exit, so the new * thread can't slip out of an OOM kill (or normal SIGKILL). */ recalc_sigpending(); if (signal_pending(current)) { spin_unlock(¤t->sighand->siglock); write_unlock_irq(&tasklist_lock); retval = -ERESTARTNOINTR; goto bad_fork_free_pid; } if (clone_flags & CLONE_THREAD) { atomic_inc(¤t->signal->count); atomic_inc(¤t->signal->live); p->group_leader = current->group_leader; list_add_tail_rcu(&p->thread_group, &p->group_leader->thread_group); } if (likely(p->pid)) { list_add_tail(&p->sibling, &p->real_parent->children); tracehook_finish_clone(p, clone_flags, trace); if (thread_group_leader(p)) { if (clone_flags & CLONE_NEWPID) p->nsproxy->pid_ns->child_reaper = p; p->signal->leader_pid = pid; tty_kref_put(p->signal->tty); p->signal->tty = tty_kref_get(current->signal->tty); attach_pid(p, PIDTYPE_PGID, task_pgrp(current)); attach_pid(p, PIDTYPE_SID, task_session(current)); list_add_tail_rcu(&p->tasks, &init_task.tasks); __get_cpu_var(process_counts)++; } attach_pid(p, PIDTYPE_PID, pid); nr_threads++; } total_forks++; spin_unlock(¤t->sighand->siglock); write_unlock_irq(&tasklist_lock); proc_fork_connector(p); cgroup_post_fork(p); perf_event_fork(p); return p; bad_fork_free_pid: if (pid != &init_struct_pid) free_pid(pid); bad_fork_cleanup_io: put_io_context(p->io_context); bad_fork_cleanup_namespaces: exit_task_namespaces(p); bad_fork_cleanup_mm: if (p->mm) mmput(p->mm); bad_fork_cleanup_signal: if (!(clone_flags & CLONE_THREAD)) __cleanup_signal(p->signal); bad_fork_cleanup_sighand: __cleanup_sighand(p->sighand); bad_fork_cleanup_fs: exit_fs(p); /* blocking */ bad_fork_cleanup_files: exit_files(p); /* blocking */ bad_fork_cleanup_semundo: exit_sem(p); bad_fork_cleanup_audit: audit_free(p); bad_fork_cleanup_policy: perf_event_free_task(p); #ifdef CONFIG_NUMA mpol_put(p->mempolicy); bad_fork_cleanup_cgroup: #endif cgroup_exit(p, cgroup_callbacks_done); delayacct_tsk_free(p); module_put(task_thread_info(p)->exec_domain->module); bad_fork_cleanup_count: atomic_dec(&p->cred->user->processes); exit_creds(p); bad_fork_free: free_task(p); fork_out: returnERR_PTR(retval); }
NORET_TYPE voiddo_exit(long code) { structtask_struct *tsk = current; int group_dead; profile_task_exit(tsk); WARN_ON(atomic_read(&tsk->fs_excl)); //不可在中断上下文中使用该函数 if (unlikely(in_interrupt())) panic("Aiee, killing interrupt handler!"); if (unlikely(!tsk->pid)) panic("Attempted to kill the idle task!"); tracehook_report_exit(&code); validate_creds_for_do_exit(tsk); /* * We're taking recursive faults here in do_exit. Safest is to just * leave this task alone and wait for reboot. */ if (unlikely(tsk->flags & PF_EXITING)) { printk(KERN_ALERT "Fixing recursive fault but reboot is needed!\n"); //设置PF_EXITING:表示进程正在退出 tsk->flags |= PF_EXITPIDONE; set_current_state(TASK_UNINTERRUPTIBLE); schedule(); } exit_irq_thread(); exit_signals(tsk); /* sets PF_EXITING */ /* * tsk->flags are checked in the futex code to protect against * an exiting task cleaning up the robust pi futexes. */ smp_mb(); spin_unlock_wait(&tsk->pi_lock); if (unlikely(in_atomic())) printk(KERN_INFO "note: %s[%d] exited with preempt_count %d\n", current->comm, task_pid_nr(current), preempt_count()); acct_update_integrals(tsk); group_dead = atomic_dec_and_test(&tsk->signal->live); if (group_dead) { hrtimer_cancel(&tsk->signal->real_timer); exit_itimers(tsk->signal); if (tsk->mm) setmax_mm_hiwater_rss(&tsk->signal->maxrss, tsk->mm); } acct_collect(code, group_dead); if (group_dead) tty_audit_exit(); if (unlikely(tsk->audit_context)) audit_free(tsk); tsk->exit_code = code; taskstats_exit(tsk, group_dead); //调用__exit_mm()函数放弃进程占用的mm_struct,如果没有别的进程使用它们即没被共享,就彻底释放它们 exit_mm(tsk); if (group_dead) acct_process(); trace_sched_process_exit(tsk); exit_sem(tsk); //调用sem_exit()函数。如果进程排队等候IPC信号,它则离开队列 //分别递减文件描述符,文件系统数据等的引用计数。当引用计数的值为0时,就代表没有进程在使用这些资源,此时就释放 exit_files(tsk); exit_fs(tsk); check_stack_usage(); exit_thread(); cgroup_exit(tsk, 1); if (group_dead && tsk->signal->leader) disassociate_ctty(1); module_put(task_thread_info(tsk)->exec_domain->module); proc_exit_connector(tsk); /* * Flush inherited counters to the parent - before the parent * gets woken up by child-exit notifications. */ perf_event_exit_task(tsk); //调用exit_notify()向父进程发送信号,将子进程的父进程重新设置为线程组中的其他线程或init进程,并把进程状态设为TASK_ZOMBIE. exit_notify(tsk, group_dead); #ifdef CONFIG_NUMA mpol_put(tsk->mempolicy); tsk->mempolicy = NULL; #endif #ifdef CONFIG_FUTEX if (unlikely(current->pi_state_cache)) kfree(current->pi_state_cache); #endif /* * Make sure we are holding no locks: */ debug_check_no_locks_held(tsk); /* * We can do this unlocked here. The futex code uses this flag * just to verify whether the pi state cleanup has been done * or not. In the worst case it loops once more. */ tsk->flags |= PF_EXITPIDONE; if (tsk->io_context) exit_io_context(); if (tsk->splice_pipe) __free_pipe_info(tsk->splice_pipe); validate_creds_for_do_exit(tsk); preempt_disable(); exit_rcu(); /* causes final put_task_struct in finish_task_switch(). */ tsk->state = TASK_DEAD; schedule(); //调用`schedule()切换到其他进程 BUG(); /* Avoid "noreturn function does return". */ for (;;) cpu_relax(); /* For when BUG is null */ }
voidrelease_task(struct task_struct * p) { structtask_struct *leader; int zap_leader; repeat: tracehook_prepare_release_task(p); /* don't need to get the RCU readlock here - the process is dead and * can't be modifying its own credentials */ atomic_dec(&__task_cred(p)->user->processes); proc_flush_task(p); write_lock_irq(&tasklist_lock); tracehook_finish_release_task(p); __exit_signal(p); //释放目前僵死进程所使用的所有剩余资源,并进行统计记录 zap_leader = 0; leader = p->group_leader; //如果进程是线程组最后一个进程,并且领头进程已经死掉,那么就通知僵死的领头进程的父进程 if (leader != p && thread_group_empty(leader) && leader->exit_state == EXIT_ZOMBIE) { BUG_ON(task_detached(leader)); do_notify_parent(leader, leader->exit_signal); zap_leader = task_detached(leader); if (zap_leader) leader->exit_state = EXIT_DEAD; } write_unlock_irq(&tasklist_lock); release_thread(p); call_rcu(&p->rcu, delayed_put_task_struct); p = leader; if (unlikely(zap_leader)) goto repeat; }
asmlinkage void __sched schedule(void) { structtask_struct *prev, *next; unsignedlong *switch_count; structrq *rq; int cpu; need_resched: preempt_disable(); cpu = smp_processor_id(); rq = cpu_rq(cpu); rcu_sched_qs(cpu); prev = rq->curr; switch_count = &prev->nivcsw; release_kernel_lock(prev); need_resched_nonpreemptible: schedule_debug(prev); if (sched_feat(HRTICK)) hrtick_clear(rq); spin_lock_irq(&rq->lock); update_rq_clock(rq); clear_tsk_need_resched(prev); if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) { if (unlikely(signal_pending_state(prev->state, prev))) prev->state = TASK_RUNNING; else deactivate_task(rq, prev, 1); switch_count = &prev->nvcsw; } pre_schedule(rq, prev); if (unlikely(!rq->nr_running)) idle_balance(cpu, rq); put_prev_task(rq, prev); <strong>next = pick_next_task(rq); //<span><span><span style="font-size:14px;">//挑选最高优先级别的任务</span></span></span></strong> if (likely(prev != next)) { sched_info_switch(prev, next); perf_event_task_sched_out(prev, next, cpu); rq->nr_switches++; rq->curr = next; ++*switch_count; context_switch(rq, prev, next); /* unlocks the rq */ /* * the context switch might have flipped the stack from under * us, hence refresh the local variables. */ cpu = smp_processor_id(); rq = cpu_rq(cpu); } else spin_unlock_irq(&rq->lock); post_schedule(rq); if (unlikely(reacquire_kernel_lock(current) < 0)) goto need_resched_nonpreemptible; preempt_enable_no_resched(); if (need_resched()) goto need_resched; }
staticinlinestruct task_struct * pick_next_task(struct rq *rq) { conststructsched_class *class; structtask_struct *p; /* * Optimization: we know that if all tasks are in * the fair class we can call that function directly: */ if (likely(rq->nr_running == rq->cfs.nr_running)) { p = fair_sched_class.pick_next_task(rq); if (likely(p)) return p; } //从最高优先级类开始,遍历每一个调度类。每一个调度类都实现了pick_next_task,他会返回指向下一个可运行进程的指针,没有时返回NULL。 class = sched_class_highest; for ( ; ; ) { p = class->pick_next_task(rq); if (p) return p; /* * Will never be NULL as the idle class always * returns a non-NULL p: */ class =class->next; } }
void __sched mutex_lock(struct mutex *lock) { might_sleep(); /* * The locking fastpath is the 1->0 transition from * 'unlocked' into 'locked' state. */ __mutex_fastpath_lock(&lock->count, __mutex_lock_slowpath); mutex_set_owner(lock); } void __sched mutex_unlock(struct mutex *lock) { /* * The unlocking fastpath is the 0->1 transition from 'locked' * into 'unlocked' state: */ #ifndef CONFIG_DEBUG_MUTEXES /* * When debugging is enabled we must not clear the owner before time, * the slow path will always be taken, and that clears the owner field * after verifying that it was indeed current. */ mutex_clear_owner(lock); #endif __mutex_fastpath_unlock(&lock->count, __mutex_unlock_slowpath); }
#define preempt_enable() \ do { \ preempt_enable_no_resched(); \ barrier(); \ preempt_check_resched(); \ } while (0)
#define preempt_enable_no_resched() \ do { \ barrier(); \ dec_preempt_count(); \ } while (0)
#define dec_preempt_count() sub_preempt_count(1)
#define sub_preempt_count(val) do { preempt_count() -= (val); } while (0) #define preempt_check_resched() \ do { \ if (unlikely(test_thread_flag(TIF_NEED_RESCHED))) \ preempt_schedule(); \ } while (0)
asmlinkage void __sched preempt_schedule(void) { structthread_info *ti = current_thread_info(); /* * If there is a non-zero preempt_count or interrupts are disabled, * we do not want to preempt the current task. Just return.. */ if (likely(ti->preempt_count || irqs_disabled())) return; do { add_preempt_count(PREEMPT_ACTIVE); schedule(); sub_preempt_count(PREEMPT_ACTIVE); /* * Check again in case we missed a preemption opportunity * between schedule and now. */ barrier(); } while (need_resched());
内存管理之页的分配与回收
内存管理单元(MMU)负责将管理内存,在把虚拟地址转换为物理地址的硬件的时候是按页为单位进行处理,从虚拟内存的角度来看,页就是内存管理中的最小单位。页的大小与体系结构有关,在 x86 结构中一般是4KB(32位)或者8KB(64位)。 通过 getconf 命令可以查看系统的page的大小:
structkmem_cache { /* 1) per-cpu data, touched during every alloc/free */ structarray_cache *array[NR_CPUS]; /* 2) Cache tunables. Protected by cache_chain_mutex */ unsignedint batchcount; unsignedint limit; unsignedint shared; unsignedint buffer_size; u32 reciprocal_buffer_size; /* 3) touched by every alloc & free from the backend */ unsignedint flags; /* constant flags */ unsignedint num; /* # of objs per slab */ /* 4) cache_grow/shrink */ /* order of pgs per slab (2^n) */ unsignedint gfporder; /* force GFP flags, e.g. GFP_DMA */ gfp_t gfpflags; size_t colour; /* cache colouring range */ unsignedint colour_off; /* colour offset */ structkmem_cache *slabp_cache; unsignedint slab_size; unsignedint dflags; /* dynamic flags */ /* constructor func */ void (*ctor)(void *obj); /* 5) cache creation/removal */ constchar *name; structlist_headnext; /* 6) statistics */ #ifdef CONFIG_DEBUG_SLAB unsignedlong num_active; unsignedlong num_allocations; unsignedlong high_mark; unsignedlong grown; unsignedlong reaped; unsignedlong errors; unsignedlong max_freeable; unsignedlong node_allocs; unsignedlong node_frees; unsignedlong node_overflow; atomic_t allochit; atomic_t allocmiss; atomic_t freehit; atomic_t freemiss; /* * If debugging is enabled, then the allocator can add additional * fields and/or padding to every object. buffer_size contains the total * object size including these internal fields, the following two * variables contain the offset to the user object and its size. */ int obj_offset; int obj_size; #endif/* CONFIG_DEBUG_SLAB */ /* * We put nodelists[] at the end of kmem_cache, because we want to size * this array to nr_node_ids slots instead of MAX_NUMNODES * (see kmem_cache_init()) * We still use [MAX_NUMNODES] and not [1] or [0] because cache_cache * is statically defined, so we reserve the max number of nodes. */ structkmem_list3 *nodelists[MAX_NUMNODES]; /* * Do not add fields after nodelists[] */ };
其中struct kmem_list3结构体链接slab,共享高速缓存,其定义如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
/* * The slab lists for all objects. */ structkmem_list3 { structlist_headslabs_partial;/* partial list first, better asm code */ structlist_headslabs_full; structlist_headslabs_free; unsignedlong free_objects; unsignedint free_limit; unsignedint colour_next; /* Per-node cache coloring */ spinlock_t list_lock; structarray_cache *shared;/* shared per node */ structarray_cache **alien;/* on other nodes */ unsignedlong next_reap; /* updated without locking */ int free_touched; /* updated without locking */ };
/* * struct slab * * Manages the objs in a slab. Placed either at the beginning of mem allocated * for a slab, or allocated from an general cache. * Slabs are chained into three list: fully used, partial, fully free slabs. */ structslab { structlist_headlist; unsignedlong colouroff; void *s_mem; /* including colour offset */ unsignedint inuse; /* num of objs active in slab */ kmem_bufctl_tfree; unsignedshort nodeid; };
/** * kmem_cache_alloc - Allocate an object * @cachep: The cache to allocate from. * @flags: See kmalloc(). * * Allocate an object from this cache. The flags are only relevant * if the cache has no available objects. */ void *kmem_cache_alloc(struct kmem_cache *cachep, gfp_t flags) { void *ret = __cache_alloc(cachep, flags, __builtin_return_address(0)); trace_kmem_cache_alloc(_RET_IP_, ret, obj_size(cachep), cachep->buffer_size, flags); return ret; }
/** * kfree - free previously allocated memory * @objp: pointer returned by kmalloc. * * If @objp is NULL, no operation is performed. * * Don't free memory not originally allocated by kmalloc() * or you will run into trouble. */ voidkfree(constvoid *objp) { structkmem_cache *c; unsignedlong flags; trace_kfree(_RET_IP_, objp); if (unlikely(ZERO_OR_NULL_PTR(objp))) return; local_irq_save(flags); kfree_debugcheck(objp); c = virt_to_cache(objp); debug_check_no_locks_freed(objp, obj_size(c)); debug_check_no_obj_freed(objp, obj_size(c)); __cache_free(c, (void *)objp); local_irq_restore(flags); }
其中堆栈安排在虚拟地址空间顶部,数据段和代码段分布在虚拟地址空间底部,空洞部分就是进程运行时可以动态分布的空间,包括映射内核地址空间内容、动态申请地址空间、共享库的代码或数据等。在虚拟地址空间中,只有那些映射到物理存储空间的地址才是合法的地址空间。每一片合法的地址空间片段都对应一个独立的虚拟内存区域(VMA,virtual memory areas ),而进程的进程地址空间就是由这些内存区域组成。
Linux 采用了复杂的数据结构来跟踪进程的虚拟地址,进程地址空间使用内存描述符结构体来表示,内存描述符由mm_struct结构体表示,该结构体表示在<include/linux/mm_types.h>文件中:
structmm_struct { structvm_area_struct * mmap;/* list of VMAs */ structrb_rootmm_rb; structvm_area_struct * mmap_cache;/* last find_vma result */ unsignedlong(*get_unmapped_area)(struct file *filp, unsignedlong addr, unsignedlong len, unsignedlong pgoff, unsignedlong flags); void (*unmap_area) (struct mm_struct *mm, unsignedlong addr); unsignedlong mmap_base; /* base of mmap area */ unsignedlong task_size; /* size of task vm space */ unsignedlong cached_hole_size; /* if non-zero, the largest hole below free_area_cache */ unsignedlong free_area_cache; /* first hole of size cached_hole_size or larger */ pgd_t * pgd; atomic_t mm_users; /* How many users with user space? */ atomic_t mm_count; /* How many references to "struct mm_struct" (users count as 1) */ int map_count; /* number of VMAs */ structrw_semaphoremmap_sem; spinlock_t page_table_lock; /* Protects page tables and some counters */ structlist_headmmlist;/* List of maybe swapped mm's. These are globally strung together off init_mm.mmlist, and are protected by mmlist_lock */ /* Special counters, in some configurations protected by the * page_table_lock, in other configurations by being atomic. */ mm_counter_t _file_rss; mm_counter_t _anon_rss; unsignedlong hiwater_rss; /* High-watermark of RSS usage */ unsignedlong hiwater_vm; /* High-water virtual memory usage */ unsignedlong total_vm, locked_vm, shared_vm, exec_vm; unsignedlong stack_vm, reserved_vm, def_flags, nr_ptes; unsignedlong start_code, end_code, start_data, end_data; unsignedlong start_brk, brk, start_stack; unsignedlong arg_start, arg_end, env_start, env_end; unsignedlong saved_auxv[AT_VECTOR_SIZE]; /* for /proc/PID/auxv */ structlinux_binfmt *binfmt; cpumask_t cpu_vm_mask; /* Architecture-specific MM context */ mm_context_t context; /* Swap token stuff */ /* * Last value of global fault stamp as seen by this process. * In other words, this value gives an indication of how long * it has been since this task got the token. * Look at mm/thrash.c */ unsignedint faultstamp; unsignedint token_priority; unsignedint last_interval; unsignedlong flags; /* Must use atomic bitops to access the bits */ structcore_state *core_state;/* coredumping support */ #ifdef CONFIG_AIO spinlock_t ioctx_lock; structhlist_headioctx_list; #endif #ifdef CONFIG_MM_OWNER /* * "owner" points to a task that is regarded as the canonical * user/owner of this mm. All of the following must be true in * order for it to be changed: * * current == mm->owner * current->mm != mm * new_owner->mm == mm * new_owner->alloc_lock is held */ structtask_struct *owner; #endif #ifdef CONFIG_PROC_FS /* store ref to file /proc/<pid>/exe symlink points to */ structfile *exe_file; unsignedlong num_exe_file_vmas; #endif #ifdef CONFIG_MMU_NOTIFIER structmmu_notifier_mm *mmu_notifier_mm; #endif };
/* * This struct defines a memory VMM memory area. There is one of these * per VM-area/task. A VM area is any part of the process virtual memory * space that has a special rule for the page-fault handlers (ie a shared * library, the executable area etc). */ structvm_area_struct { structmm_struct * vm_mm;/* The address space we belong to. */ unsignedlong vm_start; /* Our start address within vm_mm. */ unsignedlong vm_end; /* The first byte after our end address within vm_mm. */ /* linked list of VM areas per task, sorted by address */ structvm_area_struct *vm_next; pgprot_t vm_page_prot; /* Access permissions of this VMA. */ unsignedlong vm_flags; /* Flags, see mm.h. */ structrb_nodevm_rb; /* * For areas with an address space and backing store, * linkage into the address_space->i_mmap prio tree, or * linkage to the list of like vmas hanging off its node, or * linkage of vma in the address_space->i_mmap_nonlinear list. */ union { struct { structlist_headlist; void *parent; /* aligns with prio_tree_node parent */ structvm_area_struct *head; } vm_set; structraw_prio_tree_nodeprio_tree_node; } shared; /* * A file's MAP_PRIVATE vma can be in both i_mmap tree and anon_vma * list, after a COW of one of the file pages. A MAP_SHARED vma * can only be in the i_mmap tree. An anonymous MAP_PRIVATE, stack * or brk vma (with NULL file) can only be in an anon_vma list. */ structlist_headanon_vma_node;/* Serialized by anon_vma->lock */ structanon_vma *anon_vma;/* Serialized by page_table_lock */ /* Function pointers to deal with this struct. */ conststructvm_operations_struct *vm_ops; /* Information about our backing store: */ unsignedlong vm_pgoff; /* Offset (within vm_file) in PAGE_SIZE units, *not* PAGE_CACHE_SIZE */ structfile * vm_file;/* File we map to (can be NULL). */ void * vm_private_data; /* was vm_pte (shared mem) */ unsignedlong vm_truncate_count;/* truncate_count or restart_addr */ #ifndef CONFIG_MMU structvm_region *vm_region;/* NOMMU mapping region */ #endif #ifdef CONFIG_NUMA structmempolicy *vm_policy;/* NUMA policy for the VMA */ #endif };
/* * These are the virtual MM functions - opening of an area, closing and * unmapping it (needed to keep files on disk up-to-date etc), pointer * to the functions called when a no-page or a wp-page exception occurs. */ structvm_operations_struct { void (*open)(struct vm_area_struct * area); //指定内存区域被加载到一个地址空间时函数被调用 void (*close)(struct vm_area_struct * area); //指定内存区域从地址空间删除时函数被调用 int (*fault)(struct vm_area_struct *vma, struct vm_fault *vmf); //没有出现在物理内存中的页面被访问时,页面故障处理调用该函数 /* notification that a previously read-only page is about to become * writable, if an error is returned it will cause a SIGBUS */ int (*page_mkwrite)(struct vm_area_struct *vma, struct vm_fault *vmf); /* called by access_process_vm when get_user_pages() fails, typically * for use by special VMAs that can switch between memory and hardware */ int (*access)(struct vm_area_struct *vma, unsignedlong addr, void *buf, int len, int write); #ifdef CONFIG_NUMA ...... #endif };
当可执行映像映射到进程的虚拟地址空间时,将产生一组vm_area_struct结构来描述虚拟内存区间的起始点和终止点,每个vm_area_struct结构代表可执行映像的一部分,可能是可执行代码,也可能是初始化的变量或未初始化的数据,这些都是在函数do_mmap()中来实现的。随着vm_area_struct结构的生成,这些结构所描述的虚拟内存区间上的标准操作函数也由 Linux 初始化。